Skip to main content

Faster eigenvector computation via shift-and-invert preconditioning

Author(s): Garber, D; Hazan, Elad; Jin, C; Kakade, SM; Musco, C; et al

Download
To refer to this page use: http://arks.princeton.edu/ark:/88435/pr1ct11
Abstract: We give faster algorithms and improved sample complexities for the fundamental problem of estimating the top eigenvector. Given an explicit matrix A € Rn×d, we show how to compute an e approximate top eigenvector of ATA in time O (jnnz(A) + • log l/ϵ). Here nnz(A) is the number of nonzeros in A, sr(A) is the stable rank, and gap is the relative eigengap. We also consider an online setting in which, given a stream of i.i.d. samples from a distribution V with covariance matrix E and a vector xq which is an O(gap) approximate top eigenvector for E, we show how to refine xo to an € approximation using O j samples from V. Here v(P) is a natural notion of variance. Combining our algorithm with previous work to initialize xo, we obtain improved sample complexities and runtimes under a variety of assumptions on V. We achieve our results via a robust analysis of the classic shift-and-invert preconditioning method. This technique lets us reduce eigenvector computation to approximately solving a scries of linear systems with fast stochastic gradient methods.
Publication Date: 2016
Electronic Publication Date: 2016
Citation: Garber, D, Hazan, E, Jin, C, Kakade, SM, Musco, C, Netrapalli, P, Sidford, A. (2016). Faster eigenvector computation via shift-and-invert preconditioning. 6 (3886 - 3894
Pages: 3886 - 3894
Type of Material: Conference Article
Journal/Proceeding Title: 33rd International Conference on Machine Learning
Version: Author's manuscript



Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.