CaltechAUTHORS
  A Caltech Library Service

A duality view of spectral methods for dimensionality reduction

Xiao, Lin and Sun, Jun and Boyd, Stephen (2006) A duality view of spectral methods for dimensionality reduction. In: ICML '06 Proceedings of the 23rd international conference on Machine learning. ACM , New York, NY, pp. 1041-1048. ISBN 1-59593-383-2. http://resolver.caltech.edu/CaltechAUTHORS:20170109-152802886

[img] PDF - Published Version
See Usage Policy.

163Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20170109-152802886

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.


Item Type:Book Section
Related URLs:
URLURL TypeDescription
http://dx.doi.org/10.1145/1143844.1143975DOIArticle
http://dl.acm.org/citation.cfm?doid=1143844.1143975PublisherArticle
Additional Information:Copyright 2006 by the author(s)/owner(s). The authors are grateful to Lawrence Saul and Kilian Weinberger for insightful discussions. Part of this work was done when Lin Xiao was on a supported visit at the Institute for Mathematical Sciences, National University of Singapore.
Record Number:CaltechAUTHORS:20170109-152802886
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:20170109-152802886
Official Citation:Lin Xiao, Jun Sun, and Stephen Boyd. 2006. A duality view of spectral methods for dimensionality reduction. In Proceedings of the 23rd international conference on Machine learning (ICML '06). ACM, New York, NY, USA, 1041-1048. DOI: https://doi.org/10.1145/1143844.1143975
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:73351
Collection:CaltechAUTHORS
Deposited By: Kristin Buxton
Deposited On:10 Jan 2017 05:07
Last Modified:10 Jan 2017 05:07

Repository Staff Only: item control page