Finding Linear Structure in Large Datasets with Scalable Canonical Correlation Analysis

Abstract

Canonical Correlation Analysis (CCA) is a widely used spectral technique for finding correlation structures in multi-view datasets. In this paper, we tackle the problem of large scale CCA, where classical algorithms, usually requiring computing the product of two huge matrices and huge matrix decomposition, are computationally and storage expensive. We recast CCA from a novel perspective and propose a scalable and memory efficient Augmented Approximate Gradient (AppGrad) scheme for finding top $k$ dimensional canonical subspace which only involves large matrix multiplying a thin matrix of width $k$ and small matrix decomposition of dimension $k\times k$. Further, AppGrad achieves optimal storage complexity $O(k(p_1+p_2))$, compared with classical algorithms which usually require $O(p_1^2+p_2^2)$ space to store two dense whitening matrices. The proposed scheme naturally generalizes to stochastic optimization regime, especially efficient for huge datasets where batch algorithms are prohibitive. The online property of stochastic AppGrad is also well suited to the streaming scenario, where data comes sequentially. To the best of our knowledge, it is the first stochastic algorithm for CCA. Experiments on four real data sets are provided to show the effectiveness of the proposed methods.

Appearing in International Conference on Machine Learning (ICML) 2015

References in corpus (4)

• Memory Limited, Streaming PCA
• Two Step CCA: A new spectral method for estimating vector models of words
• Large scale canonical correlation analysis with iterative least squares
• Correlated random features for fast semi-supervised learning

Cited by in corpus (24)

• Learning Deep Structure-Preserving Image-Text Embeddings
• On Deep Multi-View Representation Learning: Objectives and Optimization
• Scalable and Flexible Multiview MAX-VAR Canonical Correlation Analysis
• Structured SUMCOR Multiview Canonical Correlation Analysis for Large-Scale Data
• Large-Scale Approximate Kernel Canonical Correlation Analysis
• Text2Shape: Generating Shapes from Natural Language by Learning Joint Embeddings
• Scene Graph Reasoning with Prior Visual Relationship for Visual Question Answering
• Solving Empirical Risk Minimization in the Current Matrix Multiplication Time
• Nonlinear Multiview Analysis: Identifiability and Neural Network-assisted Implementation
• Katyusha X: Practical Momentum Method for Stochastic Sum-of-Nonconvex Optimization
• Stochastic Optimization for Deep CCA via Nonlinear Orthogonal Iterations
• Stochastic Canonical Correlation Analysis
• Efficient Algorithms for Large-scale Generalized Eigenvector Computation and Canonical Correlation Analysis
• Quantum-inspired canonical correlation analysis for exponentially large dimensional data
• Noisy Accelerated Power Method for Eigenproblems with Applications
• Subspace Perspective on Canonical Correlation Analysis: Dimension Reduction and Minimax Rates
• Semantic Modeling of Textual Relationships in Cross-Modal Retrieval
• Efficient Globally Convergent Stochastic Optimization for Canonical Correlation Analysis
• D-Sempre: Learning Deep Semantic-Preserving Embeddings for User interests-Social Contents Modeling
• Learning Representations of Social Media Users
• Faster Randomized Methods for Orthogonality Constrained Problems
• Sparse Generalized Canonical Correlation Analysis: Distributed Alternating Iteration based Approach
• Tensor Canonical Correlation Analysis with Convergence and Statistical Guarantees
• Gen-Oja: A Two-time-scale approach for Streaming CCA