The Mathematics Behind Spectral Clustering And The Equivalence To PCA

2021-03-01 · T Shen

Spectral clustering is a popular algorithm that clusters points using the eigenvalues and eigenvectors of Laplacian matrices derived from the data. For years, spectral clustering has been working mysteriously. This paper explains spectral clustering by dividing it into two categories based on whether the graph Laplacian is fully connected or not. For a fully connected graph, this paper demonstrates the dimension reduction part by offering an objective function: the covariance between the original data points' similarities and the mapped data points' similarities. For a multi-connected graph, this paper proves that with a proper $k$, the first $k$ eigenvectors are the indicators of the connected components. This paper also proves there is an equivalence between spectral embedding and PCA.

📄 PDF Abstract BibTeX arXiv:2103.00733

Code (0)

등록된 구현이 없습니다.

Tasks

ClusteringDimensionality Reduction

Methods 이 논문이 사용한 방법론

Spectral Clustering Spectral clustering has attracted increasing attention due to the promising ability in dealing with nonlinearly separable datasets [15], [16]. In spectral clustering, the…

PCA Principle Components Analysis (PCA) is an unsupervised method primary used for dimensionality reduction within machine learning. PCA is calculated via a singular value…

UMAP Is Spectral Clustering on the Fuzzy Nearest-Neighbor Graph

2026-02-12 · Yang Yang arxiv

UMAP (Uniform Manifold Approximation and Projection) is among the most widely used algorithms for non linear dimensionality reduction and data visualisation. Despite its popularity, and despite being presented through th…

Dimensionality Reduction Contrastive Learning

Explainable Graph Spectral Clustering of Text Documents

2023-08-01 · Bartłomiej Starosta, Mieczysław A. Kłopotek, Sławomir T. Wierzchoń

Spectral clustering methods are known for their ability to represent clusters of diverse shapes, densities etc. However, results of such algorithms, when applied e.g. to text documents, are hard to explain to the user, e…

Clustering

Spectral Toolkit of Algorithms for Graphs: Technical Report (1)

2023-04-05 · Peter Macgregor, He Sun

Spectral Toolkit of Algorithms for Graphs (STAG) is an open-source library for efficient spectral graph algorithms, and its development starts in September 2022. We have so far finished the component on local graph clust…

Clustering Graph Clustering

A Nonlinear Orthogonal Non-Negative Matrix Factorization Approach to Subspace Clustering

2017-09-29 · Dijana Tolic, Nino Antulov-Fantulin, Ivica Kopriva

A recent theoretical analysis shows the equivalence between non-negative matrix factorization (NMF) and spectral clustering based approach to subspace clustering. As NMF and many of its variants are essentially linear, w…

Clustering

Contrastive Learning Is Spectral Clustering On Similarity Graph

2023-03-27 · Zhiquan Tan, Yifan Zhang, Jingqin Yang, Yang Yuan

Contrastive learning is a powerful self-supervised learning method, but we have a limited theoretical understanding of how it works and why it works. In this paper, we prove that contrastive learning with the standard In…

Clustering Contrastive Learning Self-Supervised Learning