Doubly Accelerated Methods for Faster CCA and Generalized Eigendecomposition

2016/07/20 by Zeyuan Allen-Zhu, Yuanzhi Li, Allen-Zhu, Zeyuan +1 · 1 citation
Computer Science · Engineering · Neuroscience · #Blind Source Separation Techniques #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Face and Expression Recognition #Functional Brain Connectivity Studies #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques

paper · pdf · doi:10.48550/arxiv.1607.06017

openalex publication_date 2016/07/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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 \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/√(ε) rather than the eigengap.

Cited by

• Representation Learning for Words and Entities

Related

• Efficient Algorithms for Large-scale Generalized Eigenvector Computation and Canonical Correlation Analysis
• Efficient Dimensionality Reduction for Canonical Correlation Analysis
• Finding Linear Structure in Large Datasets with Scalable Canonical Correlation Analysis
• ℓ₁-norm constrained multi-block sparse canonical correlation analysis via proximal gradient descent
• Large scale canonical correlation analysis with iterative least squares