📊 statistics

Accelerating Power Method with Fast Sketching for Stronger Low-Rank Approximation

This paper introduces a fast sketching framework that accelerates the power method for large-rank low-rank matrix approximation by leveraging regularized spectral approximation to achieve provably efficient and numerically strong performance in SVD, factorization, and Nyström approximation.

Original authors: Shabarish Chenakkod, Michał Dereziński

Published 2026-05-12

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Shabarish Chenakkod, Michał Dereziński

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a massive library of information (a giant data matrix) and you want to find the most important stories hidden inside it. In the world of data science, this is called finding the "top principal components."

The traditional way to do this is called the Power Method. Think of this like trying to find the loudest voice in a crowded stadium by shouting a question and listening for the echo. You shout, listen, shout again, and listen again. With every repetition, the echo gets clearer, and you get closer to the loudest voice. However, if the stadium is huge, shouting and listening takes a long time. If you need to find the top 100 voices instead of just the loudest one, the process becomes painfully slow and expensive.

Another method, called Fast Sketching, is like hiring a team of quick surveyors to take a "snapshot" of the stadium instead of listening to every single echo. They create a smaller, rougher version of the data (a "sketch") that is much faster to process. But here's the catch: if you try to use this sketch to do the "shouting and listening" (the power method) repeatedly, the surveyors get tired, and the speed advantage disappears.

The Paper's Big Idea: The "Sketch-Powered" Shortcut

The authors of this paper developed a clever hybrid strategy they call the Sketch-Powered Power Method.

Here is the analogy:
Instead of shouting at the whole stadium (the full data) or just taking a single snapshot, they do this:

Take a big, detailed snapshot: They use a fast sketching tool to create a "rough draft" of the data. This draft is smaller than the original but still holds enough detail to be useful.
Do the "shouting" on the draft: They run their repeated "shouting and listening" process (the power method) on this smaller, rough draft instead of the giant original.
The Result: Because the draft is smaller, each step of the process is incredibly fast. Even though the draft isn't perfect, doing the process a few times on it gets you a very good answer much faster than doing it once on the giant original.

The Secret Sauce: "Regularized Spectral Approximation"

The authors had to solve a tricky math problem. Usually, when you use a sketch, you have to worry that the sketch is "too blurry" to give you a perfect answer. Traditional math tools for analyzing this didn't work well for their new hybrid method.

So, they invented a new way of looking at the math, which they call Regularized Spectral Approximation.

The Metaphor: Imagine you are trying to guess the shape of a mountain by looking at a blurry photo. Traditional methods say, "If the photo is blurry, you can't trust the shape."
The New Method: The authors say, "Let's add a little bit of 'fuzziness' (regularization) to our math rules. If we accept that the photo is a slightly fuzzy version of the mountain, we can prove that even a few quick glances at the photo will get us very close to the real shape."

This new mathematical lens allowed them to prove that their method works reliably, even with the "blurry" sketch.

What They Actually Achieved

The paper doesn't just talk theory; they built three specific tools based on this idea:

Sketch-Powered Range Finder: A tool to quickly find the "directions" where the data is most important. It's faster than the old way and almost as accurate.
Sketch-Powered Low-Rank Factorization: A way to break a giant matrix into two smaller, easier-to-handle pieces. Usually, this step requires a very expensive calculation at the end. Their method skips that expensive step, saving a huge amount of time.
Sketch-Powered Nyström Approximation: A specific tool for analyzing data that is "symmetric" (like a map where the distance from A to B is the same as B to A). They made this tool faster by running the power method on a smaller, reduced version of the data.

The Bottom Line

The authors tested their method on real-world data sets (like images from the internet and synthetic data). They found that their method reaches a "good enough" answer much faster than the traditional methods.

Old Way: Slow, but eventually gets a perfect answer.
New Way: Very fast, gets a "very good" answer quickly, and is perfect for situations where you need results fast and don't need 100% perfection.

In short, they figured out how to use a "rough draft" to speed up the process of finding the most important patterns in massive data, without losing the quality of the result.

Technical Summary: Accelerating Power Method with Fast Sketching for Stronger Low-Rank Approximation

Problem Statement

Computing the top singular values and singular vectors of a large matrix $A \in \mathbb{R}^{m \times n}$ is a fundamental task in data science. The power method (and its block variant) is a standard approach for extracting these components to form low-rank approximations. However, when the target rank $k$ is large, the repeated matrix multiplications required by the power method (specifically computing $(AA^\top)^q A \Omega$ ) become a computational bottleneck.

While fast sketching (using structured random matrices $S$ to compute a sketch $\tilde{A} = AS$ ) is a powerful tool for avoiding expensive matrix multiplications in dimensionality reduction, naively combining it with the power method presents challenges:

Applying $A$ repeatedly to a sketch $(AA^\top)^q AS$ negates the speed benefits of sketching.
Replacing $A$ entirely with a sketch $\tilde{A}$ in the power iteration (computing $(\tilde{A}\tilde{A}^\top)^q \tilde{A}\Omega$ ) was previously not well-understood theoretically. It was unclear if such a "sketched power method" could provide strong approximation guarantees, as the sketch $\tilde{A}$ is a "rough" version of $A$ and the method does not converge to the exact top- $k$ subspace of $A$ even as iterations $q \to \infty$ .

Methodology

The authors propose a framework that integrates fast sketching directly into the power method iterations. Instead of the classical range finder $Q = \text{orth}((AA^\top)^q A \Omega)$ , they compute:
$Q = \text{orth}\left( (\tilde{A}\tilde{A}^\top)^q \tilde{A} \Omega \right)$
where $\tilde{A} = AS$ is a sketch of size $m \times l$ (with $l \gg k$ but $l \ll n$ ), and $\Omega$ is a Gaussian matrix of size $l \times k$ .

Theoretical Innovation: Regularized Spectral Approximation

The core theoretical contribution is the use of regularized spectral approximation to analyze this method. Unlike traditional analyses that rely on rotational invariance of Gaussian matrices or subspace embedding properties, this approach leverages the property that for a suitably chosen regularization parameter $\lambda$ and accuracy $\epsilon$ :
$(1-\epsilon)(AA^\top + \lambda I) \preceq \tilde{A}\tilde{A}^\top + \lambda I \preceq (1+\epsilon)(AA^\top + \lambda I)$
The authors demonstrate that:

Classical range finder guarantees can be recovered using this property.
A subspace approximation guarantee with respect to the sketch $\tilde{A}$ can be translated to a guarantee with respect to the original matrix $A$ , with an additive error term dependent on the quality of the regularized spectral approximation.
This analysis holds even when the initialization involves a mix of structured sketching matrices and dense Gaussian matrices.

Key Contributions

The paper develops algorithms and theoretical guarantees for three specific applications:

1. Sketch-Powered Range Finder

The authors provide a theoretical guarantee for constructing a range finder $Q$ using the sketched power method.

Result: For a sparse sketch size $l \gg k$ , the method achieves an approximation error $\|A - QQ^\top A\|_2$ bounded by $(1+\epsilon)\sigma_{k+1}^2(A) + \epsilon \sum_{i>l} \sigma_i^2(A)$ .
Significance: This allows for a trade-off where a larger sketch size $l$ reduces the additive error term, enabling strong approximations with fewer iterations $q$ compared to the classical method, while maintaining low per-iteration costs.

2. Sketch-Powered Low-Rank Factorization

Standard Randomized SVD requires an expensive final matrix product $B = Q^\top A$ . The authors integrate the sketched power method into a Generalized Nyström framework to avoid this bottleneck.

Algorithm: Uses a second sketching matrix $S_2$ to approximate the projection of $A$ onto the subspace defined by $Q$ without explicitly computing $Q^\top A$ .
Result: For an $n \times n$ matrix and $k \le O(\sqrt{n})$ , the algorithm computes a rank- $O(k)$ factorization $\hat{A} = YX$ in $\tilde{O}(n^2)$ time with an error guarantee $\|A - YX\|_2 \le \sqrt{k+1} \cdot \sigma_{k+1}(A)$ .
Comparison: Without the sketched power method, achieving similar error bounds in the same time budget is impossible; existing methods either have weaker error guarantees ( $O(\sqrt{n/k})$ ) or higher time complexity ( $\tilde{O}(n^2 k)$ ).

3. Sketch-Powered Nyström Approximation

For symmetric positive semidefinite (PSD) matrices, the authors optimize the approach for Nyström approximation.

Algorithm: Incorporates the sketched power method into the classical Nyström procedure by performing power iterations on the reduced matrix $\tilde{W} = S^\top AS$ (which is $l \times l$ ) rather than on the full matrix or a single sketch.
Result: This yields a PSD factorization with error bounds similar to the general case, specifically $\|A - CW^\dagger C^\top\| \le (1+\epsilon)\lambda_{k+1}(A) + \epsilon \sum_{i>l} \lambda_i(A)$ .

Experimental Results

The authors validate their theory on three large datasets: smallnorb ( $24300 \times 9216$ ), ImageNet ( $20800 \times 50176$ ), and a synthetic polydecay matrix ( $30000 \times 15000$ ).

Performance: The Sketch-Powered Randomized SVD reaches a moderately small relative error (e.g., 0.1) significantly faster than the Classical Randomized SVD.
Trade-off: While the error eventually plateaus (due to the additive error term from the sketch), the method achieves this plateau much sooner than the classical method, compensating for the overhead of forming the initial sketch.
Factorization: Similar computational improvements were observed for the Sketch-Powered Low-Rank Factorization (Algorithm 2) compared to baselines without sketching.

Significance and Claims

The paper claims to provide a simple and provably efficient framework for accelerating the power method.

Theoretical Novelty: The primary contribution is the shift from traditional analysis (Gaussian invariance/subspace embedding) to regularized spectral approximation. This allows the authors to analyze the sketched power method without relying on the sketching matrices being Gaussian, thereby unlocking the computational benefits of fast, structured sketches (like CountSketch).
Practical Impact: The framework offers a way to attain strong numerical performance on benchmark problems with reduced computational complexity, particularly for large target ranks where classical power methods are bottlenecked by matrix multiplication.
Modesty: The authors acknowledge that the method does not converge to a perfect alignment with the top- $k$ subspace as $q \to \infty$ (unlike the classical method), but argue that it reaches a "sufficiently good approximation much faster" due to the reduced per-iteration cost. They position this as a solution for computationally constrained environments where even the per-iteration cost of the classical method is prohibitive.