# Doubly Accelerated Methods for Faster CCA and Generalized Eigendecomposition

arXiv: https://arxiv.org/abs/1607.06017 · HTML: https://mlsanity.com/paper/1607.06017/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Jul 2016.

## Built on by (most cited first, 5 of 5)

- [An Online Riemannian PCA for Stochastic Canonical Correlation Analysis](https://mlsanity.com/paper/2106.07479/) (2021)
- [Optimization without Retraction on the Random Generalized Stiefel Manifold](https://mlsanity.com/paper/2405.01702/) (2024)
- [Nonconvex Stochastic Scaled-Gradient Descent and Generalized Eigenvector Problems](https://mlsanity.com/paper/2112.14738/) (2021)
- [The Symmetric Generalized Eigenvalue Problem as a Nash Equilibrium](https://mlsanity.com/paper/2206.04993/) (2022)
- [What is a Sketch-and-Precondition Derivation for Low-Rank Approximation? Inverse Power Error or Inverse Power Estimation?](https://mlsanity.com/paper/2502.07993/) (2025)

## Abstract (arXiv)

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 mathttLazyEV and mathttLazyCCA 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/√varepsilon rather than the eigengap.