A duality view of spectral methods for dimensionality reduction

Lin Xiao, Jun Sun, Stephen Boyd

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

15 Scopus citations

Abstract

We present a unified duality view of several recently emerged spectral methods for nonlinear dimensionality reduction, including Isomap, locally linear embedding, Laplacian eigenmaps, and maximum variance unfolding. We discuss the duality theory for the maximum variance unfolding problem, and show that other methods are directly related to either its primal formulation or its dual formulation, or can be interpreted from the optimality conditions. This duality framework reveals close connections between these seemingly quite different algorithms. In particular, it resolves the myth about these methods in using either the top eigenvectors of a dense matrix, or the bottom eigenvectors of a sparse matrix - these two eigenspaces are exactly aligned at primal-dual optimality.

Original languageEnglish
Title of host publicationICML 2006 - Proceedings of the 23rd International Conference on Machine Learning
Pages1041-1048
Number of pages8
StatePublished - 2006
Externally publishedYes
EventICML 2006: 23rd International Conference on Machine Learning - Pittsburgh, PA, United States
Duration: Jun 25 2006Jun 29 2006

Publication series

NameICML 2006 - Proceedings of the 23rd International Conference on Machine Learning
Volume2006

Conference

ConferenceICML 2006: 23rd International Conference on Machine Learning
Country/TerritoryUnited States
CityPittsburgh, PA
Period06/25/0606/29/06

Fingerprint

Dive into the research topics of 'A duality view of spectral methods for dimensionality reduction'. Together they form a unique fingerprint.

Cite this