Published on Wed Jul 20 2016

### Doubly Accelerated Methods for Faster CCA and Generalized Eigendecomposition

,

We study -GenEV, the problem of finding the top $k$ generalized eigenvectors. We propose algorithms to solve the two problems with running times linearly dependent on the input size and on .

0
0
0
###### Abstract

We study -GenEV, the problem of finding the top generalized eigenvectors, and -CCA, the problem of finding the top vectors in canonical-correlation analysis. We propose algorithms and to solve the two problems with running times linearly dependent on the input size and on . Furthermore, our algorithms are 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 -GenEV or -CCA. We also provide the first gap-free results, which provide running times that depend on rather than the eigengap.