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
Full metadata record
DC FieldValueLanguage
dc.contributor.authorGarber, D-
dc.contributor.authorHazan, Elad-
dc.contributor.authorJin, C-
dc.contributor.authorKakade, SM-
dc.contributor.authorMusco, C-
dc.contributor.authorNetrapalli, P-
dc.contributor.authorSidford, A-
dc.date.accessioned2018-07-20T15:11:00Z-
dc.date.available2018-07-20T15:11:00Z-
dc.date.issued2016en_US
dc.identifier.citationGarber, D, Hazan, E, Jin, C, Kakade, SM, Musco, C, Netrapalli, P, Sidford, A. (2016). Faster eigenvector computation via shift-and-invert preconditioning. 6 (3886 - 3894en_US
dc.identifier.urihttp://arks.princeton.edu/ark:/88435/pr1ct11-
dc.description.abstractWe 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.en_US
dc.format.extent3886 - 3894en_US
dc.language.isoen_USen_US
dc.relation.ispartof33rd International Conference on Machine Learningen_US
dc.rightsAuthor's manuscripten_US
dc.titleFaster eigenvector computation via shift-and-invert preconditioningen_US
dc.typeConference Articleen_US
dc.date.eissued2016en_US
pu.type.symplectichttp://www.symplectic.co.uk/publications/atom-terms/1.0/conference-proceedingen_US

Files in This Item:
File Description SizeFormat 
Faster eigenvector computation via shift-and-invert preconditioning.pdf539.22 kBAdobe PDFView/Download


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