mlsanityData to 7 Oct 2026

What is a Sketch-and-Precondition Derivation for Low-Rank Approximation? Inverse Power Error or Inverse Power Estimation?

arXiv 2502.07993 ↗First posted 11 Feb 2025math.NA cs.CC cs.LGcited by 0

Not on the map. Why?

Abstract (arXiv)

Randomized sketching accelerates large-scale numerical linear algebra by reducing computational complexity. While the traditional sketch-and-solve approach reduces the problem size directly through sketching, the sketch-and-precondition method leverages sketching to construct a computational friendly preconditioner. This preconditioner improves the convergence speed of iterative solvers applied to the original problem, maintaining accuracy in the full space. Furthermore, the convergence rate of the solver improves at least linearly with the sketch size. Despite its potential, developing a sketch-and-precondition framework for randomized algorithms in low-rank matrix approximation remains an open challenge. We introduce the Error-Powered Sketched Inverse Iteration (EPSI) Method via run sketched Newton iteration for the Lagrange form as a sketch-and-precondition variant for randomized low-rank approximation. Our method achieves theoretical guarantees, including a convergence rate that improves at least linearly with the sketch size.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 19 of its 63 references that are in the map. First posted on arXiv 11 Feb 2025.

Builds on

19 of 63 references.

References · 19

  1. 2015Newton Sketch: A Linear-time Optimization Algorithm with Linear-Quadratic Convergencecited by 72
  2. 2016Exact and Inexact Subsampled Newton Methods for Optimizationcited by 38
  3. 2014Iterative Hessian sketch: Fast and accurate solution approximation for constrained least-squarescited by 34
  4. 2019RSN: Randomized Subspace Newtoncited by 34
  5. 2015Convergence rates of sub-sampled Newton methodscited by 32
  6. 2016First Efficient Convergence for Streaming k-PCA: a Global, Gap-Free, and Near-Optimal Ratecited by 31
  7. 2018A Newton-CG Algorithm with Complexity Guarantees for Smooth Unconstrained Optimizationcited by 23
  8. 2016LazySVD: Even Faster SVD Decomposition Yet Without Agonizing Paincited by 22
  9. 2017Fixed-Rank Approximation of a Positive-Semidefinite Matrix from Streaming Datacited by 22
  10. 2016Sub-sampled Newton Methods with Non-uniform Samplingcited by 21
  11. 2017An Investigation of Newton-Sketch and Subsampled Newton Methodscited by 18
  12. 2015Fast and Simple PCA via Convex Optimizationcited by 16
7 more
  1. 2020Effective Dimension Adaptive Sketching Methods for Faster Regularized Least-Squares Optimizationcited by 9
  2. 2023Optimal Eigenvalue Approximation via Sketchingcited by 9
  3. 2016Sub-Sampled Newton Methods I: Globally Convergent Algorithmscited by 8
  4. 2016Sub-Sampled Newton Methods II: Local Convergence Ratescited by 7
  5. 2015Robust Shift-and-Invert Preconditioning: Faster and More Sample Efficient Algorithms for Eigenvector Computationcited by 5
  6. 2016Doubly Accelerated Methods for Faster CCA and Generalized Eigendecompositioncited by 5
  7. 2019Do Subsampled Newton Methods Work for High-Dimensional Data?cited by 5

Built on by

Not cited yet.