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

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

## Key facts

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

## Builds on (most cited first, 19 of 19)

- [Newton Sketch: A Linear-time Optimization Algorithm with Linear-Quadratic Convergence](https://mlsanity.com/paper/1505.02250/) (2015)
- [Exact and Inexact Subsampled Newton Methods for Optimization](https://mlsanity.com/paper/1609.08502/) (2016)
- [Iterative Hessian sketch: Fast and accurate solution approximation for constrained least-squares](https://mlsanity.com/paper/1411.0347/) (2014)
- [RSN: Randomized Subspace Newton](https://mlsanity.com/paper/1905.10874/) (2019)
- [Convergence rates of sub-sampled Newton methods](https://mlsanity.com/paper/1508.02810/) (2015)
- [First Efficient Convergence for Streaming k-PCA: a Global, Gap-Free, and Near-Optimal Rate](https://mlsanity.com/paper/1607.07837/) (2016)
- [Fixed-Rank Approximation of a Positive-Semidefinite Matrix from Streaming Data](https://mlsanity.com/paper/1706.05736/) (2017)
- [A Newton-CG Algorithm with Complexity Guarantees for Smooth Unconstrained Optimization](https://mlsanity.com/paper/1803.02924/) (2018)
- [LazySVD: Even Faster SVD Decomposition Yet Without Agonizing Pain](https://mlsanity.com/paper/1607.03463/) (2016)
- [Sub-sampled Newton Methods with Non-uniform Sampling](https://mlsanity.com/paper/1607.00559/) (2016)
- [An Investigation of Newton-Sketch and Subsampled Newton Methods](https://mlsanity.com/paper/1705.06211/) (2017)
- [Fast and Simple PCA via Convex Optimization](https://mlsanity.com/paper/1509.05647/) (2015)
- [Effective Dimension Adaptive Sketching Methods for Faster Regularized Least-Squares Optimization](https://mlsanity.com/paper/2006.05874/) (2020)
- [Optimal Eigenvalue Approximation via Sketching](https://mlsanity.com/paper/2304.09281/) (2023)
- [Sub-Sampled Newton Methods I: Globally Convergent Algorithms](https://mlsanity.com/paper/1601.04737/) (2016)
- [Sub-Sampled Newton Methods II: Local Convergence Rates](https://mlsanity.com/paper/1601.04738/) (2016)
- [Robust Shift-and-Invert Preconditioning: Faster and More Sample Efficient Algorithms for Eigenvector Computation](https://mlsanity.com/paper/1510.08896/) (2015)
- [Doubly Accelerated Methods for Faster CCA and Generalized Eigendecomposition](https://mlsanity.com/paper/1607.06017/) (2016)
- [Do Subsampled Newton Methods Work for High-Dimensional Data?](https://mlsanity.com/paper/1902.04952/) (2019)

## 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.