Finding Linear Structure in Large Datasets with Scalable Canonical Correlation Analysis

Zhuang Ma, Yichao Lu, Dean Foster
Proceedings of the 32nd International Conference on Machine Learning, PMLR 37:169-178, 2015.

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 \textitAugmented 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, \textitAppGrad 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 \textitAppGrad 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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v37-maa15, title = {Finding Linear Structure in Large Datasets with Scalable Canonical Correlation Analysis}, author = {Ma, Zhuang and Lu, Yichao and Foster, Dean}, booktitle = {Proceedings of the 32nd International Conference on Machine Learning}, pages = {169--178}, year = {2015}, editor = {Bach, Francis and Blei, David}, volume = {37}, series = {Proceedings of Machine Learning Research}, address = {Lille, France}, month = {07--09 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v37/maa15.pdf}, url = {https://proceedings.mlr.press/v37/maa15.html}, 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 \textitAugmented 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, \textitAppGrad 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 \textitAppGrad 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.} }
Endnote
%0 Conference Paper %T Finding Linear Structure in Large Datasets with Scalable Canonical Correlation Analysis %A Zhuang Ma %A Yichao Lu %A Dean Foster %B Proceedings of the 32nd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2015 %E Francis Bach %E David Blei %F pmlr-v37-maa15 %I PMLR %P 169--178 %U https://proceedings.mlr.press/v37/maa15.html %V 37 %X 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 \textitAugmented 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, \textitAppGrad 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 \textitAppGrad 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.
RIS
TY - CPAPER TI - Finding Linear Structure in Large Datasets with Scalable Canonical Correlation Analysis AU - Zhuang Ma AU - Yichao Lu AU - Dean Foster BT - Proceedings of the 32nd International Conference on Machine Learning DA - 2015/06/01 ED - Francis Bach ED - David Blei ID - pmlr-v37-maa15 PB - PMLR DP - Proceedings of Machine Learning Research VL - 37 SP - 169 EP - 178 L1 - http://proceedings.mlr.press/v37/maa15.pdf UR - https://proceedings.mlr.press/v37/maa15.html AB - 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 \textitAugmented 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, \textitAppGrad 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 \textitAppGrad 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. ER -
APA
Ma, Z., Lu, Y. & Foster, D.. (2015). Finding Linear Structure in Large Datasets with Scalable Canonical Correlation Analysis. Proceedings of the 32nd International Conference on Machine Learning, in Proceedings of Machine Learning Research 37:169-178 Available from https://proceedings.mlr.press/v37/maa15.html.

Related Material