# Near-Optimal Algorithms for Linear Algebra in the Current Matrix Multiplication Time

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 39 references that are in the map.
- First posted on arXiv 16 Jul 2021.

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

- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [Solving Linear Programs in the Current Matrix Multiplication Time](https://mlsanity.com/paper/1810.07896/) (2018)
- [Training (Overparametrized) Neural Networks in Near-Linear Time](https://mlsanity.com/paper/2006.11648/) (2020)
- [A Refined Laser Method and Faster Matrix Multiplication](https://mlsanity.com/paper/2010.05846/) (2020)
- [A Faster Interior Point Method for Semidefinite Programming](https://mlsanity.com/paper/2009.10217/) (2020)
- [Dimensionality Reduction for k-Means Clustering and Low Rank Approximation](https://mlsanity.com/paper/1410.6801/) (2014)
- [Input Sparsity Time Low-Rank Approximation via Ridge Leverage Score Sampling](https://mlsanity.com/paper/1511.07263/) (2015)
- [Relative Error Tensor Low Rank Approximation](https://mlsanity.com/paper/1704.08246/) (2017)
- [Faster Dynamic Matrix Inverse for Faster LPs](https://mlsanity.com/paper/2004.07470/) (2020)
- [Optimal approximate matrix product in terms of stable rank](https://mlsanity.com/paper/1507.02268/) (2015)
- [Uniform Sampling for Matrix Approximation](https://mlsanity.com/paper/1408.5099/) (2014)
- [Learning Two Layer Rectified Neural Networks in Polynomial Time](https://mlsanity.com/paper/1811.01885/) (2018)
- [Optimal CUR Matrix Decompositions](https://mlsanity.com/paper/1405.7910/) (2014)
- [Toward a unified theory of sparse dimensionality reduction in Euclidean space](https://mlsanity.com/paper/1311.2542/) (2013)
- [Input Sparsity and Hardness for Robust Subspace Approximation](https://mlsanity.com/paper/1510.06073/) (2015)
- [Input-Sparsity Low Rank Approximation in Schatten Norm](https://mlsanity.com/paper/2004.12646/) (2020)
- [Tight Bounds for ℓp Oblivious Subspace Embeddings](https://mlsanity.com/paper/1801.04414/) (2018)
- [Projection-Cost-Preserving Sketches: Proof Strategies and Constructions](https://mlsanity.com/paper/2004.08434/) (2020)

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

- [Optimal Embedding Dimension for Sparse Subspace Embeddings](https://mlsanity.com/paper/2311.10680/) (2023)
- [Faster Linear Systems and Matrix Norm Approximation via Multi-level Sketched Preconditioning](https://mlsanity.com/paper/2405.05865/) (2024)
- [Optimal Oblivious Subspace Embeddings with Near-optimal Sparsity](https://mlsanity.com/paper/2411.08773/) (2024)
- [Distributed Least Squares in Small Space via Sketching and Bias Reduction](https://mlsanity.com/paper/2405.05343/) (2024)

## Abstract (arXiv)

In the numerical linear algebra community, it was suggested that to obtain nearly optimal bounds for various problems such as rank computation, finding a maximal linearly independent subset of columns (a basis), regression, or low-rank approximation, a natural way would be to resolve the main open question of Nelson and Nguyen (FOCS, 2013). This question is regarding the logarithmic factors in the sketching dimension of existing oblivious subspace embeddings that achieve constant-factor approximation. We show how to bypass this question using a refined sketching technique, and obtain optimal or nearly optimal bounds for these problems. A key technique we use is an explicit mapping of Indyk based on uncertainty principles and extractors, which after first applying known oblivious subspace embeddings, allows us to quickly spread out the mass of the vector so that sampling is now effective. We thereby avoid a logarithmic factor in the sketching dimension that is standard in bounds proven using the matrix Chernoff inequality. For the fundamental problems of rank computation and finding a basis, our algorithms improve Cheung, Kwok, and Lau (JACM, 2013), and are optimal to within a constant factor and a poly(log log(n))-factor, respectively. Further, for constant-factor regression and low-rank approximation we give the first optimal algorithms, for the current matrix multiplication exponent.