Pith. sign in

REVIEW 2 major objections 4 minor 62 references

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

T0 review · 2 major / 4 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read New randomized algorithms solve dense k-well-conditioned linear systems and regression problems in nearly optimal time, nearly matching the Ω(d²+k^ω) lower bound and yielding the first near-linear nuclear norm approximation.

desk verdict Resolves the open problem from [18] with near-optimal Õ(d²+k^ω) solvers; the one load-bearing soft spot is Lemma 7's inferred AGD iteration count, which is likely correct but should be verified. read the letter →

arxiv 2507.11724 v1 pith:FUPZKWHP submitted 2025-07-15 cs.DS cs.NAmath.NAmath.OCstat.ML

Micha{l} Dereziński , Aaron Sidford This is my paper · ORCID
classification cs.DScs.NAmath.NAmath.OCstat.ML MSC 65F1068W2065F08
keywords linearsystemsleast-squaresregressionrecursivepreconditioninglow-rankstructureaveragedconditionnumbermatrixsketchingnuclearnormapproximationsubspaceembeddings
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper claims that linear systems and least-squares regression with a dense matrix whose spectrum is well behaved except for $k$ large singular values can be solved in nearly optimal time: $\tilde O((\mathrm{nnz}(A)+d^2)\log(1/\epsilon)) + O(k^\omega)$ for regression in $A\in\mathbb{R}^{n\times d}$, and $\tilde O(d^2\log(1/\epsilon)) + O(k^\omega)$ for positive-definite $d\times d$ systems. These bounds nearly match the $\Omega(d^2+k^\omega)$ lower bound the paper cites, resolving an open problem that had left a trade-off between $\tilde O(d^{2.065}+k^\omega)$ and $\tilde O(d^2+dk^{\omega-1})$ algorithms. The paper weakens the conditioning assumption to a new $(k,p)$-averaged condition number, requiring only $p>1/2$ for regression and $p>1/4$ for PD systems, and as a corollary obtains the first nearly-linear-time multiplicative approximation of the nuclear norm of an arbitrary dense matrix.

What carries the argument

The load-bearing mechanism is recursive preconditioning: instead of approximating $A^\top A$ by one low-rank sketch, the algorithm builds a chain of matrices $A_t = S_t A$ with decreasing dimensions and increasing regularization $\nu_t$, each a constant-factor spectral approximation of the previous one. Solving the first system requires only $\tilde O(\sqrt{\beta})$ solves at the next level, while the cost of applying each matrix shrinks faster than the recursion branches, so the total time is dominated by the top level. Three frameworks are developed: a regularized preconditioning chain, an alternating primal-dual chain that sketches both dimensions, and an implicit dual chain based on a regularized Nyström approximation (a low-rank approximation of a PD matrix of the form $CW^{-1}C^\top$) for PD matrices; the Woodbury identity converts dual solves into smaller primal solves, and sparse subspace embeddings provide the sketches.

What would settle it

Run the preconditioned accelerated gradient method from Lemma 7 on a concrete pair $M,N$ with $M \preceq N \preceq \kappa M$ for a moderately large $\kappa$ and check whether the claimed $\lceil 4\sqrt{\kappa}\log(2/\epsilon)\rceil$ iterations indeed output an $\epsilon$-solution; because every recursive level multiplies this count, a failure would invalidate the main runtime theorems.

Watch

Extended reading notes

Core claim

The central claim, stated as Theorems 3 and 4, is that the conditional lower bound $\Omega(d^2+k^\omega)$ is nearly achievable: any $(k,p)$-well-conditioned regression problem with constant $p>1/2$ can be solved with high probability in $\tilde O((\mathrm{nnz}(A)+d^2)\log(1/\epsilon))+O(k^\omega)$ time, and any $(k,p)$-well-conditioned PD system with constant $p>1/4$ in $\tilde O(d^2\log(1/\epsilon))+O(k^\omega)$ time. Along the way the paper introduces the $(k,p)$-averaged condition number $\bar\kappa_{k,p}$, the generalized mean of the tail singular values, and shows that this weaker notion, rather than the usual $k$-well-conditioned assumption, is the right measure of hardness for these problems. The nuclear norm corollary (Theorem 5) follows by showing that Schatten $p$-norm approximation reduces to solving $(0,p)$-well-conditioned systems.

Load-bearing premise

Everything rests on an explicit iteration count for accelerated gradient descent that the paper infers from a cited theorem that did not state the count; every recursive level multiplies this count, so if the inferred count is too small, the claimed runtimes would need to be revisited.

Editorial extensions

If this is right

  • If Theorems 3 and 4 are correct, the complexity of dense $k$-well-conditioned linear algebra is essentially settled: no algorithm can beat $\Omega(d^2+k^\omega)$ under the stated lower bound, and these algorithms attain it up to polylogarithmic factors and matrix-multiplication constants.
  • The new algorithms remove the previous trade-off: they dominate both the $\tilde O(d^{2.065}+k^\omega)$ sketched-preconditioning result and the $\tilde O(d^2+dk^{\omega-1})$ block-Kaczmarz result across the relevant range of $k$.
  • Because the conditioning threshold is $p>1/2$ for regression and $p>1/4$ for PD systems, the methods work on matrices where tail singular values are large on average, such as individual ratios as large as $O(d^2)$, a regime where prior running times would degrade substantially.
  • The nuclear norm algorithm implies that computing a $(1\pm\epsilon)$ approximation of $\|A\|_*$ for dense $A$ takes $\tilde O((\mathrm{nnz}(A)+d^2)\mathrm{poly}(1/\epsilon))$ time, with no fast matrix multiplication needed.
  • The same reduction gives the first nearly-linear-time Schatten $p$-norm approximations for all $p\in(1/2,2)$, and the new best known time complexities for $p\in(0,1/2]$.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Editorial inference: The recursive chaining template looks portable: any family of matrices with a fast sketching oracle and a Woodbury-compatible low-rank update could inherit similar runtimes, for example regularized kernel matrices or shifted systems, though the paper does not make this claim.
  • Editorial inference: The thresholds $p=1/2$ for regression and $p=1/4$ for PD systems are natural breaking points; a testable question is whether these are genuinely the lowest exponents achievable by any recursive scheme, or whether a different chain can reach $p=1/2$ and $p=1/4$ for both settings.
  • Editorial inference: The near-linear nuclear norm result may strengthen practical trace-estimation heuristics, since a dense matrix's nuclear norm could be approximated without invoking fast matrix multiplication, potentially changing preprocessing choices in low-rank recovery; this is an extrapolation beyond the paper's explicit guarantees.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 4 minor

Summary. The paper presents randomized algorithms for high-accuracy solving of dense linear systems and least-squares regression under averaged low-rank conditioning assumptions. The main technical contribution is a family of recursive preconditioning frameworks that combine sparse subspace embeddings, Woodbury-type reductions, and preconditioned accelerated gradient descent. For a d x d positive definite system that is (k,p)-well-conditioned with p>1/4, the paper claims an O~(d^2 log(1/epsilon)) + O(k^omega) solver; for regression with A in R^{n x d} that is (k,p)-well-conditioned with p>1/2, it claims O~((nnz(A)+d^2)log(1/epsilon)) + O(k^omega). These bounds nearly match the conditional lower bound Omega(d^2+k^omega) from prior work. The paper also derives a nearly-linear-time multiplicative approximation algorithm for the nuclear norm of a dense matrix. The analysis is carried out in the real-RAM model with exact arithmetic, as stated in Section 3.

Significance. If the main theorems hold as stated, this is a substantial advance: it resolves the open problem posed in [18] for k-well-conditioned systems, improves the averaged-conditioning thresholds from p>=2 to p>1/2 for regression and from p>=1 to p>1/4 for PD systems, and gives the first nearly-linear-time dense nuclear norm approximation. The paper is written with unusually detailed proofs: the recursive preconditioning lemmas (Lemmas 17, 19, 28, 40) are cleanly separated from the sketching tools, and the main runtime claims are derived explicitly from these lemmas. The applications to Schatten norm approximation are a natural and valuable byproduct. The main caveats are the unverified iteration count in Lemma 7 and an apparent unstated condition-number assumption in the headline theorem statements; both are fixable and do not, on the face of the paper, indicate a fundamental flaw in the algorithmic framework.

major comments (2)
  1. [Theorems 1, 3, 4; Sections 4.3, 5.3, 6.3] The main theorem statements drop all dependence on the condition number kappa(A) or kappa(M), but the proofs only establish runtimes with explicit polylog(d*kappa) factors. Specifically, Theorem 29 bounds the solver by O~(d^2 * min_eta ... log^{3+8/eta}(d*kappa(A))) and the proof in Section 5.3 grid-searches over O(log^3(d*kappa(A))) configurations; Theorem 41 and the proof in Section 6.3 have the analogous log^{9/2+6/eta}(d*kappa(M)) factor and grid search. Since O~ is defined in Section 3 as hiding only polylog(n+d), the stated runtimes in Theorems 1, 3, and 4 (and the abstract) follow only if kappa is assumed polynomially bounded in n and d. The introduction explicitly limits the polynomial-kappa assumption to Sections 1 and 2, so it does not cover these theorems. Please either add this assumption to the theorem statements or include the log-kappa factors in the claimed bounds.
  2. [Lemma 7 and Footnote 1] Lemma 7 is the sole source of the preconditioned-AGD iteration count ceil(4*sqrt(kappa)*log(2/epsilon)) and is cited from [32, Theorem 4.4]. The footnote concedes that the cited theorem does not state an explicit count and asserts that it follows from the proof and associated pseudocode. Since Lemmas 17, 19, 28, and 40 (and hence Theorems 1, 3, 4, 29, and 41) multiply this count across T = O(log d) recursion levels, this is load-bearing. I request a self-contained proof of Lemma 7, or an exact citation to the equation or pseudocode line in [32] where the count and the required inner-solver accuracy appear. If the correct count is C*sqrt(kappa)*log(1/epsilon) for a universal constant C, no asymptotic claim changes; the concern is an unstated additional dependence on the inner-solver accuracy or on kappa that could accumulate through the recursion.
minor comments (4)
  1. [Section 4.4, proof of Theorem 21] The displayed line 'R_t * max{nnz(A_{t-1}), nnz(A_t), n_t^2} = O(sqrt(Sigma_{k_t}(A)/sigma_d(A)^2) exp(alpha t))' omits the factor d*k_{t-1} that is needed to match the theorem statement (11); the final bound is correct only after restoring this factor.
  2. [Sections 5.3 and 6.3] When Lemma 23 is invoked with p=2, the displayed exponents such as (1/2)(2^2-1) and 3/2 correspond to c_p = 3/2 rather than the value c_p = 1 + 1/(2p) = 5/4 defined in Lemma 23. The constants used in the proofs are larger than those the lemma yields, so the stated upper bounds remain valid, but the derivation should be aligned with the lemma statement.
  3. [Section 3, Numerical Precision] The exact real-RAM assumption is stated transparently, and the authors point to relevant stability literature. For completeness, a brief discussion of the expected bit-complexity or of which parts of the analysis would need to change under finite-precision arithmetic would help readers assess the practical import of the results.
  4. [Section 5.3, proof of Theorem 29] The proof does not explicitly handle the boundary case k >= d/2, where T = ceil(sqrt(log(d/(2k))/alpha)) is zero or undefined; a sentence covering this case (e.g., by direct inversion in O(k^omega) time) would make the proof complete for all k in [d].

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the recursive preconditioning frameworks reduce to smaller systems and bottom out in direct solves, with no step equivalent to its own inputs.

full rationale

The derivation is self-contained. Theorems 3 and 4 are obtained by composing standard preconditioned accelerated gradient descent (Lemma 7), recursive preconditioning reductions (Lemmas 17, 19, 28, 40), sketching and subspace-embedding guarantees (Lemmas 11-13 and 26), and Woodbury-based direct bottom-level solvers (Lemmas 14-15). Each recursive level solves a smaller regularized system, and the runtime is summed over levels, so the claimed bounds do not assume the target runtime. The conditioning parameters are either given as inputs, found by grid search, or verified by the inexact power-method tests in Sections 5.4 and 6.4; they are not fitted to the final error in a way that forces the conclusion. The conditional lower bound of [18] is used only as a comparison benchmark and not as a load-bearing step in the algorithmic derivation. The one caveat worth flagging is Lemma 7: the explicit iteration count floor(4*sqrt(kappa)*log(2/epsilon)) is inferred from Theorem 4.4 of [32] and is load-bearing for every recursive runtime bound. However, this is an unverified detail of an external published result, not a reduction of the paper's claims to their own inputs; if the constant or inner-solver accuracy condition were wrong, the main theorems would need revision, but that is a correctness risk rather than circularity.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The central claims rest on standard mathematical tools and one domain assumption (exact arithmetic). No new entities are introduced; the (k,p)-averaged condition number is a new definition, not a physical or algorithmic entity. The free-parameter list is empty because the constants in the algorithms are fixed analysis constants, and hyper-parameters are found by provable grid search rather than fitted to data.

assumptions (5)
  • domain assumption Real-RAM model with exact arithmetic (Section 3, Numerical Precision).
    The stated runtimes assume exact arithmetic; the authors note that approximate arithmetic variants are left open. If finite precision breaks the low-rank approximations, the runtime bounds may not transfer.
  • standard math Sparse subspace embedding OSE guarantee (Lemma 11, citing [6]).
    The recursive chains rely on the existence of sparse embeddings with the stated sketch size and OSE moments; this is a cited external result by the authors' group.
  • standard math Preconditioned AGD iteration count (Lemma 7, adapted from Theorem 4.4 of [32]).
    The paper infers an explicit iteration count of 4√κ log(2/ε) from the proof of [32], which did not state it explicitly; the recursion runtimes depend on this count.
  • standard math Power method spectral norm estimation with error (Lemma 32 from [37]).
    Used in spectral approximation testing (Sections 5.4 and 6.4).
  • standard math Woodbury matrix identity (Lemma 14).
    Used throughout for low-rank inversion.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Approaching Optimality for Solving Dense Linear Systems with Low-Rank Structure." pith.science (2026). https://pith.science/paper/FUPZKWHP

@misc{pith2026250711724,
  author       = {Pith},
  title        = {Pith review of: Approaching Optimality for Solving Dense Linear Systems with Low-Rank Structure},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/FUPZKWHP}},
  note         = {Machine review of arXiv:2507.11724}
}
abstract

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 \times d$ positive definite system our algorithms succeed whp. and run in time $\tilde O(d^2 + k^\omega)$. For solving such regression problems in a matrix $\mathbf{A} \in \mathbb{R}^{n \times d}$ our methods succeed whp. and run in time $\tilde O(\mathrm{nnz}(\mathbf{A}) + d^2 + k^\omega)$ where $\omega$ is the matrix multiplication exponent and $\mathrm{nnz}(\mathbf{A})$ is the number of non-zeros in $\mathbf{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(d^{2.065}+k^\omega)$ or $\tilde O(d^2 + dk^{\omega-1})$ for $d\times 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.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

62 extracted references · 59 canonical work pages

  1. [18]

    Faster linear systems and matrix norm approximation via multi-level sketched preconditioning.ACM-SIAM Symposium on Discrete Algorithms (SODA), 2025

    Micha l Derezi´ nski, Christopher Musco, and Jiaming Yang. Faster linear systems and matrix norm approximation via multi-level sketched preconditioning.ACM-SIAM Symposium on Discrete Algorithms (SODA), 2025

    work page 2025

  2. [32]

    Ultrasparse ultrasparsifiers and faster laplacian system solvers

    Arun Jambulapati and Aaron Sidford. Ultrasparse ultrasparsifiers and faster laplacian system solvers. ACM Trans. Algorithms, February 2024

    work page 2024

  3. [1]

    Leverage score sampling for faster accelerated regression and erm

    Naman Agarwal, Sham Kakade, Rahul Kidambi, Yin-Tat Lee, Praneeth Netrapalli, and Aaron Sidford. Leverage score sampling for faster accelerated regression and erm. In Algorithmic Learning Theory , pages 22–47. PMLR, 2020

    work page 2020

  4. [2]

    Katyusha: The first direct acceleration of stochastic gradient methods

    Zeyuan Allen-Zhu. Katyusha: The first direct acceleration of stochastic gradient methods. Journal of Machine Learning Research, 18(221):1–51, 2018

    work page 2018

  5. [3]

    More asymmetry yields faster matrix multiplication

    Josh Alman, Ran Duan, Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, and Renfei Zhou. More asymmetry yields faster matrix multiplication. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 2005–2039. SIAM, 2025

    work page 2025

  6. [4]

    Faster kernel ridge regression using sketching and preconditioning

    Haim Avron, Kenneth L Clarkson, and David P Woodruff. Faster kernel ridge regression using sketching and preconditioning. SIAM Journal on Matrix Analysis and Applications , 38(4):1116–1138, 2017

    work page 2017

  7. [5]

    On the rate of convergence of the preconditioned conjugate gradient method

    Owe Axelsson and Gunhild Lindskog. On the rate of convergence of the preconditioned conjugate gradient method. Numerische Mathematik , 48:499–523, 1986

    work page 1986

  8. [6]

    Optimal oblivious subspace embeddings with near-optimal sparsity

    Shabarish Chenakkod, Micha l Derezi´ nski, and Xiaoyu Dong. Optimal oblivious subspace embeddings with near-optimal sparsity. In 52nd International Colloquium on Automata, Languages, and Program- ming (ICALP 2025) , 2024

    work page 2025

Show all 62 references
  1. [7]

    Optimal embedding dimension for sparse subspace embeddings

    Shabarish Chenakkod, Micha l Derezi´ nski, Xiaoyu Dong, and Mark Rudelson. Optimal embedding dimension for sparse subspace embeddings. Symposium on Theory of Computing (STOC) , 2024

    2024

  2. [8]

    Clarkson and David P

    Kenneth L. Clarkson and David P. Woodruff. Low-rank approximation and regression in input sparsity time. J. ACM, 63(6):54:1–54:45, January 2017

    2017

  3. [9]

    Nearly tight oblivious subspace embeddings by trace inequalities

    Michael B Cohen. Nearly tight oblivious subspace embeddings by trace inequalities. In Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms , pages 278–287. SIAM, 2016. 34

    2016

  4. [10]

    Solving directed laplacian systems in nearly-linear time through sparse lu factorizations

    Michael B Cohen, Jonathan Kelner, Rasmus Kyng, John Peebles, Richard Peng, Anup B Rao, and Aaron Sidford. Solving directed laplacian systems in nearly-linear time through sparse lu factorizations. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS) , p...

    2018

  5. [11]

    Cohen, Jonathan A

    Michael B. Cohen, Jonathan A. Kelner, John Peebles, Richard Peng, Anup B. Rao, Aaron Sidford, and Adrian Vladu. Almost-linear-time algorithms for markov chains and new spectral primitives for directed graphs. In 2017 Proceedings of the 49th Annual ACM SIGACT Symposium on Theor...

    2017

  6. [12]

    Cohen, Rasmus Kyng, Gary L

    Michael B. Cohen, Rasmus Kyng, Gary L. Miller, Jakub W. Pachocki, Richard Peng, Anup B. Rao, and Shen Chen Xu. Solving SDD linear systems in nearly m log1/2 n time. In Symposium on Theory of Computing, STOC 2014 , pages 343–352. ACM, 2014

    2014

  7. [13]

    Cohen, Yin Tat Lee, Cameron Musco, Christopher Musco, Richard Peng, and Aaron Sidford

    Michael B. Cohen, Yin Tat Lee, Cameron Musco, Christopher Musco, Richard Peng, and Aaron Sidford. Uniform sampling for matrix approximation. In Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, ITCS 2015 , pages 181–190. ACM, 2015

    2015

  8. [14]

    Optimal approximate matrix product in terms of stable rank

    Michael B Cohen, Jelani Nelson, and David P Woodruff. Optimal approximate matrix product in terms of stable rank. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Schloss-Dagstuhl-Leibniz Zentrum f¨ ur Informatik, 2016

    2016

  9. [15]

    Matrix multiplication via arithmetic progressions

    Don Coppersmith and Shmuel Winograd. Matrix multiplication via arithmetic progressions. In Pro- ceedings of the nineteenth annual ACM symposium on Theory of computing , pages 1–6, 1987

    1987

  10. [16]

    Fast linear algebra is stable

    James Demmel, Ioana Dumitriu, and Olga Holtz. Fast linear algebra is stable. Numerische Mathematik, 108(1):59–91, 2007

    2007

  11. [17]

    Fine-grained analysis and faster algorithms for iteratively solving linear systems

    Micha l Derezi´ nski, Daniel LeJeune, Deanna Needell, and Elizaveta Rebrova. Fine-grained analysis and faster algorithms for iteratively solving linear systems. arXiv preprint arXiv:2405.05818 , 2024

    2024 arXiv

  12. [19]

    Randomized kaczmarz methods with beyond-krylov convergence

    Micha l Derezi´ nski, Deanna Needell, Elizaveta Rebrova, and Jiaming Yang. Randomized kaczmarz methods with beyond-krylov convergence. arXiv preprint arXiv:2501.11673 , 2025

    2025 arXiv

  13. [20]

    Solving linear systems faster than via preconditioning

    Micha l Derezi´ nski and Jiaming Yang. Solving linear systems faster than via preconditioning. In Pro- ceedings of the Symposium on Theory of Computing (STOC) , 2024

    2024

  14. [21]

    Randomized Nystrom preconditioning

    Zachary Frangella, Joel A Tropp, and Madeleine Udell. Randomized Nystrom preconditioning. arXiv preprint arXiv:2110.02820, 2021

    2021 arXiv

  15. [22]

    Un-regularizing: approximate proximal point and faster stochastic algorithms for empirical risk minimization

    Roy Frostig, Rong Ge, Sham Kakade, and Aaron Sidford. Un-regularizing: approximate proximal point and faster stochastic algorithms for empirical risk minimization. In International Conference on Machine Learning, pages 2540–2548. PMLR, 2015

    2015

  16. [23]

    Principal component projection without principal component analysis

    Roy Frostig, Cameron Musco, Christopher Musco, and Aaron Sidford. Principal component projection without principal component analysis. In International Conference on Machine Learning , pages 2349–

  17. [24]

    Faster eigenvector computation via shift-and-invert preconditioning

    Dan Garber, Elad Hazan, Chi Jin, Cameron Musco, Praneeth Netrapalli, and Aaron Sidford. Faster eigenvector computation via shift-and-invert preconditioning. In International Conference on Machine Learning, pages 2626–2634. PMLR, 2016

    2016

  18. [25]

    Matrix computations

    Gene H Golub and Charles F Van Loan. Matrix computations. JHU press, 2013. 35

    2013

  19. [26]

    Chebyshev semi-iterative methods, successive overrelaxation iterative methods, and second order richardson iterative methods

    Gene H Golub and Richard S Varga. Chebyshev semi-iterative methods, successive overrelaxation iterative methods, and second order richardson iterative methods. Numerische Mathematik , 3(1):157– 168, 1961

    1961

  20. [27]

    Solving ridge regression using sketched preconditioned svrg

    Alon Gonen, Francesco Orabona, and Shai Shalev-Shwartz. Solving ridge regression using sketched preconditioned svrg. In International conference on machine learning , pages 1397–1405. PMLR, 2016

    2016

  21. [28]

    Behavior of slightly perturbed lanczos and conjugate-gradient recurrences

    Anne Greenbaum. Behavior of slightly perturbed lanczos and conjugate-gradient recurrences. Linear Algebra and its Applications , 113:7–63, 1989

    1989

  22. [29]

    Methods of conjugate gradients for solving linear systems, volume 49

    Magnus Rudolph Hestenes and Eduard Stiefel. Methods of conjugate gradients for solving linear systems, volume 49. NBS Washington, DC, 1952

    1952

  23. [30]

    Gaussian elimination

    Nicholas J Higham. Gaussian elimination. Wiley Interdisciplinary Reviews: Computational Statistics , 3(3):230–238, 2011

    2011

  24. [31]

    Structured semidefinite programming for recovering structured preconditioners

    Arun Jambulapati, Jerry Li, Christopher Musco, Kirankumar Shiragur, Aaron Sidford, and Kevin Tian. Structured semidefinite programming for recovering structured preconditioners. In Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Pr...

    2023

  25. [33]

    Accelerating stochastic gradient descent using predictive variance reduc- tion

    Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduc- tion. Advances in neural information processing systems , 26, 2013

    2013

  26. [34]

    Single pass spectral sparsification in dynamic streams

    Michael Kapralov, Yin Tat Lee, Cameron Musco, Christopher Musco, and Aaron Sidford. Single pass spectral sparsification in dynamic streams. SIAM Journal of Computing , 46(1):456–477, 2017

    2017

  27. [35]

    Miller, and Richard Peng

    Ioannis Koutis, Gary L. Miller, and Richard Peng. Approaching optimality for solving SDD linear systems. In 2010 IEEE 51th Annual Symposium on Foundations of Computer Science, FOCS , pages 235–244. IEEE Computer Society, 2010

    2010

  28. [36]

    Miller, and Richard Peng

    Ioannis Koutis, Gary L. Miller, and Richard Peng. A nearly-m log n time solver for SDD linear systems. In 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS , pages 590–598. IEEE Computer Society, 2011

    2011

  29. [37]

    Estimating the largest eigenvalue by the power and lanczos algorithms with a random start

    Jacek Kuczy´ nski and Henryk Wo´ zniakowski. Estimating the largest eigenvalue by the power and lanczos algorithms with a random start. SIAM journal on matrix analysis and applications , 13(4):1094–1122, 1992

    1992

  30. [38]

    Sparsified cholesky and multigrid solvers for connection laplacians

    Rasmus Kyng, Yin Tat Lee, Richard Peng, Sushant Sachdeva, and Daniel A Spielman. Sparsified cholesky and multigrid solvers for connection laplacians. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing , pages 842–850, 2016

    2016

  31. [39]

    Approximate gaussian elimination for laplacians-fast, sparse, and simple

    Rasmus Kyng and Sushant Sachdeva. Approximate gaussian elimination for laplacians-fast, sparse, and simple. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS) , pages 573–582. IEEE, 2016

    2016

  32. [40]

    Faster algorithms for rectangular matrix multiplication

    Francois Le Gall. Faster algorithms for rectangular matrix multiplication. In 2012 IEEE 53rd annual symposium on foundations of computer science , pages 514–523. IEEE, 2012

    2012

  33. [41]

    Efficient accelerated coordinate descent methods and faster algorithms for solving linear systems

    Yin Tat Lee and Aaron Sidford. Efficient accelerated coordinate descent methods and faster algorithms for solving linear systems. In 2013 ieee 54th annual symposium on foundations of computer science , pages 147–156. IEEE, 2013. 36

    2013

  34. [42]

    Randomized methods for linear constraints: convergence rates and conditioning

    Dennis Leventhal and Adrian S Lewis. Randomized methods for linear constraints: convergence rates and conditioning. Mathematics of Operations Research, 35(3):641–654, 2010

    2010

  35. [43]

    Miller, and Richard Peng

    Mu Li, Gary L. Miller, and Richard Peng. Iterative row sampling. 2013 IEEE 54th Annual Symposium on Foundations of Computer Science , 00:127–136, 2014

    2013

  36. [44]

    A universal catalyst for first-order optimization

    Hongzhou Lin, Julien Mairal, and Zaid Harchaoui. A universal catalyst for first-order optimization. Advances in neural information processing systems , 28, 2015

    2015

  37. [45]

    Stability of the lanczos method for matrix function approximation

    Cameron Musco, Christopher Musco, and Aaron Sidford. Stability of the lanczos method for matrix function approximation. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Dis- crete Algorithms, pages 1605–1624. SIAM, 2018

    2018

  38. [46]

    Spec- trum approximation beyond fast matrix multiplication: Algorithms and hardness

    Cameron Musco, Praneeth Netrapalli, Aaron Sidford, Shashanka Ubaru, and David P Woodruff. Spec- trum approximation beyond fast matrix multiplication: Algorithms and hardness. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Schloss-Dagstuhl-Leibniz Ze...

    2018

  39. [47]

    Nguyˆ en

    Jelani Nelson and Huy L. Nguyˆ en. OSNAP: Faster numerical linear algebra algorithms via sparser subspace embeddings. In Proceedings of the Symposium on Foundations of Computer Science , FOCS ’13, pages 117–126, 2013

    2013

  40. [48]

    Nesterov

    Yurii E. Nesterov. Efficiency of coordinate descent methods on huge-scale optimization problems. SIAM Journal of Optimization , 22(2):341–362, 2012

    2012

  41. [49]

    Nesterov and Sebastian U

    Yurii E. Nesterov and Sebastian U. Stich. Efficiency of the accelerated coordinate descent method on structured optimization problems. SIAM Journal of Optimization , 27(1):110–123, 2017

    2017

  42. [50]

    Algorithm Design Using Spectral Graph Theory

    Richard Peng. Algorithm Design Using Spectral Graph Theory. PhD thesis, Carnegie Mellon University, USA, 2013

    2013

  43. [51]

    Sparsified block elimination for directed laplacians

    Richard Peng and Zhuoqing Song. Sparsified block elimination for directed laplacians. In STOC ’22: 54th Annual ACM SIGACT Symposium on Theory of Computing , pages 557–567. ACM, 2022

    2022

  44. [52]

    A fast randomized algorithm for overdetermined linear least-squares regression

    Vladimir Rokhlin and Mark Tygert. A fast randomized algorithm for overdetermined linear least-squares regression. Proceedings of the National Academy of Sciences , 105(36):13212–13217, 2008

    2008

  45. [53]

    Improved approximation algorithms for large matrices via random projections

    Tamas Sarlos. Improved approximation algorithms for large matrices via random projections. In Pro- ceedings of the Symposium on Foundations of Computer Science , FOCS ’06, pages 143–152, 2006

    2006

  46. [54]

    Spielman and Shang-Hua Teng

    Daniel A. Spielman and Shang-Hua Teng. Nearly linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems. SIAM Journal on Matrix Analysis and Applications , 35(3):835–885, 2014

    2014

  47. [55]

    A note on preconditioning by low-stretch spanning trees

    Daniel A Spielman and Jaeoh Woo. A note on preconditioning by low-stretch spanning trees. arXiv preprint arXiv:0903.2816, 2009

    2009 arXiv

  48. [56]

    Gaussian elimination is not optimal

    Volker Strassen. Gaussian elimination is not optimal. Numerische Mathematik , 13(4):354–356, Aug 1969

    1969

  49. [57]

    A randomized Kaczmarz algorithm with exponential conver- gence

    Thomas Strohmer and Roman Vershynin. A randomized Kaczmarz algorithm with exponential conver- gence. Journal of Fourier Analysis and Applications , 15(2):262–278, 2009

    2009

  50. [58]

    Christopher K. I. Williams and Matthias Seeger. Using the Nystr¨ om method to speed up kernel ma- chines. In Advances in Neural Information Processing Systems 13 , pages 682–688. 2001

    2001

  51. [59]

    Multiplying matrices faster than coppersmith-winograd

    Virginia Vassilevska Williams. Multiplying matrices faster than coppersmith-winograd. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing , pages 887–898, 2012. 37

    2012

  52. [60]

    New bounds for matrix multiplication: from alpha to omega

    Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, and Renfei Zhou. New bounds for matrix multiplication: from alpha to omega. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 3792–3835, 2024

    2024

  53. [61]

    Sketching as a tool for numerical linear algebra

    David P Woodruff. Sketching as a tool for numerical linear algebra. Foundations and Trends ® in Theoretical Computer Science, 10(1–2):1–157, 2014

    2014

  54. [62]

    Even faster accelerated coordinate descent using non-uniform sampling

    Zeyuan Allen Zhu, Zheng Qu, Peter Richt´ arik, and Yang Yuan. Even faster accelerated coordinate descent using non-uniform sampling. In Proceedings of the 33nd International Conference on Machine Learning, ICML 2016 , volume 48 of JMLR Workshop and Conference Proceedings , pag...

    2016

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.