A simple and provable algorithm for sparse diagonal CCA

Megasthenis Asteris, Anastasios Kyrillidis, Oluwasanmi Koyejo, Russell Poldrack

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Given two sets of variables, derived from a common set of samples, sparse Canonical Correlation Analysis (CCA) seeks linear combinations of a small number of variables in each set. such that the induced canonical variables are maximally correlated. Sparse CCA is NP-hard. We propose a novel combinatorial algorithm for sparse diagonal CCA, i.e., sparse CCA under the additional assumption that variables within each set are standardized and uncorrelated. Our algorithm operates on a low rank approximation of the input data and its computational complexity scales linearly with the number of input variables. It is simple to implement, and parallelizable. In contrast to most existing approaches, our algorithm administers precise control on the sparsity of the extracted canonical vectors, and comes with theoretical data-dependent global approximation guarantees, that hinge on the spectrum of the input data. Finally, it can be straightforwardly adapted to other constrained variants of CCA enforcing structure beyond sparsity. We empirically evaluate the proposed scheme and apply it on a real neuroimaging dataset to investigate associations between brain activity and behavior measurements.

Original languageEnglish (US)
Title of host publication33rd International Conference on Machine Learning, ICML 2016
EditorsKilian Q. Weinberger, Maria Florina Balcan
PublisherInternational Machine Learning Society (IMLS)
Pages1774-1783
Number of pages10
ISBN (Electronic)9781510829008
StatePublished - Jan 1 2016
Event33rd International Conference on Machine Learning, ICML 2016 - New York City, United States
Duration: Jun 19 2016Jun 24 2016

Publication series

Name33rd International Conference on Machine Learning, ICML 2016
Volume3

Other

Other33rd International Conference on Machine Learning, ICML 2016
CountryUnited States
CityNew York City
Period6/19/166/24/16

ASJC Scopus subject areas

  • Artificial Intelligence
  • Software
  • Computer Networks and Communications

Fingerprint Dive into the research topics of 'A simple and provable algorithm for sparse diagonal CCA'. Together they form a unique fingerprint.

  • Cite this

    Asteris, M., Kyrillidis, A., Koyejo, O., & Poldrack, R. (2016). A simple and provable algorithm for sparse diagonal CCA. In K. Q. Weinberger, & M. F. Balcan (Eds.), 33rd International Conference on Machine Learning, ICML 2016 (pp. 1774-1783). (33rd International Conference on Machine Learning, ICML 2016; Vol. 3). International Machine Learning Society (IMLS).