The Time Complexity of Solving Dense Linear Systems with k Large Singular Values: Logarithmic Factors, Matrix-Multiplication Dependence, and Derandomization

The source paper (Dereziński and Yang, STOC 2024) posed the question: what is the time complexity of solving an $n\times n$ dense linear system $Ax=b$ whose matrix has at most $k$ singular values larger than a constant factor times its smallest positive singular value? It gave a randomized stochastic solver running in $\tilde O((n^2+nk^{\omega-1})\log(1/\epsilon))$ time, where $\omega<2.372$ is the matrix multiplication exponent and $\tilde O$ hides polylogarithmic factors. Follow-up work improved this to $\tilde O(n^{2.065}+k^\omega)$ via multi-level sketched preconditioning, proved a matching conditional lower bound $\Omega(n^2+k^\omega)$, and finally achieved $\tilde O(n^2\log(1/\epsilon))+O(k^\omega)$ under strictly weaker averaged-conditioning assumptions, resolving the headline question up to polylogarithmic factors. The exact complexity remains open: eliminating (or proving necessary) the polylogarithmic overhead in the $n^2$ term, determining whether the dependence on fast matrix multiplication (the $k^\omega$ term) is unconditionally necessary or can be avoided by algorithms that do not use such primitives, and removing the randomization.

Background

Solving a linear system $Ax=b$ for a dense $n\times n$ real matrix $A$ is a foundational algorithmic task. Direct methods such as Gaussian elimination take $O(n^3)$ arithmetic operations, and fast matrix multiplication reduces this to $O(n^\omega)$, where $\omega<2.372$ is the matrix multiplication exponent, i.e. the infimum of exponents $c$ such that two $n\times n$ matrices can be multiplied in $O(n^c)$ operations. Iterative methods such as conjugate gradient (CG) instead access $A$ only through matrix-vector products (each costing $O(n^2)$ for dense $A$), and their iteration count is governed by the singular values $\sigma_1\ge\dots\ge\sigma_n$ of $A$ — the square roots of the eigenvalues of $A^\top A$, measuring how much $A$ stretches different directions — most coarsely through the condition number $\kappa(A)=\sigma_1/\sigma_n$.

Many linear systems arising in machine learning, statistics, and optimization are well-conditioned except for a few large singular values: either because of explicit regularization (e.g. $A=B+\lambda I$ in ridge regression or kernel methods) or because the matrix is distorted by isotropic noise from measurement error, compression, or privacy enforcement. Call such a matrix $k$-well-conditioned if at most $k$ of its singular values exceed a constant multiple of its smallest positive singular value (a flat-tailed spectrum). CG exploits this structure: it converges in $k+O(\log(1/\epsilon))$ iterations on such inputs, but each iteration costs $O(n^2)$, giving $\tilde O(n^2 k)$ overall — better than $O(n^\omega)$ only for small $k$. The classical alternative is preconditioning: approximate the dominant rank-$k$ subspace, e.g. by randomized power iteration (Halko, Martinsson, and Tropp), and use it as a preconditioner; this costs $\tilde O(n^2k^{\omega-2})$ (refinable to $\tilde O(n^{\omega(1,1,\log_n k)})$ using rectangular matrix multiplication), again leaving a polynomial overhead over the input size $n^2$.

The source paper (Dereziński and Yang, STOC 2024) broke this trade-off with a stochastic approach: a randomized block Kaczmarz/coordinate-descent method (Kaczmarz-type methods solve $Ax=b$ by repeatedly projecting the current iterate onto the solution set of a single equation, or a block of equations) in which coordinate blocks are sampled from a determinantal point process (a $k$-DPP — a distribution over size-$k$ index subsets where the probability of a subset is proportional to the determinant of the corresponding $k\times k$ submatrix of a kernel matrix, which biases sampling toward high-leverage directions). They proved a sharp convergence rate via majorization inequalities for elementary symmetric polynomials, then showed via a Markov-chain coupling argument that the expensive $k$-DPP sampling can be replaced by uniform sampling after preprocessing with the randomized Hadamard transform (a fast randomized sign-flip transform that approximately equalizes the row leverage scores — a row's leverage score measures its influence within the matrix's row space), and accelerated each iteration with matrix sketching (random projections that compress a matrix while approximately preserving the relevant geometry). The result: an $\tilde O((n^2+nk^{\omega-1})\log(1/\epsilon))$-time solver returning $\tilde x$ with $\|A\tilde x-b\|\le\epsilon\|b\|$ with high probability — near-linear time $\tilde O(n^2)$ whenever $k=O(n^{1/(\omega-1)})\approx n^{0.729}$. The full runtime bound carries an averaged condition number factor $\bar\kappa_k$ (the root-mean-square of the tail singular-value ratios $\sigma_i/\sigma_r$ for $i>k$) squared, polylogarithmic factors such as $\log^3 n$ and $\log^{3\omega} n$, the restriction $k\ge\log n$, and a simplifying cap $\bar\kappa_k<m^4$ that the authors themselves describe as a loose condition adopted for ease of presentation.

This triggered a rapid line of work. Dereziński, Musco, and Yang (SODA 2025) gave a different algorithm — deterministic Lanczos iterations (Lanczos is a Krylov-subspace method: it orthonormalizes the sequence $b, Ab, A^2b, \dots$ to extract approximate spectral information) with a randomized multi-level sketched preconditioner built from a Nyström approximation (a symmetric low-rank approximation of a matrix constructed from a random sample of its columns) — running in $\tilde O(n^{2.065}+k^\omega)$ time, improving on the stochastic bound for $k\gtrsim n^{0.78}$, and proved a conditional lower bound: solving a $k$-well-conditioned $d\times d$ system to $1/\mathrm{poly}(n)$ accuracy requires $\Omega(d^2+k^\omega)$ time as long as solving an arbitrary $k\times k$ linear system requires $\Omega(k^\omega)$ time. They posed achieving $\tilde O(d^2+k^\omega)$ as the key open problem. Dereziński and Sidford (SODA 2026) resolved it: for general $A\in\mathbb{R}^{n\times d}$ whose $(k,p)$-averaged condition number — the generalized mean with exponent $p$ of the tail singular-value ratios $\sigma_i/\sigma_d$, $i>k$ — is $O(1)$ for any constant $p>1/2$, their recursive-preconditioning algorithm solves regression in $\tilde O((\mathrm{nnz}(A)+d^2)\log(1/\epsilon))+O(k^\omega)$ time ($\mathrm{nnz}(A)$ is the number of nonzero entries of $A$) with high probability, and for positive definite systems they relax the requirement to $p>1/4$. Since the flat-tailed ($k$-well-conditioned) case implies averaged conditioning for every $p$, this matches the conditional lower bound up to polylogarithmic factors and strictly weakens the conditioning assumptions of the STOC 2024 paper. In parallel, Dereziński, Epperly, and Meyer (COLT 2026) proved that in the matrix-vector access model, any randomized two-sided algorithm needs $\Omega(\kappa\log(1/\epsilon))$ matrix-vector products and any one-sided algorithm needs $n$ products even for perfectly conditioned systems — confirming that Krylov-type methods are optimal among matvec algorithms, so the improvements above fundamentally rely on non-matvec access such as sketching and block operations.

Problem Statement

Determine the time complexity of solving an $n\times n$ linear system $Ax=b$ — computing $\tilde x$ with $\|A\tilde x-b\|\le\epsilon\|b\|$ — when $A$ has at most $k$ singular values larger than a constant factor times its smallest positive singular value (the central question of the source paper, restated as Problem 1.1 in the SODA 2025 follow-up). The current state of knowledge is an upper bound of $\tilde O(n^2\log(1/\epsilon))+O(k^\omega)$ by a randomized algorithm (Dereziński–Sidford, SODA 2026), valid already under weaker averaged tail-conditioning assumptions, and a conditional lower bound of $\Omega(n^2+k^\omega)$ (Dereziński–Musco–Yang, SODA 2025), which assumes only that solving an arbitrary $k\times k$ linear system requires $\Omega(k^\omega)$ time. These bounds agree only up to polylogarithmic factors, and the lower bound is conditional; the exact complexity therefore remains open. Pinning it down reduces to the following three questions, each part of the same objective:

1. Logarithmic factors: can the polylogarithmic overhead in the $n^2$ term be eliminated, i.e. is there an $O(n^2\log(1/\epsilon))+O(k^\omega)$-time algorithm in the real RAM model (unit-cost exact arithmetic on real numbers) used by this literature, or can polylogarithmic factors be shown to be necessary for this problem class?

2. Matrix-multiplication dependence: is the $k^\omega$ term necessary? This can be resolved either by an algorithm for $k$-well-conditioned systems that replaces the $k^\omega$ term by $o(k^\omega)$ — e.g. $O(k^2\,\mathrm{polylog}\,k)$ — without using fast matrix multiplication primitives (by the block-diagonal reduction underlying the conditional lower bound, such an algorithm would yield a solver asymptotically faster than matrix multiplication for arbitrary $k\times k$ systems), or by an unconditional lower bound showing that super-quadratic time in $k$ — in particular $\Omega(k^\omega)$ under current bounds on $\omega$ — is required for this class.

3. Randomization: all known near-optimal algorithms are randomized. Is there a deterministic algorithm achieving comparable guarantees, or does derandomization provably incur additional time?

Each facet stands on its own: resolving any single one of them — by an algorithm, a proof, or a lower bound as specified — is a complete answer to that facet. Matching upper and lower bounds, up to constant factors, for the time complexity of the $k$-well-conditioned dense linear system problem in every regime of $k$ would settle the problem.

References

1. Michał Dereziński, Jiaming Yang. Solving Dense Linear Systems Faster Than via Preconditioning. STOC 2024. arXiv:2312.08893, DOI 10.48550/arXiv.2312.08893. https://arxiv.org/abs/2312.08893
2. Michał Dereziński, Christopher Musco, Jiaming Yang. Faster Linear Systems and Matrix Norm Approximation via Multi-level Sketched Preconditioning. SODA 2025, DOI 10.1137/1.9781611978322.62. arXiv:2405.05865, DOI 10.48550/arXiv.2405.05865. https://arxiv.org/abs/2405.05865
3. Michał Dereziński, Aaron Sidford. Approaching Optimality for Solving Dense Linear Systems with Low-Rank Structure. SODA 2026, DOI 10.1137/1.9781611978971.37. arXiv:2507.11724, DOI 10.48550/arXiv.2507.11724. https://arxiv.org/abs/2507.11724
4. Michał Dereziński, Daniel LeJeune, Deanna Needell, Elizaveta Rebrova. Fine-grained Analysis and Faster Algorithms for Iteratively Solving Linear Systems. Journal of Machine Learning Research 26(144):1-49, 2025. https://jmlr.org/papers/v26/24-1906.html. arXiv:2405.05818, DOI 10.48550/arXiv.2405.05818. https://arxiv.org/abs/2405.05818
5. Richard Peng, Santosh Vempala. Solving Sparse Linear Systems Faster than Matrix Multiplication. Journal of the ACM 72(6):40:1-40:72, 2025, DOI 10.1145/3767721. arXiv:2007.10254, DOI 10.48550/arXiv.2007.10254. https://arxiv.org/abs/2007.10254
6. Michał Dereziński, Ethan N. Epperly, Raphael A. Meyer. The matrix-vector complexity of Ax=b. COLT 2026. arXiv:2602.04842, DOI 10.48550/arXiv.2602.04842. https://arxiv.org/abs/2602.04842
7. Nathan Halko, Per-Gunnar Martinsson, Joel A. Tropp. Finding Structure with Randomness: Probabilistic Algorithms for Constructing Approximate Matrix Decompositions. SIAM Review 53(2):217-288, 2011, DOI 10.1137/090771806. arXiv:0909.4061, DOI 10.48550/arXiv.0909.4061. https://arxiv.org/abs/0909.4061
8. Noah Amsel, Yves Baumann, Paul Beckman, Peter Bürgisser, Chris Camaño, Tyler Chen, Edmond Chow, Anil Damle, Michał Dereziński, Mark Embree, Ethan N. Epperly, Robert Falgout, Mark Fornace, Anne Greenbaum, Chen Greif, Diana Halikias, Zhen Huang, Elias Jarlebring, Yiannis Koutis, Daniel Kressner, Rasmus Kyng, Jörg Liesen, Jackie Lok, Raphael A. Meyer, Yuji Nakatsukasa, Kate Pearce, Richard Peng, David Persson, Eliza Rebrova, Ryan Schneider, Rikhav Shah, Edgar Solomonik, Nikhil Srivastava, Alex Townsend, Robert J. Webber, Jess Williams. Linear Systems and Eigenvalue Problems: Open Questions from a Simons Workshop. 2026. arXiv:2602.05394, DOI 10.48550/arXiv.2602.05394. https://arxiv.org/abs/2602.05394