Clustering as Approximation by Constrained Projectors: Theory and Guarantees

• URL: http://arxiv.org/abs/2608.29102v1
• Date: Sat, 29 Aug 2026 07:19:04 GMT
• Title: Clustering as Approximation by Constrained Projectors: Theory and Guarantees
• Abstract summary: 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.
• Score: 11.62669179647184
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• 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.

Related papers

• Weight-Informed Self-Explaining Clustering for Mixed-Type Tabular Data [63.62853416081748]
  WISE is a framework that unifies representation, feature weighting, clustering, and interpretation.<n>It produces faithful, human-interpretable explanations grounded in the same primitives that drive clustering.
  arXiv  Detail & Related papers  (2026-04-07T13:18:31Z)
• Universal NP-Hardness of Clustering under General Utilities [11.62669179647184]
  We formalise the common optimisation core motivating a diverse-time computable partition utility over a finite metric space.<n>By mapping ten major paradigms -- including k-means, GMMs, DBSCAN, spectral clustering, and affinity propagation -- to the UCP framework, we demonstrate that each inherits this fundamental inability.
  arXiv  Detail & Related papers  (2026-02-27T13:08:15Z)
• A Unified Matrix Factorization Framework for Classical and Robust Clustering [11.62669179647184]
  This paper presents a unified matrix factorization framework for classical and robust clustering.<n>We derive an analogous matrix factorization interpretation for fuzzy c-means clustering, which to the best of our knowledge has not been previously formalized.<n>To address sensitivity to outliers, we propose robust formulations for both crisp and fuzzy clustering by replacing the Frobenius norm with the l1,2-norm.
  arXiv  Detail & Related papers  (2025-10-24T05:51:48Z)
• Self-Supervised Graph Embedding Clustering [70.36328717683297]
  K-means one-step dimensionality reduction clustering method has made some progress in addressing the curse of dimensionality in clustering tasks. We propose a unified framework that integrates manifold learning with K-means, resulting in the self-supervised graph embedding framework.
  arXiv  Detail & Related papers  (2024-09-24T08:59:51Z)
• Spectral Clustering for Directed Graphs via Likelihood Estimation on Stochastic Block Models [22.421702511126373]
  We leverage statistical inference on block models to guide the development of a spectral clustering algorithm for directed graphs.<n>We establish a theoretical upper bound on the misclustering error of its spectral relaxation, and based on this relaxation, introduce a novel, self-adaptive spectral clustering method for directed graphs.
  arXiv  Detail & Related papers  (2024-03-28T15:47:13Z)
• Wide Gaps and Clustering Axioms [0.0]
  k-means is in conflict with Kleinberg's axiomatic system for distance based clustering algorithms. We introduce two new clusterability properties, variational k-separability and residual k-separability. We reconcile k-means with Kleinberg's axiomatic framework in Euclidean and non-Euclidean settings.
  arXiv  Detail & Related papers  (2023-08-07T10:43:48Z)
• Multi-View Clustering via Semi-non-negative Tensor Factorization [120.87318230985653]
  We develop a novel multi-view clustering based on semi-non-negative tensor factorization (Semi-NTF) Our model directly considers the between-view relationship and exploits the between-view complementary information. In addition, we provide an optimization algorithm for the proposed method and prove mathematically that the algorithm always converges to the stationary KKT point.
  arXiv  Detail & Related papers  (2023-03-29T14:54:19Z)
• Perfect Spectral Clustering with Discrete Covariates [68.8204255655161]
  We propose a spectral algorithm that achieves perfect clustering with high probability on a class of large, sparse networks. Our method is the first to offer a guarantee of consistent latent structure recovery using spectral clustering.
  arXiv  Detail & Related papers  (2022-05-17T01:41:06Z)
• Provable Clustering of a Union of Linear Manifolds Using Optimal Directions [8.680676599607123]
  This paper focuses on the Matrix Factorization based Clustering (MFC) method which is one of the few closed form algorithms for the subspace clustering problem. We reveal the connection between MFC and the Innovation Pursuit (iPursuit) algorithm which was shown to be able to outperform the other spectral clustering based methods.
  arXiv  Detail & Related papers  (2022-01-08T02:36:25Z)
• Clustering Ensemble Meets Low-rank Tensor Approximation [50.21581880045667]
  This paper explores the problem of clustering ensemble, which aims to combine multiple base clusterings to produce better performance than that of the individual one. We propose a novel low-rank tensor approximation-based method to solve the problem from a global perspective. Experimental results over 7 benchmark data sets show that the proposed model achieves a breakthrough in clustering performance, compared with 12 state-of-the-art methods.
  arXiv  Detail & Related papers  (2020-12-16T13:01:37Z)
• Multi-View Spectral Clustering Tailored Tensor Low-Rank Representation [105.33409035876691]
  This paper explores the problem of multi-view spectral clustering (MVSC) based on tensor low-rank modeling. We design a novel structured tensor low-rank norm tailored to MVSC. We show that the proposed method outperforms state-of-the-art methods to a significant extent.
  arXiv  Detail & Related papers  (2020-04-30T11:52:12Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.