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

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Nov 2022.

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

- [GradientCoin: A Peer-to-Peer Decentralized Large Language Models](https://mlsanity.com/paper/2308.10502/) (2023)
- [A Nearly-Optimal Bound for Fast Regression with ℓ_∞ Guarantee](https://mlsanity.com/paper/2302.00248/) (2023)
- [Optimal Embedding Dimension for Sparse Subspace Embeddings](https://mlsanity.com/paper/2311.10680/) (2023)
- [Optimal Oblivious Subspace Embeddings with Near-optimal Sparsity](https://mlsanity.com/paper/2411.08773/) (2024)
- [Beyond Averaging in John Ellipsoid Approximation: High-Accuracy Algorithms in the Leverage-Score Model](https://mlsanity.com/paper/2606.20082/) (2026)

## Abstract (arXiv)

We study fundamental problems in linear algebra, such as finding a maximal linearly independent subset of rows or columns (a basis), solving linear regression, or computing a subspace embedding. For these problems, we consider input matrices A∈ℝn× d with n > d. The input can be read in nnz(A) time, which denotes the number of nonzero entries of A. In this paper, we show that beyond the time required to read the input matrix, these fundamental linear algebra problems can be solved in dω time, i.e., where ω ≈ 2.37 is the current matrix-multiplication exponent. To do so, we introduce a constant-factor subspace embedding with the optimal m=O(d) number of rows, and which can be applied in time Oleft(fracnnz(A)αright) + d2 + αpoly(log d) for any trade-off parameter α>0, tightening a recent result by Chepurko et. al. [SODA 2022] that achieves an exp(poly(loglog n)) distortion with m=d·poly(loglog d) rows in Oleft(fracnnz(A)α+d2+α+o(1)right) time. Our subspace embedding uses a recently shown property of stacked Subsampled Randomized Hadamard Transforms (SRHT), which actually increase the input dimension, to "spread" the mass of an input vector among a large number of coordinates, followed by random sampling. To control the effects of random sampling, we use fast semidefinite programming to reweight the rows. We then use our constant-factor subspace embedding to give the first optimal runtime algorithms for finding a maximal linearly independent subset of columns, regression, and leverage score sampling. To do so, we also introduce a novel subroutine that iteratively grows a set of independent rows, which may be of independent interest.