To refer to this page use:
|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.|
|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|
Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.