# Fast Length-Squared Sampling for Positive-Semidefinite Matrices

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

## Key facts

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

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

- [Stochastic Gradient Descent, Weighted Sampling, and the Randomized Kaczmarz algorithm](https://mlsanity.com/paper/1310.5715/) (2013)
- [Less is More: Nystr"om Computational Regularization](https://mlsanity.com/paper/1507.04717/) (2015)
- [Kernel methods through the roof: handling billions of points efficiently](https://mlsanity.com/paper/2006.10350/) (2020)
- [Fastfood: Approximate Kernel Expansions in Loglinear Time](https://mlsanity.com/paper/1408.3060/) (2014)
- [A quantum-inspired classical algorithm for recommendation systems](https://mlsanity.com/paper/1807.04271/) (2018)
- [On Fast Leverage Score Sampling and Optimal Learning](https://mlsanity.com/paper/1810.13258/) (2018)
- [Determinantal Point Processes in Randomized Numerical Linear Algebra](https://mlsanity.com/paper/2005.03185/) (2020)
- [Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning](https://mlsanity.com/paper/1910.06151/) (2019)
- [Randomly pivoted Cholesky: Practical approximation of a kernel matrix with few entry evaluations](https://mlsanity.com/paper/2207.06503/) (2022)
- [Sublinear Time Low-Rank Approximation of Positive Semidefinite Matrices](https://mlsanity.com/paper/1704.03371/) (2017)
- [Testing probability distributions underlying aggregated data](https://mlsanity.com/paper/1402.3835/) (2014)
- [Sample-Optimal Low-Rank Approximation of Distance Matrices](https://mlsanity.com/paper/1906.00339/) (2019)
- [Sublinear Time Low-Rank Approximation of Distance Matrices](https://mlsanity.com/paper/1809.06986/) (2018)
- [Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra](https://mlsanity.com/paper/2011.04125/) (2020)
- [Sublinear Time Eigenvalue Approximation via Random Sampling](https://mlsanity.com/paper/2109.07647/) (2021)
- [Robust and Sample Optimal Algorithms for PSD Low-Rank Approximation](https://mlsanity.com/paper/1912.04177/) (2019)
- [Embrace rejection: Kernel matrix approximation by accelerated randomly pivoted Cholesky](https://mlsanity.com/paper/2410.03969/) (2024)
- [Turnstile ℓp leverage score sampling with applications](https://mlsanity.com/paper/2406.00339/) (2024)
- [Tight Sampling Bounds for Eigenvalue Approximation](https://mlsanity.com/paper/2411.03227/) (2024)
- [Column and row subset selection using nuclear scores: algorithms and theory for Nystr"om approximation, CUR decomposition, and graph Laplacian reduction](https://mlsanity.com/paper/2407.01698/) (2024)
- [Sublinear Time Eigenvector Approximation via Column Sampling](https://mlsanity.com/paper/2608.00840/) (2026)

## Abstract (arXiv)

We describe a simple rejection-sampling-based algorithm to perform length-squared sampling on an n × n positive-semidefinite (psd) matrix: that is, to sample a column with probability proportional to its squared ℓ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.