# Approaching Optimality for Solving Dense Linear Systems with Low-Rank Structure

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 62 references that are in the map.
- First posted on arXiv 15 Jul 2025.

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

- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [Katyusha: The First Direct Acceleration of Stochastic Gradient Methods](https://mlsanity.com/paper/1603.05953/) (2016)
- [A Universal Catalyst for First-Order Optimization](https://mlsanity.com/paper/1506.02186/) (2015)
- [Faster Kernel Ridge Regression Using Sketching and Preconditioning](https://mlsanity.com/paper/1611.03220/) (2016)
- [Optimal approximate matrix product in terms of stable rank](https://mlsanity.com/paper/1507.02268/) (2015)
- [New Bounds for Matrix Multiplication: from Alpha to Omega](https://mlsanity.com/paper/2307.07970/) (2023)
- [Uniform Sampling for Matrix Approximation](https://mlsanity.com/paper/1408.5099/) (2014)
- [More Asymmetry Yields Faster Matrix Multiplication](https://mlsanity.com/paper/2404.16349/) (2024)
- [Even Faster Accelerated Coordinate Descent Using Non-Uniform Sampling](https://mlsanity.com/paper/1512.09103/) (2015)
- [Approximate Gaussian Elimination for Laplacians: Fast, Sparse, and Simple](https://mlsanity.com/paper/1605.02353/) (2016)
- [Un-regularizing: approximate proximal point and faster stochastic algorithms for empirical risk minimization](https://mlsanity.com/paper/1506.07512/) (2015)
- [Faster Eigenvector Computation via Shift-and-Invert Preconditioning](https://mlsanity.com/paper/1605.08754/) (2016)
- [Stability of the Lanczos Method for Matrix Function Approximation](https://mlsanity.com/paper/1708.07788/) (2017)
- [Solving Ridge Regression using Sketched Preconditioned SVRG](https://mlsanity.com/paper/1602.02350/) (2016)
- [Efficient Accelerated Coordinate Descent Methods and Faster Algorithms for Solving Linear Systems](https://mlsanity.com/paper/1305.1922/) (2013)
- [Optimal Embedding Dimension for Sparse Subspace Embeddings](https://mlsanity.com/paper/2311.10680/) (2023)
- [Almost-Linear-Time Algorithms for Markov Chains and New Spectral Primitives for Directed Graphs](https://mlsanity.com/paper/1611.00755/) (2016)
- [Ultrasparse Ultrasparsifiers and Faster Laplacian System Solvers](https://mlsanity.com/paper/2011.08806/) (2020)
- [Single Pass Spectral Sparsification in Dynamic Streams](https://mlsanity.com/paper/1407.1289/) (2014)
- [Sparsified Cholesky and Multigrid Solvers for Connection Laplacians](https://mlsanity.com/paper/1512.01892/) (2015)
- [Leverage Score Sampling for Faster Accelerated Regression and ERM](https://mlsanity.com/paper/1711.08426/) (2017)
- [Solving Directed Laplacian Systems in Nearly-Linear Time through Sparse LU Factorizations](https://mlsanity.com/paper/1811.10722/) (2018)
- [Fine-grained Analysis and Faster Algorithms for Iteratively Solving Linear Systems](https://mlsanity.com/paper/2405.05818/) (2024)
- [Randomized Kaczmarz Methods with Beyond-Krylov Convergence](https://mlsanity.com/paper/2501.11673/) (2025)
- [Principal Component Projection Without Principal Component Analysis](https://mlsanity.com/paper/1602.06872/) (2016)
- [Spectrum Approximation Beyond Fast Matrix Multiplication: Algorithms and Hardness](https://mlsanity.com/paper/1704.04163/) (2017)
- [Structured Semidefinite Programming for Recovering Structured Preconditioners](https://mlsanity.com/paper/2310.18265/) (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)
- [Sparsified Block Elimination for Directed Laplacians](https://mlsanity.com/paper/2111.10257/) (2021)

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

- [Accelerating Power Method with Fast Sketching for Stronger Low-Rank Approximation](https://mlsanity.com/paper/2605.09755/) (2026)
- [Fast, Parallel, Query-Efficient Binary Classification](https://mlsanity.com/paper/2607.04062/) (2026)

## Abstract (arXiv)

We provide new high-accuracy randomized algorithms for solving linear systems and regression problems that are well-conditioned except for k large singular values. For solving such d × d positive definite system our algorithms succeed whp. and run in time tilde O(d2 + kω). For solving such regression problems in a matrix A ∈ ℝn × d our methods succeed whp. and run in time tilde O(nnz(A) + d2 + kω) where ω is the matrix multiplication exponent and nnz(A) is the number of non-zeros in A. Our methods nearly-match a natural complexity limit under dense inputs for these problems and improve upon a trade-off in prior approaches that obtain running times of either tilde O(d2.065+kω) or tilde O(d2 + dkω-1) for d× d systems. Moreover, we show how to obtain these running times even under the weaker assumption that all but k of the singular values have a suitably bounded generalized mean. Consequently, we give the first nearly-linear time algorithm for computing a multiplicative approximation to the nuclear norm of an arbitrary dense matrix. Our algorithms are built on three general recursive preconditioning frameworks, where matrix sketching and low-rank update formulas are carefully tailored to the problems' structure.