Abstract

TUTORIAL - Spectral Methods for Dimensionality Reduction (Part 1)

Lawrence Saul
University of Pennsylvania

How can we detect low dimensional structure in high dimensional data? If the data is mainly confined to a low dimensional subspace, then simple linear methods can be used to discover the subspace and estimate its dimensionality. More generally, though, if the data lies on (or near) a low dimensional submanifold, then its structure may be highly nonlinear,and linear methods are bound to fail. 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. The matrices are constructed from sparse weighted graphs whose vertices represent data points and whose edges indicate neighborhood relations. The main
computations for manifold learning are based on highly tractable optimizations, such as shortest path problems, least squares fits,semidefinite programming, and matrix diagonalization.

In this tutorial, I will provide an overview of unsupervised learning algorithms that can be viewed as spectral methods for linear and
nonlinear dimensionality reduction.

Presentation (PDF File)
Video of Talk (RealPlayer File)