# Sample-Optimal Low-Rank Approximation of Distance Matrices

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Jun 2019.

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

- [Low-Rank Sinkhorn Factorization](https://mlsanity.com/paper/2103.04737/) (2021)
- [Linear-Time Gromov Wasserstein Distances using Low Rank Couplings and Costs](https://mlsanity.com/paper/2106.01128/) (2021)
- [Generalization Bounds for Data-Driven Numerical Linear Algebra](https://mlsanity.com/paper/2206.07886/) (2022)
- [Dynamic Tensor Product Regression](https://mlsanity.com/paper/2210.03961/) (2022)
- [Efficient Nearest Neighbor Search for Cross-Encoder Models using Matrix Factorization](https://mlsanity.com/paper/2210.12579/) (2022)
- [Hierarchical Refinement: Optimal Transport to Infinity and Beyond](https://mlsanity.com/paper/2503.03025/) (2025)
- [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)
- [Unbalanced Low-rank Optimal Transport Solvers](https://mlsanity.com/paper/2305.19727/) (2023)
- [Sublinear Time Approximation of Text Similarity Matrices](https://mlsanity.com/paper/2112.09631/) (2021)
- [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)
- [Invariance Measures for Neural Networks](https://mlsanity.com/paper/2310.17404/) (2023)
- [Adaptive Retrieval and Scalable Indexing for k-NN Search with Cross-Encoders](https://mlsanity.com/paper/2405.03651/) (2024)
- [Fast Length-Squared Sampling for Positive-Semidefinite Matrices](https://mlsanity.com/paper/2608.12503/) (2026)

## Abstract (arXiv)

A distance matrix A ∈ mathbb Rn × m represents all pairwise distances, Aij=d(xi,yj), between two point sets x1,...,xn and y1,...,ym in an arbitrary metric space (mathcal Z, d). Such matrices arise in various computational contexts such as learning image manifolds, handwriting recognition, and multi-dimensional unfolding. In this work we study algorithms for low-rank approximation of distance matrices. Recent work by Bakshi and Woodruff (NeurIPS 2018) showed it is possible to compute a rank-k approximation of a distance matrix in time O((n+m)1+γ) · poly(k,1/ε), where ε>0 is an error parameter and γ>0 is an arbitrarily small constant. Notably, their bound is sublinear in the matrix size, which is unachievable for general matrices. We present an algorithm that is both simpler and more efficient. It reads only O((n+m) k/ε) entries of the input matrix, and has a running time of O(n+m) · poly(k,1/ε). We complement the sample complexity of our algorithm with a matching lower bound on the number of entries that must be read by any algorithm. We provide experimental results to validate the approximation quality and running time of our algorithm.