Doubly Accelerated Methods for Faster CCA and Generalized Eigendecomposition

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 $\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{\epsilon }$ rather than the eigengap.

We have now stated more clearly why this paper has outperformed relevant previous results, and included discussions for doubly-stochastic methods. arXiv admin note: text overlap with arXiv:1607.03463

References in corpus (3)

• Even Faster Accelerated Coordinate Descent Using Non-Uniform Sampling
• Randomized Block Krylov Methods for Stronger and Faster Approximate Singular Value Decomposition
• Fast and Simple PCA via Convex Optimization

Cited by in corpus (6)

• Structured SUMCOR Multiview Canonical Correlation Analysis for Large-Scale Data
• Accelerated Stochastic Power Iteration
• First Efficient Convergence for Streaming k-PCA: a Global, Gap-Free, and Near-Optimal Rate
• Faster Principal Component Regression and Stable Matrix Chebyshev Approximation
• Noisy Accelerated Power Method for Eigenproblems with Applications
• Larger is Better: The Effect of Learning Rates Enjoyed by Stochastic Optimization with Progressive Variance Reduction