A Caltech Library Service

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

Hou, Thomas Y. and Li, Zhenzhen and Zhang, Ziyun (2020) Fast Global Convergence for Low-rank Matrix Recovery via Riemannian Gradient Descent with Random Initialization. . (Unpublished)

[img] PDF - Submitted Version
Creative Commons Attribution.


Use this Persistent URL to link to this item:


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. O(log(1/ϵ) + log(n)) iterations to reach an ϵ-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.

Item Type:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription Paper
Hou, Thomas Y.0000-0001-6287-1133
Additional Information:Attribution 4.0 International (CC BY 4.0) This research was in part supported by NSF Grants DMS P2259068 and DMS P2259075. We would also like to thank Prof. Jian-feng Cai for helpful suggestions.
Funding AgencyGrant Number
Record Number:CaltechAUTHORS:20221221-220354531
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:118576
Deposited By: George Porter
Deposited On:22 Dec 2022 18:45
Last Modified:02 Jun 2023 01:13

Repository Staff Only: item control page