large scale canonical correlation analysis with iterative least squares

Yichao Lu, Dean P. FosterNeurIPS 2014

Overview

This paper introduces L-CCA, a highly scalable algorithm for Canonical Correlation Analysis (CCA) that replaces expensive matrix decompositions with a sequence of fast, iterative least squares problems. By combining randomized Singular Value Decomposition (SVD) with a clever gradient descent technique, L-CCA can process datasets with millions of features in minutes, significantly outperforming standard approximation methods.

The Scalability Bottleneck of CCA

Canonical Correlation Analysis (CCA) is a fundamental tool for finding relationships between two different "views" of the same data (e.g., a text description and its corresponding image). While powerful for dimensionality reduction and latent variable modeling, CCA suffers from a major scalability bottleneck.

The classical approach requires whitening the data using QR decomposition or SVD. For a dataset with $n$ samples and $p$ features, this costs roughly $O(np^2)$. When dealing with modern "big data"—where $n$ and $p$ can both be in the millions—this becomes computationally prohibitive. Existing approximations often fail because they either assume the data is overly simple (e.g., possessing a diagonal covariance) or they use random projections that might accidentally discard the very correlation structures the researcher is trying to uncover.

Methodology: L-CCA and the LING Solver

The authors propose L-CCA (Iterative Least Squares CCA) to bypass these bottlenecks. The core innovation lies in breaking the global CCA problem into smaller, iterative pieces:

  1. Iterative Framework: Instead of a one-shot decomposition, the algorithm uses "simultaneous iteration." It repeatedly projects one view onto the other using a Least Squares (LS) solver.
  2. The LING Solver: Solving a massive LS problem in every iteration is still slow. To fix this, the authors introduce LING (Linear Iteration with No-Gaps).
  3. The Challenge: Gradient Descent (GD) is notoriously slow when a matrix has a "steep spectrum" (a few very large singular values and many small ones).
  4. The Solution: LING first uses a fast, randomized SVD to find and "remove" the top singular vectors (the heavy hitters). It then applies GD only to the remaining "flatter" part of the signal. This hybrid approach converges much faster than standard gradient descent.
  5. Numerical Stability: The algorithm incorporates QR decomposition on small, intermediate matrices to ensure the iterative process doesn't collapse or drift due to numerical errors.

Datasets and Evaluation

The authors evaluated L-CCA on two large-scale, sparse real-world datasets:

  • Penn Tree Bank (PTB): A word co-occurrence dataset ($1000k \times 43k$ matrix). The goal was to find embeddings for words based on their context.
  • URL Reputation Dataset: Sourced from the UCI repository, containing 2.4 million URLs and 3.2 million features (host-based and lexical features). This represents a massive feature space where traditional CCA would fail.

Key Results

Speed and Accuracy

On the tested datasets, classical CCA implementations took over an hour. In contrast, L-CCA provided high-quality approximations in less than 10 minutes. Furthermore, L-CCA captured significantly more correlation than RPCCA (Randomized Principal Component CCA) within the exact same CPU time budget.

Correlation captured by various CCA methods on the PTB dataset across different CPU time budgets.

Robustness Against Feature Correlation

While D-CCA (a version that assumes diagonal covariance) is faster in some contexts, it performed poorly on the URL dataset because the underlying features were highly correlated. L-CCA remained stable and accurate even when the diagonal assumption failed, demonstrating its robustness in complex, real-world feature spaces.

Performance on the URL Reputation dataset, demonstrating L-CCA's robustness compared to D-CCA and other baselines.

Key Insights

  • CCA vs. PCA Approximation: Approximating CCA is fundamentally harder than approximating PCA. In PCA, the focus is solely on the top singular vectors. In CCA, the strongest correlations might actually reside in the "tail" (the bottom singular vectors) of the individual data matrices.
  • Conditioning Matters: The LING algorithm acts as a powerful pre-conditioner. By surgically removing the top singular values before running gradient descent, it turns a slow, crawling optimization into a highly efficient process.
  • Asymptotic Correctness: Unlike heuristic methods that provide a fixed approximation, L-CCA is asymptotically correct—given enough time, it converges to the exact CCA solution.

Limitations and Future Work

  • Hyperparameter Tuning: The performance of L-CCA depends on choosing the right number of singular vectors ($k_{pc}$) to remove in the LING step. While the paper provides intuition, an automated method for selecting this parameter would be beneficial.
  • Downstream Tasks: While the paper proves the mathematical accuracy of the correlation capture, evaluating these features on specific machine learning tasks (like classification or clustering) is a logical next step.
  • Online Learning: The iterative nature of the algorithm hints at potential for streaming data, though the current implementation is designed for batch processing of large, static datasets.

Summary updated

BibTeX
@inproceedings{lu2014large,
  author = {Yichao Lu and Dean P. Foster},
  title = {{large scale canonical correlation analysis with iterative least squares}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2014},
}
Figure