Global Convergence of a Grassmannian Gradient Descent Algorithm for Subspace Estimation
arXiv:1506.07405
Abstract
It has been observed in a variety of contexts that gradient descent methods have great success in solving low-rank matrix factorization problems, despite the relevant problem formulation being non-convex. We tackle a particular instance of this scenario, where we seek the -dimensional subspace spanned by a streaming data matrix. We apply the natural first order incremental gradient descent method, constraining the gradient method to the Grassmannian. In this paper, we propose an adaptive step size scheme that is greedy for the noiseless case, that maximizes the improvement of our metric of convergence at each data index , and yields an expected improvement for the noisy case. We show that, with noise-free data, this method converges from any random initialization to the global minimum of the problem. For noisy data, we provide the expected convergence rate of the proposed algorithm per iteration.
23 pages, 10 figures
References in corpus (2)
Cited by in corpus (12)
- Global Optimality of Local Search for Low Rank Matrix Recovery
- Dropping Convexity for Faster Semi-definite Optimization
- Grassmannian Optimization for Online Tensor Completion and Tracking with the t-SVD
- A Well-Tempered Landscape for Non-convex Robust Subspace Recovery
- Provable Subspace Tracking from Missing Data and Matrix Completion
- The local convexity of solving systems of quadratic equations
- Subspace Estimation from Incomplete Observations: A High-Dimensional Analysis
- Federated Over-Air Subspace Tracking from Incomplete and Corrupted Data
- MOSES: A Streaming Algorithm for Linear Dimensionality Reduction
- Distributed Stochastic Algorithms for High-rate Streaming Principal Component Analysis
- Subspace Clustering using Ensembles of -Subspaces
- Sequential (Quickest) Change Detection: Classical Results and New Directions