Doubly Accelerated Methods for Faster CCA and Generalized Eigendecomposition
[edit]
Proceedings of the 34th International Conference on Machine Learning, PMLR 70:98106, 2017.
Abstract
We study kGenEV, the problem of finding the top k generalized eigenvectors, and kCCA, the problem of finding the top k vectors in canonicalcorrelation 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 doublyaccelerated: 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 kGenEV or kCCA. We also provide the first gapfree results, which provide running times that depend on $1/\sqrt{\varepsilon}$ rather than the eigengap.
Related Material


