Spectral methods for dimensionality reduction
 
L. K. Saul, K. Q. Weinberger, J. H. Ham, F. Sha, and D.D. Lee (2006)
Spectral methods for dimensionality reduction
To appear in B. Schoelkopf, O. Chapelle, and A. Zien (eds.), Semisupervised Learning. MIT Press: Cambridge, MA.
[pdf][bib]
 
Spectral methods for dimensionality reduction
Monday, May 15, 2006
Spectral methods have recently emerged as a powerful tool for nonlinear dimensionality reduction and manifold learning. These methods are able to reveal low dimensional structure in high dimensional data from the top or bottom eigenvectors of specially constructed matrices. To analyze data that lies on a low dimensional submanifold, the matrices are constructed from sparse weighted graphs whose vertices represent input patterns and whose edges indicate neighborhood relations. The main computations for manifold learning are based on tractable, polynomial-time optimizations, such as shortest path problems, least squares fits, semidefinite programming, and matrix diagonalization. This chapter provides an overview of unsupervised learning algorithms that can be viewed as spectral methods for linear and nonlinear dimensionality reduction.