# Improved analysis of randomized SVD for top-eigenvector approximation

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 50 references that are in the map.
- First posted on arXiv 16 Feb 2022.

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

- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [Randomized Block Krylov Methods for Stronger and Faster Approximate Singular Value Decomposition](https://mlsanity.com/paper/1504.05477/) (2015)
- [The Noisy Power Method: A Meta Algorithm with Applications](https://mlsanity.com/paper/1311.2495/) (2013)
- [Frequent Directions : Simple and Deterministic Matrix Sketching](https://mlsanity.com/paper/1501.01711/) (2015)
- [Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors](https://mlsanity.com/paper/1512.02337/) (2015)
- [LazySVD: Even Faster SVD Decomposition Yet Without Agonizing Pain](https://mlsanity.com/paper/1607.03463/) (2016)
- [Accelerated Stochastic Power Iteration](https://mlsanity.com/paper/1707.02670/) (2017)
- [Discovering Polarized Communities in Signed Networks](https://mlsanity.com/paper/1910.02438/) (2019)
- [Sublinear Time Low-Rank Approximation of Positive Semidefinite Matrices](https://mlsanity.com/paper/1704.03371/) (2017)
- [Randomized Matrix Decompositions using R](https://mlsanity.com/paper/1608.02148/) (2016)
- [Tight Query Complexity Lower Bounds for PCA via Finite Sample Deformed Wigner Law](https://mlsanity.com/paper/1804.01221/) (2018)
- [Spectral Approaches to Nearest Neighbor Search](https://mlsanity.com/paper/1408.0751/) (2014)
- [Spectral Algorithms for Temporal Graph Cuts](https://mlsanity.com/paper/1702.04746/) (2017)

## Abstract (arXiv)

Computing the top eigenvectors of a matrix is a problem of fundamental interest to various fields. While the majority of the literature has focused on analyzing the reconstruction error of low-rank matrices associated with the retrieved eigenvectors, in many applications one is interested in finding one vector with high Rayleigh quotient. In this paper we study the problem of approximating the top-eigenvector. Given a symmetric matrix A with largest eigenvalue λ1, our goal is to find a vector hu that approximates the leading eigenvector u1 with high accuracy, as measured by the ratio R(hatu)=λ1-1hatuTAhatu/hatuThatu. We present a novel analysis of the randomized SVD algorithm of citethalko2011finding and derive tight bounds in many cases of interest. Notably, this is the first work that provides non-trivial bounds of R(hatu) for randomized SVD with any number of iterations. Our theoretical analysis is complemented with a thorough experimental study that confirms the efficiency and accuracy of the method.