CS Paper Radar

Randomized SVD Approximations for Spectral Co-Clustering of Word-Document Matrices

Fateme Mazdarani, Carlos Toxtli

cs.LG cs.AI ·submitted 2026-09-16 17:42 UTC · v1
published

Abstract

Spectral co-clustering is a useful tool for discovering latent structure in word-document matrices, but its reliance on singular value decomposition (SVD) can make standard formulations expensive on high-dimensional data. This paper presents two randomized approximations for normalized spectral co-clustering of bipartite text data when the numbers of document and word clusters may differ. The first method uses randomized SVD through random projection, while the second combines partial SVD with element-wise random sampling. Across real-world and synthetic datasets, both methods reduce runtime relative to the full-SVD baseline, but their behavior depends on matrix sparsity. The random projection method is the more reliable approximation across the tested settings, whereas the sampling-based method is most useful on denser matrices and provides limited benefit on already sparse text data. These results show that randomized approximations for spectral co-clustering should be selected according to the underlying structure of the data.

Comment
Accepted to 2026 IEEE International Conference on Machine Learning and Applications (ICMLA)

Closest papers

Nearest neighbours by meaning across the whole index.

EigenLI: Spectral Approximations to Late Interaction

cs.IR cs.LG ·2026-09-07 ·Archish S, Sabyasachi Basu, Ankit Garg, Ravishankar Krishnaswamy, Kirankumar Shiragur
similarity 0.65
Abstract

Late-interaction models such as ColBERT achieve strong effectiveness by representing each document with many token-level vectors, but this expressivity leads to large indexing cost, storage footprints and expensive MaxSim scoring. We show that late-interaction representations exhibit an intrinsic low-rank structure: document token embeddings concentrate in a low-dimensional subspace that preserves most of the retrieval signal. Leveraging this observation, we introduce EigenLI, a spectral approximation framework that compresses late-interaction representations via document-specific low-dimensional subspaces. Unlike clustering or pooling methods, EigenLI identifies the dominant eigendirections of each document and uses them to construct reduced interaction representations. Empirically, $k$-EigenLI with $k \le 32$ outperforms k-means and Ward clustering based pooling methods on ColBERTv2 and AnswerAI-ColBERT-small; GTE-ModernColBERT exhibits a different tradeoff at $k=32$, where clustering methods perform better. The same spectral construction also yields EigenLI-SV, an ANN-compatible single-vector representation derived from the second-order summary of the reduced structure. Across multiple datasets and all three text models, EigenLI-SV consistently outperforms comparable single-vector surrogates such as MUVERA.

0.43

Kernelised covariance matrices, dimension reduction and imbalanced spectral clustering

cs.LG stat.MLmath.PRmath.SP ·2026-10-23 ·Xiaoyu Dong, Subhro Ghosh, Soumendu Sundar Mukherjee, Himasish Talukdar
similarity 0.57
Abstract

The Gaussian Mixture Model (abbrv. GMM) is a classic generative model for clustered data, for which spectral clustering based on dimension reduction via PCA has been an effective framework. In this work, we investigate kernelised covariance matrices as an alternative mechanism for dimension reduction and spectral clustering, focusing on truncation kernels that select pairs of data points with suitable separation constraints. The structure of these matrices is motivated by considerations from statistical mechanics of repulsive particle systems. Our approach is particularly relevant for the setting of imbalanced clusters, where the sizes of the largest and smallest clusters have a diverging ratio with the problem size, and existing PCA-based methods turn out to be of limited effectiveness. We demonstrate efficient dimension reduction and clustering performance of these modified covariance matrices, substantiated by quantitative bounds. In particular, they achieve superior dimension reduction guarantees compared to PCA for a wide range of parameters in the regime of imbalanced clusters. For spectral clustering, our approach exhibits improvements over PCA in the imbalanced setting, in particular guaranteeing accurate clustering in a much larger regime of intra-cluster separations. Our theoretical guarantees reflected in a range of simulation experiments that exhibit these improvements for unbalanced clustering problems. Our analytical approach, based on kernel Laplacians, provide a toolbox as well as a relevant conceptual ingredient for clustering problems at large. We believe that our work will motivate the application of such kernelised covariance matrices for related classes of statistical problems, as well as spur new investigations in the theory of random matrices.

0.22

Subzero matrix completion for sparse data analysis: large-scale learning of latent low-rank structure

cs.LG stat.ML ·2026-08-21 ·Lawrence K. Saul, Ningyuan Huang, Dennis Bollweg, Jeff Soules, Diana C. Halikias
similarity 0.57
Abstract

We investigate when a sparse nonnegative matrix can be recovered from a real-valued matrix of much lower rank by zeroing out its negative elements. The potential for such decompositions suggests a mathematical connection between sparsity and rank; we analyze a number of sparse matrices with this latent low-rank structure and use them to illustrate the geometric origins of this connection. Previous algorithms have discovered these decompositions via an alternating minimization over the factors of a low-rank matrix, but to do so, they have also needed to compute and store another matrix, neither sparse nor low-rank, that is the size of their product. We develop a stochastic, alternating least-squares algorithm that operates on smaller blocks of this dense matrix and scales as a result to much larger problems. We also show how to further accelerate this algorithm with sparse optimizations and customized CUDA kernels. As one example, we use the algorithm to analyze the sparse matrix of synaptic weights for the recently published $\textit{Drosphilia}$ connectome. The nonzero elements of this matrix, with 139,255 rows and columns, record the number of synapses between cells in the nervous system of a female fruit fly. Despite a slowly decaying spectrum of singular values, this matrix exhibits a latent low-rank structure that is predictive of cell categories across multiple levels of specificity.

0.38

A Manifold-Aware Topic Modeling Approach via Rank-Based Prototypes

cs.LG cs.AIcs.CLcs.IR ·2026-08-29 ·Thiago César Castilho Almeida, Daniel Carlos Guimarães Pedronette
top venuecode/data similarity 0.56
Abstract · Accepted at the Main Conference of 2026 Conference on Empirical Methods in Natural Language Processing (EMNLP 2026)

Recent topic models leverage pretrained embeddings, but neural architectures produce latent representations without grounding in specific texts, and clustering-based pipelines assign representative documents only post hoc, relying on absolute distances distorted by hubness and anisotropy in high-dimensional spaces. We introduce MARETopic, a training-free framework that casts topic discovery as rank-based prototype selection. After projecting embeddings onto a low-dimensional manifold, MARETopic builds ranked lists encoding ordinal neighborhood structure. A greedy algorithm selects exactly K exemplar documents, real corpus texts, whose neighborhoods cover the corpus. Two variants share this criterion. MARETopic$_\text{Corr}$ scores candidates with a query performance predictor and a rank correlation measure, leading Purity and NMI on the two benchmarks with the most categories, ahead of both neural and clustering-based topic models. MARETopic$_\text{Diff}$ scores them with a rank-based diffusion matrix, needs neither measure, and runs 1.7 to 1.9 times faster. Without a single gradient update, MARETopic leads topic coherence on two of three datasets. A novel inter-topic Maximal Marginal Relevance step raises vocabulary diversity at little cost in coherence. Our code is available at https://github.com/thcastilho/maretopic.

0.54

LoomSC: Scalable Deep Subspace Clustering with Projector Factorization and Exact Spectral Reduction

cs.CV cs.AI ·2026-10-07 ·Nairouz Mrabah, Youssef Melki, Mohamed Bouguessa, Riadh Ksantini, Shakeeb Murtaza +1 more
similarity 0.55
Abstract · 19 pages, 7 figures, 5 tables; includes appendices

Dense self-expression matrices and full-affinity spectral clustering limit the scalability of subspace clustering. We introduce the Latent Orthogonal Optimization Model for Subspace Clustering (LoomSC), a framework that addresses both bottlenecks through projector factorization and exact spectral reduction. Motivated by the spectral structure of least-squares regression, LoomSC jointly learns latent features and a projector self-representation through two thin factors. Alternating Procrustes and least-squares updates preserve the sample factor's orthogonality while keeping the coefficient matrix implicit. We construct a nonnegative quadratic affinity that preserves the projector's support. An exact feature map then reduces its normalized spectral problem to an eigenproblem whose dimension depends only on the factor width. Neither the full affinity nor the sample Laplacian needs to be formed. Our analysis quantifies the projector approximation and identifies conditions for subspace preservation and within-subspace connectivity. For fixed dimensions and iteration budgets, the complete pipeline has linear time and memory complexity in the number of samples. Across five image-clustering benchmarks, LoomSC ranks first or second in all 15 dataset-metric comparisons against 9 state-of-the-art baselines. Its mean accuracy exceeds the highest baseline mean by 6.66 percentage points. Synthetic experiments scale to 500,000 samples while maintaining at least 99.8% accuracy.

0.24

Fast Length-Squared Sampling for Positive-Semidefinite Matrices

cs.DS cs.LG ·2026-08-12 ·Rajarshi Bhattacharjee, Ethan N. Epperly, Cameron Musco, Aaron Tian
similarity 0.55
Abstract

We describe a simple rejection-sampling-based algorithm to perform length-squared sampling on an $n \times n$ positive-semidefinite (psd) matrix: that is, to sample a column with probability proportional to its squared $\ell_2$-norm. The algorithm runs in just $O(n)$ expected time, which is significantly sublinear in the input matrix size. The runtime is optimal, even when the input is assumed to be diagonal. Our result has several applications. Length-squared sampling is used by a number of sublinear time algorithms for matrix problems, like low-rank approximation and eigenvalue approximation. Often, it is assumed that the algorithm is given access to the matrix column norms, and thus can perform length-squared sampling efficiently. Our result shows that, at least for psd matrices, we can remove this assumption. We also discuss an application to an asymptotically optimal algorithm for estimating the Frobenius norm of a psd matrix to relative error. Finally, we show that our sampling algorithm yields a very simple sublinear time algorithm for the robust psd low-rank approximation problem introduced by Bakshi et al. (FOCS, 2020), which nearly matches the more complex method developed there.

0.04

Efficient Group-Penalty k-means for Text Clustering with Noisy LLM-Generated Constraints

cs.DB ·2026-10-28 ·Feiteng Nie, Yuan Sun, Shengkun Zhu, Sheng Wang, Zhiyong Peng
theory similarity 0.55
Abstract

k-means provides a simple and efficient foundation for text clustering, but embedding alone can miss task-specific semantic boundaries. Must-link (ML) and cannot-link (CL) constraints can correct such errors, yet conventional constrained clustering assumes that these relations are already supplied. LLMs can generate them without task-specific labels, but exhaustive querying is costly and their judgments can be incorrect. We present GPKmeans, an efficient Group-Penalty k-means method for text clustering with noisy LLM-generated constraints. GPKmeans uses LLM as an offline local pairwise annotator, querying selected anchor-candidate pairs for sparse ML links and constructing set-valued CL evidence without all-pairs queries. It converts connected components of the ML-link graph and the generated CL sets into groups with normalized, bounded soft penalties, limiting each group's influence independently of its size. Cached coordinate descent is proposed to efficiently solve the constraints clustering problem. We prove finite-step convergence and derive deterministic and probabilistic oracle-referenced bounds that relate objective distortion to the penalty coefficients and to the group-level error probabilities of the generated constraints. Across nine datasets, GPKmeans uses fewer LLM calls and yields more accurate constraints. It achieves the best average ACC, NMI, and ARI while running approximately 30 times faster than state-of-the-art constrained clustering methods.

0.20

A Subsampled Davis-Kahan Bound for Large-Scale Eigenspace Estimation

cs.LG stat.MLstat.ME ·2026-09-06 ·Huan Qing
theoryhot direction similarity 0.54
Abstract · 24 pages

The Davis-Kahan theorem is a fundamental tool in spectral analysis, providing quantitative control over the distance between the eigenspaces of a symmetric matrix and its perturbation. However, when the matrix dimension is large, computing leading eigenvectors is computationally expensive, limiting the practical use of spectral methods in modern large-scale applications. This paper addresses this problem by proposing an independent Bernoulli sampling scheme and proves that the leading left singular vectors of the subsampled matrix faithfully approximate the target subspace of a low-rank symmetric matrix. Our main result is a subsampled Davis-Kahan bound that gives an explicit error bound depending directly on the sampling probability. The bound reveals the trade-off: the computational cost scales linearly with the sampling probability, while the statistical error scales as the inverse square root of the sampling probability. Our result thus extends the Davis-Kahan theorem to the subsampled setting, enabling scalable spectral analysis of large-scale symmetric matrices.

0.25