Efficient Algorithms for Large-scale Generalized Eigenvector Computation
  and Canonical Correlation Analysis
  This paper considers the problem of canonical-correlation analysis (CCA)
(Hotelling, 1936) and, more broadly, the generalized eigenvector problem for a
pair of symmetric matrices. These are two fundamental problems in data analysis
and scientific computing with numerous applications in machine learning and
statistics (Shi and Malik, 2000; Hardoon et al., 2004; Witten et al., 2009).
  We provide simple iterative algorithms, with improved runtimes, for solving
these problems that are globally linearly convergent with moderate dependencies
on the condition numbers and eigenvalue gaps of the matrices involved.
  We obtain our results by reducing CCA to the top-$k$ generalized eigenvector
problem. We solve this problem through a general framework that simply requires
black box access to an approximate linear system solver. Instantiating this
framework with accelerated gradient descent we obtain a running time of
$O(\frac{z k \sqrt{\kappa}}{\rho} \log(1/\epsilon) \log
\left(k\kappa/\rho\right))$ where $z$ is the total number of nonzero entries,
$\kappa$ is the condition number and $\rho$ is the relative eigenvalue gap of
the appropriate matrices.
  Our algorithm is linear in the input size and the number of components $k$ up
to a $\log(k)$ factor. This 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 and ultimately improve the practical running time for
performing these important data analysis procedures on large data sets.
