2015/10/29 by Chi Jin, Jin, Chi, Sham M. Kakade +7 · 2 citations
Computer Science · Engineering · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Matrix Theory and Algorithms #Numerical Analysis (math.NA) #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.1510.08896
openalex publication_date 2015/10/29 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28
We provide faster algorithms and improved sample complexities for approximating the top eigenvector of a matrix. Offline Setting: Given an n × d matrix A, we show how to compute an ε approximate top eigenvector in time O ( [nnz(A) + (d ⋅ sr(A))/(gap2)]⋅ log 1/ε) and O([\fracnnz(A)3/4 (d ⋅ sr(A))1/4√(gap)]⋅ log1/ε). Here sr(A) is the stable rank and gap is the multiplicative eigenvalue gap. By separating the gap dependence from nnz(A) we improve on the classic power and Lanczos methods. We also improve prior work using fast subspace embeddings and stochastic optimization, giving significantly improved dependencies on sr(A) and ε. Our second running time improves this further when nnz(A) ≤ (d⋅ sr(A))/(gap2). Online Setting: Given a distribution D with covariance matrix Σ and a vector x0 which is an O(gap) approximate top eigenvector for Σ, we show how to refine to an ε approximation using O((v(D))/(gap2) + (v(D))/(gap ⋅ ε)) samples from D. Here v(D) is a natural variance measure. Combining our algorithm with previous work to initialize x0, we obtain a number of improved sample complexity and runtime results. For general distributions, we achieve asymptotically optimal accuracy as a function of sample size as the number of samples grows large. Our results center around 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 SVRG based approximate system solvers to achieve our claims. We believe our results suggest the general effectiveness of shift-and-invert based approaches and imply that further computational gains may be reaped in practice.