Minimax Embeddings
| Citation: |
Brand, M., "Minimax Embeddings", Neural Information Processing Systems, December 2003 (NIPS 2003) |
| MERL Report: | TR2004-102 |
Spectral methods for nonlinear dimensionality reduction(NLDR) impose a neighborhood graph on point data anc compute eigenfunctions of a quadratic form generated from the graph. We introduce a more general and more robust formulation of NLDR based on the singular value decomposition (SVD). In this framework, most spectral NLDR principles can be recovered by taking a subset of the constraints in a quadratic form built from local nullspaces on the manifold. The minimax formulation also opens up a interesting class of methods in which the graph is "decorated" with the information at the vertices, offering discrete or continuous maps, reduced computational complexity, and immunity to some solution instabilities of eigenfunction approaches. Apropos, we show almost all NLDR methods based on eigenvalue decompositions (EVD) have a solution instability that increases faster than problem size. This pathology can be observed (and corrected via the minimax formulation) in problems as small as N < 100 points.
