# Faster Eigenvector Computation via Shift-and-Invert Preconditioning

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

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 May 2016.

## Built on by (most cited first, 18 of 18)

- [Hessian Averaging in Stochastic Newton Methods Achieves Superlinear Convergence](https://mlsanity.com/paper/2204.09266/) (2022)
- [On the Optimality of the Oja's Algorithm for Online PCA](https://mlsanity.com/paper/2104.00512/) (2021)
- [Stochastic Distributed Optimization under Average Second-order Similarity: Algorithms and Analysis](https://mlsanity.com/paper/2304.07504/) (2023)
- [RECAPP: Crafting a More Efficient Catalyst for Convex Optimization](https://mlsanity.com/paper/2206.08627/) (2022)
- [Black-Box k-to-1-PCA Reductions: Theory and Applications](https://mlsanity.com/paper/2403.03905/) (2024)
- [FedPower: Privacy-Preserving Distributed Eigenspace Estimation](https://mlsanity.com/paper/2103.00704/) (2021)
- [Generating Post-hoc Explanations for Skip-gram-based Node Embeddings by Identifying Important Nodes with Bridgeness](https://mlsanity.com/paper/2304.12036/) (2023)
- [Community Detection in the Hypergraph SBM: Exact Recovery Given the Similarity Matrix](https://mlsanity.com/paper/2208.12227/) (2022)
- [Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function](https://mlsanity.com/paper/2310.11866/) (2023)
- [Approaching Optimality for Solving Dense Linear Systems with Low-Rank Structure](https://mlsanity.com/paper/2507.11724/) (2025)
- [Communication-efficient distributed eigenspace estimation with arbitrary node failures](https://mlsanity.com/paper/2206.00127/) (2022)
- [Provable Model-Parallel Distributed Principal Component Analysis with Parallel Deflation](https://mlsanity.com/paper/2502.17615/) (2025)
- [Gap-Free Streaming PCA Beyond Rank-One Updates: Near-Optimal Rates and Applications to Differential Privacy](https://mlsanity.com/paper/2609.26508/) (2026)
- [Spectral Algorithms Optimally Recover Planted Sub-structures](https://mlsanity.com/paper/2203.11847/) (2022)
- [Stochastic Parallelizable Eigengap Dilation for Large Graph Clustering](https://mlsanity.com/paper/2207.14589/) (2022)
- [k-SVD with Gradient Descent](https://mlsanity.com/paper/2502.00320/) (2025)
- [Efficient Training of Deep Networks using Guided Spectral Data Selection: A Step Toward Learning What You Need](https://mlsanity.com/paper/2507.04269/) (2025)
- [Incremental Aggregation on the Grassmannian for Asynchronous Eigenspace Computation](https://mlsanity.com/paper/2608.04406/) (2026)

## Abstract (arXiv)

We give faster algorithms and improved sample complexities for estimating the top eigenvector of a matrix Sigma -- i.e. computing a unit vector x such that xT Sigma x ≥ (1-ε)λ1(Sigma): Offline Eigenvector Estimation: Given an explicit A ∈ ℝn × d with Sigma = ATA, we show how to compute an ε approximate top eigenvector in time tilde O([nnz(A) + fracd*sr(A)gap2 ]* log 1/ε ) and tilde O([fracnnz(A)3/4 (d*sr(A))1/4√gap ] * log 1/ε ). Here nnz(A) is the number of nonzeros in A, sr(A) is the stable rank, gap is the relative eigengap. By separating the gap dependence from the nnz(A) term, our first runtime improves upon the classical power and Lanczos methods. It also improves prior work using fast subspace embeddings [AC09, CW13] and stochastic optimization [Sha15c], giving significantly better dependencies on sr(A) and ε. Our second running time improves these further when nnz(A) ≤ fracd*sr(A)gap2. Online Eigenvector Estimation: Given a distribution D with covariance matrix Sigma and a vector x0 which is an O(gap) approximate top eigenvector for Sigma, we show how to refine to an ε approximation using  O(fracvar(D)gap*ε) samples from D. Here var(D) is a natural notion of variance. Combining our algorithm with previous work to initialize x0, we obtain improved sample complexity and runtime results under a variety of assumptions on D. We achieve our results using a general framework that we believe is of independent interest. We give a robust analysis of the classic method of shift-and-invert preconditioning to reduce eigenvector computation to approximately solving a sequence of linear systems. We then apply fast stochastic variance reduced gradient (SVRG) based system solvers to achieve our claims.