TY - GEN
T1 - A duality view of spectral methods for dimensionality reduction
AU - Xiao, Lin
AU - Sun, Jun
AU - Boyd, Stephen
PY - 2006
Y1 - 2006
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=33749254086&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:33749254086
SN - 1595933832
SN - 9781595933836
T3 - ICML 2006 - Proceedings of the 23rd International Conference on Machine Learning
SP - 1041
EP - 1048
BT - ICML 2006 - Proceedings of the 23rd International Conference on Machine Learning
Y2 - 25 June 2006 through 29 June 2006
ER -