Fast Global Convergence for Low-rank Matrix Recovery via Riemannian Gradient Descent with Random Initialization

Abstract

In this paper, we propose a new global analysis framework for a class of low-rank matrix recovery problems on the Riemannian manifold. We analyze the global behavior for the Riemannian optimization with random initialization. We use the Riemannian gradient descent algorithm to minimize a least squares loss function, and study the asymptotic behavior as well as the exact convergence rate. We reveal a previously unknown geometric property of the low-rank matrix manifold, which is the existence of spurious critical points for the simple least squares function on the manifold. We show that under some assumptions, the Riemannian gradient descent starting from a random initialization with high probability avoids these spurious critical points and only converges to the ground truth in nearly linear convergence rate, i.e. $\mathcal{O}(\text{log}(\frac{1}{\epsilon })+\text{log}(n))$ iterations to reach an $\epsilon$-accurate solution. We use two applications as examples for our global analysis. The first one is a rank-1 matrix recovery problem. The second one is a generalization of the Gaussian phase retrieval problem. It only satisfies the weak isometry property, but has behavior similar to that of the first one except for an extra saddle set. Our convergence guarantee is nearly optimal and almost dimension-free, which fully explains the numerical observations. The global analysis can be potentially extended to other data problems with random measurement structures and empirical least squares loss functions.

References in corpus (8)

• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• Gradient Descent Converges to Minimizers
• First-order Methods Almost Always Avoid Saddle Points
• Gradient Descent Only Converges to Minimizers: Non-Isolated Critical Points and Invariant Regions
• Exact Guarantees on the Absence of Spurious Local Minima for Non-negative Rank-1 Robust Principal Component Analysis
• Solving systems of phaseless equations via Riemannian optimization with optimal sampling complexity
• Analysis of Asymptotic Escape of Strict Saddle Sets in Manifold Optimization

Cited by in corpus (9)

• Finding stationary points on bounded-rank matrices: A geometric hurdle and a smooth remedy
• Small random initialization is akin to spectral learning: Optimization and generalization guarantees for overparameterized low-rank matrix reconstruction
• Low-rank Tensor Estimation via Riemannian Gauss-Newton: Statistical Optimality and Second-Order Convergence
• Riemannian Perspective on Matrix Factorization
• Analysis of Asymptotic Escape of Strict Saddle Sets in Manifold Optimization
• Asymptotic Escape of Spurious Critical Points on the Low-rank Matrix Manifold
• Nonconvex Factorization and Manifold Formulations are Almost Equivalent in Low-rank Matrix Optimization
• Sign-RIP: A Robust Restricted Isometry Property for Low-rank Matrix Recovery
• On Geometric Connections of Embedded and Quotient Geometries in Riemannian Fixed-rank Matrix Optimization