2003 · 142 citations · 22 references
ComputingComputer ScienceComputational GeometryData StructuresData VisualizationDimension ReductionDimensionality ReductionMatrix ComputationMatrix FactorizationSpectral AnalysisSpectral MethodsData AffinityDimensionality Reduction For ClusteringLow-dimensional EmbeddingsManifold LearningNonlinear Dimension ReductionNumerical Data RepresentationSpectral EmbeddingSubspace Learning
Spectral methods use selected eigenvectors of a data affinity matrix to obtain a data representation that can be trivially clustered or embedded in a low-dimensional space. We present a theorem that explains, for broad classes of affinity matrices and eigenbases, why this works: For successively smaller eigenbases (i.e., using fewer and fewer of the affinity matrix’s dominant eigenvalues and eigenvectors), the angles between “similar ” vectors in the new representation shrink while the angles between “dissimilar” vectors grow. Specifically, the sum of the squared cosines of the angles is strictly increasing as the dimensionality of the representation decreases. Thus spectral methods work because the truncated eigenbasis amplifies structure in the data so that any heuristic post-processing is more likely to succeed. We use this result to construct a nonlinear dimensionality reduction (NLDR) algorithm for data sampled from manifolds whose intrinsic coordinate system has linear and cyclic axes, and a novel clustering-by-projections algorithm that requires no post-processing and gives superior performance on “challenge problems” from the recent literature.
22
Nonlinear Dimensionality Reduction by Locally Linear Embedding
Sam T. Roweis, Lawrence K. Saul · Science · 2000 · 15K citations
On Spectral Clustering: Analysis and an algorithm
Andrew Y. Ng, Michael I. Jordan, Yair Weiss · 2001 · 7.8K citations
Algebraic connectivity of graphs
Miroslav Fiedler · Czechoslovak Mathematical Journal · 1973 · 4K citations · Full text