Noisy Accelerated Power Method for Eigenproblems with Applications
  This paper introduces an efficient algorithm for finding the dominant
generalized eigenvectors of a pair of symmetric matrices. Combining tools from
approximation theory and convex optimization, we develop a simple scalable
algorithm with strong theoretical performance guarantees. More precisely, the
algorithm retains the simplicity of the well-known power method but enjoys the
asymptotic iteration complexity of the powerful Lanczos method. Unlike these
classic techniques, our algorithm is designed to decompose the overall problem
into a series of subproblems that only need to be solved approximately. The
combination of good initializations, fast iterative solvers, and appropriate
error control in solving the subproblems lead to a linear running time in the
input sizes compared to the superlinear time for the traditional methods. The
improved running time immediately offers acceleration for several applications.
As an example, we demonstrate how the proposed algorithm can be used to
accelerate canonical correlation analysis, which is a fundamental statistical
tool for learning of a low-dimensional representation of high-dimensional
objects. Numerical experiments on real-world data sets confirm that our
approach yields significant improvements over the current state-of-the-art.
