Lune

SODA2025Top-tier venue

Faster Linear Systems and Matrix Norm Approximation via Multi-level Sketched Preconditioning

Michal Derezinski, Christopher Musco, Jiaming Yang

Abstract

We present a new class of preconditioned iterative methods for solving linear systems of the form Ax = b. Our methods are based on constructing a low-rank Nyström approximation to A using sparse random matrix sketching. This approximation is used to construct a preconditioner, which itself is inverted quickly using additional levels of random sketching and preconditioning.

We prove that the convergence of our methods depends on a natural average condition number of A, which improves as the rank of the Nyström approximation increases. Concretely, this allows us to obtain faster runtimes for a number of fundamental linear algebraic problems:

  1. We show how to solve any n×n linear system that is well-conditioned except for k outlying large singular values in Õ(n 2.065 + k ω ) time, improving on a recent result of [Dereziński, Yang, STOC 2024] for all k n 0.78 .

  2. We give the first Õ(n 2 + d λ ω ) time algorithm for solving a regularized linear system (A + λI)x = b, where A is positive semidefinite with effective dimension d λ = tr(A(A + λI) -1 ). This problem arises in applications like Gaussian process regression.

  3. We give faster algorithms for approximating Schatten p-norms and other matrix norms.

For example, for the Schatten 1-norm (nuclear norm), we give an algorithm that runs in Õ(n 2.11 ) time, improving on an Õ(n 2.18 ) method of [Musco et al., ITCS 2018].

All results are proven in the real RAM model of computation. Interestingly, previous state-ofthe-art algorithms for most of the problems above relied on stochastic iterative methods, like stochastic coordinate and gradient descent. Our work takes a completely different approach, instead leveraging tools from matrix sketching.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

1 top-tier paper has cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Approaching Optimality for Solving Dense Linear Systems with Low-Rank Structure cites New Bounds for Matrix Multiplication: from Alpha to Omega
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers1

  1. Approaching Optimality for Solving Dense Linear Systems with Low-Rank StructureMichal Derezinski, Aaron SidfordSODA 2026

Builds on9

  1. Kernel Methods Through the Roof: Handling Billions of Points EfficientlyGiacomo Meanti, Luigi Carratino, Lorenzo Rosasco, Alessandro RudiNeurIPS 2020 · 138 citations
  2. New Bounds for Matrix Multiplication: from Alpha to OmegaVirginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, Renfei ZhouSODA 2024 · 90 citations
  3. A Faster Interior Point Method for Semidefinite ProgrammingHaotian Jiang, Tarun Kathuria, Yin Tat Lee, Swati Padmanabhan et al.FOCS 2020 · 62 citations
  4. Solving Sparse Linear Systems Faster than Matrix MultiplicationRichard Peng, Santosh S. VempalaSODA 2021 · 34 citations
  5. Nearly Optimal Approximation of Matrix Functions by the Lanczos MethodNoah Amsel, Tyler Chen, Anne Greenbaum, Cameron Musco et al.NeurIPS 2024 · 13 citations

Related papers

  1. Low-rank approximation with 1/ε1/3 matrix-vector productsAinesh Bakshi, Kenneth L. Clarkson, David P. WoodruffSTOC 2022 · 5 citations
  2. Solving Dense Linear Systems Faster Than via PreconditioningMichal Derezinski, Jiaming YangSTOC 2024
  3. Optimal Randomized First-Order Methods for Least-Squares ProblemsJonathan Lacotte, Mert PilanciICML 2020 · 30 citations
  4. Near-optimal hierarchical matrix approximation from matrix-vector productsTyler Chen, Feyza Duman Keles, Diana Halikias, Cameron Musco et al.SODA 2025
  5. Sketching Algorithms and Lower Bounds for Ridge RegressionPraneeth Kacham, David P. WoodruffICML 2022 · 6 citations
Dusk over the sea between two cliffs drawn in fine vertical lines