Skip to yearly menu bar Skip to main content


Poster

Doubly Accelerated Methods for Faster CCA and Generalized Eigendecomposition

Zeyuan Allen-Zhu · Yuanzhi Li

Gallery #68

Abstract:

We study k-GenEV, the problem of finding the top k generalized eigenvectors, and k-CCA, the problem of finding the top k vectors in canonical-correlation analysis. We propose algorithms LazyEV and LazyCCA to solve the two problems with running times linearly dependent on the input size and on k.

Furthermore, our algorithms are \emph{doubly-accelerated}: our running times depend only on the square root of the matrix condition number, and on the square root of the eigengap. This is the first such result for both k-GenEV or k-CCA. We also provide the first gap-free results, which provide running times that depend on 1/\sqrt{\varepsilon}$ rather than the eigengap.

Live content is unavailable. Log in and register to view live content