# Solving Dense Linear Systems Faster Than via Preconditioning

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 38 of its 92 references that are in the map.
- First posted on arXiv 14 Dec 2023.

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

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [Pruning and Quantization for Deep Neural Network Acceleration: A Survey](https://mlsanity.com/paper/2101.09671/) (2021)
- [High-Dimensional Asymptotics of Prediction: Ridge Regression and Classification](https://mlsanity.com/paper/1507.03003/) (2015)
- [Solving Linear Programs in the Current Matrix Multiplication Time](https://mlsanity.com/paper/1810.07896/) (2018)
- [FALKON: An Optimal Large Scale Kernel Method](https://mlsanity.com/paper/1705.10958/) (2017)
- [Randomized Block Krylov Methods for Stronger and Faster Approximate Singular Value Decomposition](https://mlsanity.com/paper/1504.05477/) (2015)
- [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 Kernel Ridge Regression Using Sketching and Preconditioning](https://mlsanity.com/paper/1611.03220/) (2016)
- [Determinantal Point Processes in Randomized Numerical Linear Algebra](https://mlsanity.com/paper/2005.03185/) (2020)
- [Randomized Numerical Linear Algebra : A Perspective on the Field With an Eye to Software](https://mlsanity.com/paper/2302.11474/) (2023)
- [New Bounds for Matrix Multiplication: from Alpha to Omega](https://mlsanity.com/paper/2307.07970/) (2023)
- [Monte Carlo Markov Chain Algorithms for Sampling Strongly Rayleigh Distributions and Determinantal Point Processes](https://mlsanity.com/paper/1602.05242/) (2016)
- [Query Complexity of Least Absolute Deviation Regression via Robust Uniform Convergence](https://mlsanity.com/paper/2102.02322/) (2021)
- [Approximate Gaussian Elimination for Laplacians: Fast, Sparse, and Simple](https://mlsanity.com/paper/1605.02353/) (2016)
- [Fast Randomized Kernel Methods With Statistical Guarantees](https://mlsanity.com/paper/1411.0306/) (2014)
- [Exact sampling of determinantal point processes with sublinear time preprocessing](https://mlsanity.com/paper/1905.13476/) (2019)
- [Sharp Analysis of Sketch-and-Project Methods via a Connection to Randomized Singular Value Decomposition](https://mlsanity.com/paper/2208.09585/) (2022)
- [Bayesian experimental design using regularized determinantal point processes](https://mlsanity.com/paper/1906.04133/) (2019)
- [Stability of the Lanczos Method for Matrix Function Approximation](https://mlsanity.com/paper/1708.07788/) (2017)
- [Efficient Accelerated Coordinate Descent Methods and Faster Algorithms for Solving Linear Systems](https://mlsanity.com/paper/1305.1922/) (2013)
- [Fast determinantal point processes via distortion-free intermediate sampling](https://mlsanity.com/paper/1811.03717/) (2018)
- [Convergence Analysis of Block Coordinate Algorithms with Determinantal Sampling](https://mlsanity.com/paper/1910.11561/) (2019)
- [Optimal Embedding Dimension for Sparse Subspace Embeddings](https://mlsanity.com/paper/2311.10680/) (2023)
- [Solving Sparse Linear Systems Faster than Matrix Multiplication](https://mlsanity.com/paper/2007.10254/) (2020)
- [Minimax experimental design: Bridging the gap between statistical and worst-case approaches to least squares regression](https://mlsanity.com/paper/1902.00995/) (2019)

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

- [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)
- [Faster Linear Systems and Matrix Norm Approximation via Multi-level Sketched Preconditioning](https://mlsanity.com/paper/2405.05865/) (2024)
- [Distributed Least Squares in Small Space via Sketching and Bias Reduction](https://mlsanity.com/paper/2405.05343/) (2024)
- [Turbocharging Gaussian Process Inference with Approximate Sketch-and-Project](https://mlsanity.com/paper/2505.13723/) (2025)
- [TCS-BENCH: Benchmarking State-of-the-Art Generative AI Theoretical Computer Science Research Ability](https://mlsanity.com/paper/2608.09538/) (2026)
- [Worth Their Weight: Randomized and Regularized Block Kaczmarz Algorithms without Preprocessing](https://mlsanity.com/paper/2502.00882/) (2025)
- [A Sketch-and-Project Analysis of Subsampled Natural Gradient Algorithms](https://mlsanity.com/paper/2508.21022/) (2025)
- [Last-Iterate Convergence of Randomized Kaczmarz and SGD with Greedy Step Size](https://mlsanity.com/paper/2604.09909/) (2026)
- [Faster Low-Rank Approximation and Kernel Ridge Regression via the Block-Nystr"om Method](https://mlsanity.com/paper/2506.17556/) (2025)
- [HERTA: A High-Efficiency and Rigorous Training Algorithm for Unfolded Graph Neural Networks](https://mlsanity.com/paper/2403.18142/) (2024)
- [Perfect Parallelization in Mini-Batch SGD with Classical Momentum Acceleration](https://mlsanity.com/paper/2605.18609/) (2026)

## Abstract (arXiv)

We give a stochastic optimization algorithm that solves a dense n× n real-valued linear system Ax=b, returning tilde x such that |Atilde x-b|≤ ε|b| in time: tilde O((n2+nkω-1)log1/ε), where k is the number of singular values of A larger than O(1) times its smallest positive singular value, ω < 2.372 is the matrix multiplication exponent, and tilde O hides a poly-logarithmic in n factor. When k=O(n1-θ) (namely, A has a flat-tailed spectrum, e.g., due to noisy data or regularization), this improves on both the cost of solving the system directly, as well as on the cost of preconditioning an iterative method such as conjugate gradient. In particular, our algorithm has an tilde O(n2) runtime when k=O(n0.729). We further adapt this result to sparse positive semidefinite matrices and least squares regression. Our main algorithm can be viewed as a randomized block coordinate descent method, where the key challenge is simultaneously ensuring good convergence and fast per-iteration time. In our analysis, we use theory of majorization for elementary symmetric polynomials to establish a sharp convergence guarantee when coordinate blocks are sampled using a determinantal point process. We then use a Markov chain coupling argument to show that similar convergence can be attained with a cheaper sampling scheme, and accelerate the block coordinate descent update via matrix sketching.