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.

本文提出了一种适用于 Riemann 流形上低秩矩阵恢复问题的新的全局分析框架，其中使用 Riemann 梯度下降算法最小化最小二乘损失函数，并研究了渐近行为以及精确收敛速率。