Doubly Accelerated Methods for Faster CCA and Generalized Eigendecomposition
This work addresses computational bottlenecks in machine learning and data analysis for researchers and practitioners dealing with large-scale matrix problems, offering significant speedups.
The paper tackled the problems of finding top k generalized eigenvectors (k-GenEV) and canonical-correlation analysis vectors (k-CCA) by proposing algorithms LazyEV and LazyCCA, achieving running times linear in input size and k, with doubly-accelerated dependencies on the square root of matrix condition number and eigengap, and providing the first such results for these problems.
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 $\mathtt{LazyEV}$ and $\mathtt{LazyCCA}$ to solve the two problems with running times linearly dependent on the input size and on $k$. 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 $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.