Efficient algorithms for large-scale generalized eigenvector computation and canonical correlation analysis

Rong Ge, Chi Jin, Sham Kakade, Praneeth Netrapalli, Aaron Sidford

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

12 Scopus citations

Abstract

This paper considers the problem of canonical- correlation analysis, and more broadly, the generalized eigenvector problem for a pair of symmetric matrices. We consider the setting of finding top-A- canonical/eigen subspace, and solve these problems through a general framework that simply requires black box access to an approximate linear system solver. Instantiating this framework with acceleratcd gradient descent we obtain a running time of O log(l/) log (∗ κ/p)) where z is the total number of nonzero entries, κ is the condition number and p is the relative eigenvalue gap of the appropriate matrices. Our algorithm is linear in the input size and the number of components κup to a iog( κ) factor, which is essential for handling large-scale matrices that appear in practice. To the best of our knowledge this is the first such algorithm with global linear convergence. We hope that our results prompt further research improving the practical running time for performing these important data analysis procedures on large-scale data sets.

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)
Pages4009-4026
Number of pages18
ISBN (Electronic)9781510829008
StatePublished - Jan 1 2016
Externally publishedYes
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
Volume6

Other

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

All Science Journal Classification (ASJC) codes

  • Artificial Intelligence
  • Software
  • Computer Networks and Communications

Fingerprint Dive into the research topics of 'Efficient algorithms for large-scale generalized eigenvector computation and canonical correlation analysis'. Together they form a unique fingerprint.

  • Cite this

    Ge, R., Jin, C., Kakade, S., Netrapalli, P., & Sidford, A. (2016). Efficient algorithms for large-scale generalized eigenvector computation and canonical correlation analysis. In K. Q. Weinberger, & M. F. Balcan (Eds.), 33rd International Conference on Machine Learning, ICML 2016 (pp. 4009-4026). (33rd International Conference on Machine Learning, ICML 2016; Vol. 6). International Machine Learning Society (IMLS).