I describe here the topics covered and references used
1. Background: SVD, PCA, MDS, Numerical linear algebra
At one point (some time after course) I will polish my notes and put them here.
Anyway, for SVD and related issues of numerical linear algebra I used mainly
Applied Numerical Linear Algebra by James W. Demmel
and a bit of
Numerical Linear Algebra by Lloyd N. Trefethen and David Bau III
We showed how to find least squares d-flat via SVD/PCA (proof based on Ky Fan Inequality).
We also described MDS as a way of recovering coordinates from distances (up to a rigid transformation)
and emphasized the relation to PCA.
I am not sure of a good reference for the above two points, and thus will try to put it in notes in the future.
We mentioned also random sampling methods for fast SVD and in particular two interesting theoretical results
* Sampling from Large Matrices: An Approach through Geometric Functional Analysis by Rudelson and Vershynin
* Adaptive Sampling and
Fast Low-Rank Matrix Approximation by Deshpande and Vempala
2. Kernel methods and Kernel PCA
For some basic ideas on kernel we used parts of Chapter 2 of
Learning with Kernels by Bernhard Schölkopf and Alex Smola
For kernel PCA we followed
Nonlinear Component Analysis as a Kernel Eigenvalue Problem by Scholkopf, Smola and Muller
3. Spectral Clustering
We followed
A Tutorial on Spectral Clustering by Ulrike von Luxburg
and also discussed some details behind the proof of
On Spectral Clustering: Analysis and an algorithm by Ng, Jordan and Weiss
We related it to Kernel K-means (and more easily to Kernel PCA)
Kernel kmeans,
Spectral Clustering and Normalized Cuts by Dhilon, Guan and Kulis
4. Some Manifold Embedding Algorithms
We distinguish between
A.
Manifold parameterizing algorithms (following the formulation in
Image manifolds which are isometric to Euclidean space by Donoho and Grimes)
Those included
1. Isomap, which is described in
A Global Geometric Framework
for Nonlinear Dimensionality
Reduction by Tenenbaum, de Silva and Langford
(we also followed Donoho and Grimes above)
2. Hessian Eigenmaps, which is described in
Hessian eigenmaps: Locally linear embedding
techniques for high-dimensional data by Donoho and Grimes
(we discussed only theoretical justification and no numerical details)
3. LTSA, which is described in
Principal Manifolds and Nonlinear Dimension Reduction via Local Tangent Space Alignment by Zhang and Zha
B. "clustering oriented" embeddings
1. LLE, which is described in
Nonlinear Dimensionality Reduction by Locally Linear Embedding by Roweis and Saul
Think Globally, Fit Locally:
Unsupervised Learning of Low Dimensional Manifoldsk by Roweis and Saul
2. Laplacian eigenmap
Laplacian Eigenmaps for Dimensionality Reduction and Data Representation by Belkin and Niyogi
We termed them "clustering oriented" due to the tendency of laplacain eigenmap to cluster (e.g., embedding of bottleneck). It also partially true for LLE (as we showed their close relation). Nevertheless, we also mentioned stronger geometric properties of the embedding following
Universal Local Parametrizations via Heat Kernels and Eigenfunctions of the Laplacian by Jones, Maggioni and Schul
Another theoretical aspect relating the continuous case (discussed above) to the discrete one was mentioned following
Towards a Theoretical Foundation for Laplacian-Based Manifold Methods by Belkin and Niyogi
5. Hybrid Linear Modeling (HLM)
Many aspects and interesting applications of HLM are covered in the book
Generalized Principal Component Analysis:
Modeling & Segmentation of Multivariate Mixed Data by Vidal, Ma and Sastry
We also covered the following specific techniques (with the application of motion segmentation in mind):
1. K-flats (easy generalization of K-means, for exmaple in
k-Plane Clustering by
Bradley, Mangasarian and Pardalos
and related issues
2. GPCA (all in book above)
3.
Local Subspace Alignment (LSA)
A general framework for motion segmentation by Yan and M. Pollefeys
4. Subspace separation and Multi-Stage Learning (MSL)
A multibody factorization method for independently
moving objects by Costeira and Kanade
Motion Segmentation by Subspace Separation and Model Selection by Kanatani
Spectral Clustering for Robust Motion Segmentation by
Park, Zha and Kasturi
Geometric structure of degeneracy
for multi-body motion segmentation by Sugaya and Kanatani.
5.
Lossy Data Coding for hybrid linear modeling and motion segmentation
Following the 3 papers in
http://perception.csl.uiuc.edu/coding/publications.htm
6. Spectral Curvature Clustering (SCC) following the 2 papers in
http://www.math.umn.edu/~lerman/scc/
5. Direct Methods for Multi-Manifold Modeling
We first talked about local methods, in particular localizing SCC.
We then studied carefully the application of local Gaussians + Hellinger distance (for their "alignment") in the context of semi-supervised learning, following
Multi-manifold semi-supervised learning by
Goldberg, Zhu, Singh, Xu, and Nowak.
We also covered the following related papers
Semi-supervised learning using Gaussian fields and harmonic functions by Zhu, Ghahramani, and Lafferty,
Combining active learning and semi-supervised learning using Gaussian fields and harmonic functions by Zhu, Lafferty, and Ghahramani. .
Unlabeled data: Now it helps, now it doesn't by
Singh, Nowak, and Zhu.
We then talked about cases where one cannot apply local methods due to sparse and nonuniform sampling, but the underlying manifolds belong to a certain model. We showed how to use kernels there and discussed related applications.
6. Sparse Approximation and Possible Relations.
Mark Iwen
introduced us to Compressed Sensing (CS) in 3 lectures. He talked about compressible signals, and simple combinatorial CS methods for recovering them. He then presented a construction of RIP matrices and also discussed L1-RIP matrices and their relationship to expander graph.
Pablo Sprechmann covered the following works on matrix completion
Matrix Completion from a Few Entries by
Keshavan, Oh and Montanari
Matrix Completion by Emmanuel Candes and collaborators (whatever available at that time)
We also talked about possible relations to HLM.