# Spectral Clustering via the Power Method -- Provably

arXiv: https://arxiv.org/abs/1311.2854 · HTML: https://mlsanity.com/paper/1311.2854/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Nov 2013.

## Built on by (most cited first, 10 of 10)

- [Graph Filters for Signal Processing and Machine Learning on Graphs](https://mlsanity.com/paper/2211.08854/) (2022)
- [Matrix Completion with Hierarchical Graph Side Information](https://mlsanity.com/paper/2201.01728/) (2022)
- [Fast and Simple Spectral Clustering in Theory and Practice](https://mlsanity.com/paper/2310.10939/) (2023)
- [Deep Spectral Clustering via Joint Spectral Embedding and Kmeans](https://mlsanity.com/paper/2412.11080/) (2024)
- [Spectral Clustering via Orthogonalization-Free Methods](https://mlsanity.com/paper/2305.10356/) (2023)
- [Free Lunch for Efficient Textual Commonsense Integration in Language Models](https://mlsanity.com/paper/2305.15516/) (2023)
- [A Novel Normalized-Cut Solver with Nearest Neighbor Hierarchical Initialization](https://mlsanity.com/paper/2311.15214/) (2023)
- [Blind Extraction of Equitable Partitions from Graph Signals](https://mlsanity.com/paper/2203.05407/) (2022)
- [Recovering Top-Two Answers and Confusion Probability in Multi-Choice Crowdsourcing](https://mlsanity.com/paper/2301.00006/) (2022)
- [PASCO (PArallel Structured COarsening): an overlay to speed up graph clustering algorithms](https://mlsanity.com/paper/2412.13592/) (2024)

## Abstract (arXiv)

Spectral clustering is one of the most important algorithms in data mining and machine intelligence; however, its computational complexity limits its application to truly large scale data analysis. The computational bottleneck in spectral clustering is computing a few of the top eigenvectors of the (normalized) Laplacian matrix corresponding to the graph representing the data to be clustered. One way to speed up the computation of these eigenvectors is to use the "power method" from the numerical linear algebra literature. Although the power method has been empirically used to speed up spectral clustering, the theory behind this approach, to the best of our knowledge, remains unexplored. This paper provides the first such rigorous theoretical justification, arguing that a small number of power iterations suffices to obtain near-optimal partitionings using the approximate eigenvectors. Specifically, we prove that solving the k-means clustering problem on the approximate eigenvectors obtained via the power method gives an additive-error approximation to solving the k-means problem on the optimal eigenvectors.