# Clustering as Approximation by Constrained Projectors: Theory and Guarantees

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 4 of its 42 references that are in the map.
- First posted on arXiv 29 Aug 2026.

## Builds on (most cited first, 4 of 4)

- [Robust subspace clustering](https://mlsanity.com/paper/1301.2603/) (2013)
- [Kernel-based Graph Learning from Smooth Signals: A Functional Viewpoint](https://mlsanity.com/paper/2008.10065/) (2020)
- [Approximating Spectral Clustering via Sampling: a Review](https://mlsanity.com/paper/1901.10204/) (2019)
- [Fuzzy K-Means Clustering without Cluster Centroids](https://mlsanity.com/paper/2404.04940/) (2024)

## Abstract (arXiv)

This paper develops a unified theoretical framework showing that a broad family of clustering methods, including k-means, fuzzy c-means, kernel k-means, kernel FCM, and spectral clustering, can all be expressed as structured low-rank projectors acting on a signal-derived matrix. By formulating each method as an instance of min over B in C of ||M - M P_B||_F^2, with different constraint sets C, we establish a common optimization template that clarifies the algebraic links among hard, fuzzy, kernel-induced, and orthonormal projections. Within this framework, we derive non-trivial theoretical results, including geodesic convexity properties on the projection manifold, perturbation bounds quantifying stability to matrix noise, and exact recovery guarantees under ideal block-model conditions. The analysis further explains when different clustering families collapse to the same optimal subspace and how deviations arise under small inter-cluster leakage. Overall, the work provides a coherent, theory-first foundation for understanding clustering through structured projectors.