# Sublinear Time Low-Rank Approximation of Positive Semidefinite Matrices

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

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Apr 2017.

## Built on by (most cited first, 18 of 18)

- [Randomly pivoted Cholesky: Practical approximation of a kernel matrix with few entry evaluations](https://mlsanity.com/paper/2207.06503/) (2022)
- [Learning a Latent Simplex in Input-Sparsity Time](https://mlsanity.com/paper/2105.08005/) (2021)
- [Recent and Upcoming Developments in Randomized Numerical Linear Algebra for Machine Learning](https://mlsanity.com/paper/2406.11151/) (2024)
- [Efficient Nearest Neighbor Search for Cross-Encoder Models using Matrix Factorization](https://mlsanity.com/paper/2210.12579/) (2022)
- [Faster Kernel Matrix Algebra via Density Estimation](https://mlsanity.com/paper/2102.08341/) (2021)
- [Low-Rank Approximation with 1/ε1/3 Matrix-Vector Products](https://mlsanity.com/paper/2202.05120/) (2022)
- [Embrace rejection: Kernel matrix approximation by accelerated randomly pivoted Cholesky](https://mlsanity.com/paper/2410.03969/) (2024)
- [Faster Linear Systems and Matrix Norm Approximation via Multi-level Sketched Preconditioning](https://mlsanity.com/paper/2405.05865/) (2024)
- [Sublinear Time Approximation of Text Similarity Matrices](https://mlsanity.com/paper/2112.09631/) (2021)
- [Relating tSNE and UMAP to Classical Dimensionality Reduction](https://mlsanity.com/paper/2306.11898/) (2023)
- [Hardness of Low Rank Approximation of Entrywise Transformed Matrix Products](https://mlsanity.com/paper/2311.01960/) (2023)
- [Sub-quadratic Algorithms for Kernel Matrices via Kernel Density Estimation](https://mlsanity.com/paper/2212.00642/) (2022)
- [Krylov Methods are (nearly) Optimal for Low-Rank Approximation](https://mlsanity.com/paper/2304.03191/) (2023)
- [Ridge Leverage Score Sampling for ℓp Subspace Approximation](https://mlsanity.com/paper/2407.03262/) (2024)
- [Randomly Pivoted Partial Cholesky: Random How?](https://mlsanity.com/paper/2404.11487/) (2024)
- [Adaptive Retrieval and Scalable Indexing for k-NN Search with Cross-Encoders](https://mlsanity.com/paper/2405.03651/) (2024)
- [Improved analysis of randomized SVD for top-eigenvector approximation](https://mlsanity.com/paper/2202.07992/) (2022)
- [Fast Length-Squared Sampling for Positive-Semidefinite Matrices](https://mlsanity.com/paper/2608.12503/) (2026)

## Abstract (arXiv)

We show how to compute a relative-error low-rank approximation to any positive semidefinite (PSD) matrix in sublinear time, i.e., for any n × n PSD matrix A, in tilde O(n · poly(k/ε)) time we output a rank-k matrix B, in factored form, for which |A-B|F2 ≤ (1+ε)|A-Ak|F2, where Ak is the best rank-k approximation to A. When k and 1/ε are not too large compared to the sparsity of A, our algorithm does not need to read all entries of the matrix. Hence, we significantly improve upon previous nnz(A) time algorithms based on oblivious subspace embeddings, and bypass an nnz(A) time lower bound for general matrices (where nnz(A) denotes the number of non-zero entries in the matrix). We prove time lower bounds for low-rank approximation of PSD matrices, showing that our algorithm is close to optimal. Finally, we extend our techniques to give sublinear time algorithms for low-rank approximation of A in the (often stronger) spectral norm metric |A-B|22 and for ridge regression on PSD matrices.