Noisy Accelerated Power Method for Eigenproblems with Applications
arXiv:1903.08742 · doi:10.1109/TSP.2019.2908126
Abstract
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.
arXiv commentAccepted for publication in the IEEE Transaction on Signal Processing
References in corpus (10)
- SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
- Stochastic Dual Coordinate Ascent Methods for Regularized Loss Minimization
- Angles between subspaces and their tangents
- Un-regularizing: approximate proximal point and faster stochastic algorithms for empirical risk minimization
- Finding Linear Structure in Large Datasets with Scalable Canonical Correlation Analysis
- A Stochastic PCA and SVD Algorithm with an Exponential Convergence Rate
- Faster Eigenvector Computation via Shift-and-Invert Preconditioning
- Fast Stochastic Algorithms for SVD and PCA: Convergence Properties and Convexity
- Accelerated Stochastic Power Iteration
- Doubly Accelerated Methods for Faster CCA and Generalized Eigendecomposition