Clustering as Approximation by Constrained Projectors: Theory and Guarantees
Artificial IntelligenceMachine Learning
Summary
The authors present a theory that shows many common clustering methods, like k-means and spectral clustering, can be seen as special ways of projecting data onto simpler structures called low-rank projectors. They create a single mathematical template that explains how these methods relate and differ based on certain constraints. Using this unified approach, they prove new results about stability, accuracy, and connections between clustering types, helping to better understand when and why different methods agree or differ. This work offers a clear, math-focused perspective on clustering techniques.
Authors
Angshul Majumdar
Abstract
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.