EE 290: Advanced Topics in Computer-Aided Design: Modeling and Analysis of High-Dimensional Data
DESCRIPTION |
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. |
PREREQUISITES |
Linear Algebra, Introduction to Probability. Additional background from convex analysis, optimization, ect., will be introduced in the course as necessary. |
GRADING |
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. |
OFFICE HOURS |
Fridays, 4:00pm--5:00pm, 337 Cory Hall. |
SYLLABUS |
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
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
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
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
Applications
|
READINGS |
Lecture 1: Big Picture on High-Dim Data Analysis, Principal Component Analysis
Lecture 2: Nonlinear Dimensionality Reduction: Kernel PCA, Spectral Embedding
Lecture 3: Latent Variable Models: Factor Analysis, Probabilistic PCA, Missing Data, Expectation Maximization
Lecture 4: Union of Subspaces: K-Subspaces, Mixture of Factor Analyzers, Mixture of Probabilistic PCA
Lecture 5: Spectral Clustering, Analysis under Perturbation, Local Subspace Affinity, Spectral Curvature Clustering
Lecture 6: Algebraic-Geometric-Based Subspace Clustering, Efficient Eigen-Decomposition
Lecture 7: Sparse Representation: L0-norm, Greedy Pursuit, Convex Envelope, L1-norm Recovery, Geometry of Lp-norm recovery.
Lecture 8: Sparse Recovery Theory: Uniqueness Condition, Exact Recovery Condition, Spark, Mutual Coherence.
Lecture 9: Sparse Recovery Algorithms and Theory: Null-Space Property, Basis Pursuit De-Noising and Lasso, Orthogonal Matching Pursuit.
Lecture 10: Subspace Clustering and Dictionary Learning using Sparse Recovery, Subspace Null-Space Property.
Lecture 11: Affine Low-Rank Recovery, Low-Rank Matrix Completion, Nuclear-Norm Minimization, Rank-RIP.
Lecture 12: Noisy Low-Rank Matrix Completion, Robust Principal Component Analysis, Dual Certificates, Rank-Sparsity Incoherence.
|
TEXTBOOKS |
[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.
|
|