TY - GEN

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

AU - Ge, Rong

AU - Jin, Chi

AU - Kakade, Sham

AU - Netrapalli, Praneeth

AU - Sidford, Aaron

PY - 2016

Y1 - 2016

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84998812231&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84998812231&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:84998812231

T3 - 33rd International Conference on Machine Learning, ICML 2016

SP - 4009

EP - 4026

BT - 33rd International Conference on Machine Learning, ICML 2016

A2 - Weinberger, Kilian Q.

A2 - Balcan, Maria Florina

PB - International Machine Learning Society (IMLS)

T2 - 33rd International Conference on Machine Learning, ICML 2016

Y2 - 19 June 2016 through 24 June 2016

ER -