The increasing amounts of high-dimensional data across different science and engineering disciplines requires efficient algorithms for analyzing and uncovering the structure in the data. This course covers state-of-the-art algorithms for modeling and analysis of high-dimensional datasets with low-dimensional structures. The course introduces different classes of methods, including latent variable models, spectral clustering-based methods, and sparse/low-rank representation-based algorithms, and covers the theoretical tools for the analysis of each class of methods. In addition, the course provides students with implementation experience of different algorithms and discusses applications of these tools in signal/image processing, controls, computer vision and bio-informatics.

Linear Algebra, Introduction to Probability. Additional background from convex analysis, optimization, ect., will be introduced in the course as necessary.

There will be 4 homeworks, which include both analytical exercises and programming assignments in MATLAB or Python. The course will have a final project (4th HW), which will be on analytical problems or research-related applications. The final project can be done individually or in teams of two students.

Fridays, 4:00pm--5:00pm, 337 Cory Hall.

1. Modeling and Analysis of Data in a Single Subspace

• Principal Component Analysis (PCA), Factor Analysis, Probabilistic PCA

• Robust Principal Component Analysis: Dealing with Missing Entries and Errors

• Kernel Principal Component Analysis: Dealing with Data in Nonlinear Manifolds

• Other Extensions of PCA

2. Modeling and Analysis of Data in Multiple Subspaces

• Iterative Algorithms: K-Subspaces, Mixture of Factor Analyzers

• Algebraic Algorithms: Generalized PCA

• Spectral Clustering-Based Algorithms: Local Subspace Affinity, Spectral Curvature Clustering, Sparse Subspace Clustering

3. Sparse and Low-Rank Recovery Theory

• Sparsity and Properties of Different Norms

• Coherence, Null-Space Property and Generalization to Subspaces

• Restricted Isometry Property (RIP) and Rank-RIP

• Group-Sparsity, Multiple Measurement Vector Problems

4. Sparse and Low-Rank Optimization Methods

• Convex Algorithms: Proximal Methods, Alternating Direction Methods, Non-smooth Convex Optimization

• Greedy Algorithms: Matching Pursuit, Orthogonal Matching Pursuit, Subspace Pursuit

• Homotopy Algorithms

5. Applications

• Compressive Sensing

• Dictionary Learning

• Compression and Clustering of Visual Data

• System Identification

• Other Application Areas: Energy Systems, Bio-informatics

Lecture 1: Big Picture on High-Dim Data Analysis, Principal Component Analysis

• Chapter 2 of VMS book

Lecture 2: Nonlinear Dimensionality Reduction: Kernel PCA, Spectral Embedding

• Kernel PCA by Scholkopf, Smola and Muller

• Locally Linear Embedding by Roweis and Saul

• Laplacian Eigenmaps by Belkin and Niyogi

Lecture 3: Latent Variable Models: Factor Analysis, Probabilistic PCA, Missing Data, Expectation Maximization

• Factor Analysis

• Probabilistic PCA by Tipping and Bishop

• Expectation Maximization (EM) note by Andrew Ng

Lecture 4: Union of Subspaces: K-Subspaces, Mixture of Factor Analyzers, Mixture of Probabilistic PCA

• K-Subspaces by Ho and Kriegman

• Mixture of Factor Analyzers by Ghahramani and Hinton

• Mixture of Probabilistic PCA by Tipping and Bishop

Lecture 5: Spectral Clustering, Analysis under Perturbation, Local Subspace Affinity, Spectral Curvature Clustering

• Tutorial on Spectral Clustering by von Luxburg

• Spectral Clustering Analysis under Perturbation by Huang and Jordan

• Normalized Cuts by Shi and Malik

• Local Subspace Affinity by Yan and Pollefeys

• Spectral Curvature Clustering by Chen and Lerman

Lecture 6: Algebraic-Geometric-Based Subspace Clustering, Efficient Eigen-Decomposition

• Generalized PCA by Vidal, Ma and Sastry

• Power Method, Generalized Power Method and Lanczos Iterations

Lecture 7: Sparse Representation: L0-norm, Greedy Pursuit, Convex Envelope, L1-norm Recovery, Geometry of Lp-norm recovery.

• Atomic Decomposition via Basis Pursuit by Chen, Donoho and Saunders

• Convex Envelope of Complexity Controlling Penalties by Jojic, Saria and Koller

• An Introduction to Compressive Sensing by Davenport, et al.

Lecture 8: Sparse Recovery Theory: Uniqueness Condition, Exact Recovery Condition, Spark, Mutual Coherence.

• Sparse Recovery in Arbitrary Dictionaries via L1 by Donoho and Elad

• From Sparse Solutions of Systems of Equations to Sparse Modeling of Signals and Images by Bruckstein, Donoho and Elad

Lecture 9: Sparse Recovery Algorithms and Theory: Null-Space Property, Basis Pursuit De-Noising and Lasso, Orthogonal Matching Pursuit.

• Stable Sparse Recovery in the Presence of Noise by Donoho, Elad and Temlyakov

• Regression Shrinkage and Selection via LASSO by Tibshirani

• Orthogonal Matching Pursuit by Pati, Rezaifar and Krishnaprasad

Lecture 10: Subspace Clustering and Dictionary Learning using Sparse Recovery, Subspace Null-Space Property.

• Sparse Subspace Clustering by Elhamifar and Vidal

• Dictionary Learning via K-SVD by Aharon, Elad and Bruckstein

Lecture 11: Affine Low-Rank Recovery, Low-Rank Matrix Completion, Nuclear-Norm Minimization, Rank-RIP.

• Near Optimal Matrix Completion by Candes and Tao

• Guaranteed Minimum Rank Solutions of Linear Matrix Equation via Nuclear Norm Minimization by Recht, Parrilo and Fazel

Lecture 12: Noisy Low-Rank Matrix Completion, Robust Principal Component Analysis, Dual Certificates, Rank-Sparsity Incoherence.

• Matrix Completion with Noise by Candes and Plan

• Rank-Sparsity Incoherence for Matrix Decomposition by Chandrasekaran, Sanghavi, Parrilo and Willsky

• Homework 1     Data     Due Date: 10/10/2014

• Homework 2     Data     Due Date: 11/14/2014

• Homework 3     Data     Due Date: 12/12/2014

• [ME] M. Elad, Sparse and Redundant Representations: From Theory to Applications in Signal and Image Processing, Springer.

• [KM] K. Murphy, Machine Learning: A Probabilistic Perspective, MIT Press.