# Efficient Algorithms for Large-scale Generalized Eigenvector Computation and Canonical Correlation Analysis

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Apr 2016.

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

- [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)
- [Differential geometry with extreme eigenvalues in the positive semidefinite cone](https://mlsanity.com/paper/2304.07347/) (2023)
- [Generalized Eigenvalue Problems with Generative Priors](https://mlsanity.com/paper/2411.01326/) (2024)
- [Faster Randomized Methods for Orthogonality Constrained Problems](https://mlsanity.com/paper/2106.12060/) (2021)
- [Nonconvex Stochastic Scaled-Gradient Descent and Generalized Eigenvector Problems](https://mlsanity.com/paper/2112.14738/) (2021)
- [The inexact power augmented Lagrangian method for constrained nonconvex optimization](https://mlsanity.com/paper/2410.20153/) (2024)
- [Communication-Efficient Federated Linear and Deep Generalized Canonical Correlation Analysis](https://mlsanity.com/paper/2109.12400/) (2021)
- [Multiblock ADMM for nonsmooth nonconvex optimization with nonlinear coupling constraints](https://mlsanity.com/paper/2201.07657/) (2022)
- [The Symmetric Generalized Eigenvalue Problem as a Nash Equilibrium](https://mlsanity.com/paper/2206.04993/) (2022)

## Abstract (arXiv)

This paper considers the problem of canonical-correlation analysis (CCA) (Hotelling, 1936) and, more broadly, the generalized eigenvector problem for a pair of symmetric matrices. These are two fundamental problems in data analysis and scientific computing with numerous applications in machine learning and statistics (Shi and Malik, 2000; Hardoon et al., 2004; Witten et al., 2009). We provide simple iterative algorithms, with improved runtimes, for solving these problems that are globally linearly convergent with moderate dependencies on the condition numbers and eigenvalue gaps of the matrices involved. We obtain our results by reducing CCA to the top-k generalized eigenvector problem. We solve this problem through a general framework that simply requires black box access to an approximate linear system solver. Instantiating this framework with accelerated gradient descent we obtain a running time of O(fracz k √kappaρ log(1/ε) log left(kkappa/ρright)) where z is the total number of nonzero entries, kappa is the condition number and ρ is the relative eigenvalue gap of the appropriate matrices. Our algorithm is linear in the input size and the number of components k up to a log(k) factor. This is essential for handling large-scale matrices that appear in practice. To the best of our knowledge this is the first such algorithm with global linear convergence. We hope that our results prompt further research and ultimately improve the practical running time for performing these important data analysis procedures on large data sets.