This paper rigorously shows how over-parameterization changes the convergence
behaviors of gradient descent (GD) for the matrix sensing problem, where the
goal is to recover an unknown low-rank ground-truth matrix from near-isotropic
linear measurements. First, we consider the symmetric setting with the
symmetric parameterization where $M^* \in \mathbb{R}^{n \times n}$ is a
positive semi-definite unknown matrix of rank $r \ll n$, and one uses a
symmetric parameterization $XX^\top$ to learn $M^*$. Here $X \in \mathbb{R}^{n
\times k}$ with $k > r$ is the factor matrix. We give a novel $\Omega (1/T^2)$
lower bound of randomly initialized GD for the over-parameterized case ($k >r$)
where $T$ is the number of iterations. This is in stark contrast to the
exact-parameterization scenario ($k=r$) where the convergence rate is $\exp
(-\Omega (T))$. Next, we study asymmetric setting where $M^* \in
\mathbb{R}^{n_1 \times n_2}$ is the unknown matrix of rank $r \ll
\min\{n_1,n_2\}$, and one uses an asymmetric parameterization $FG^\top$ to
learn $M^*$ where $F \in \mathbb{R}^{n_1 \times k}$ and $G \in \mathbb{R}^{n_2
\times k}$. Building on prior work, we give a global exact convergence result
of randomly initialized GD for the exact-parameterization case ($k=r$) with an
$\exp (-\Omega(T))$ rate. Furthermore, we give the first global exact
convergence result for the over-parameterization case ($k>r$) with an
$\exp(-\Omega(\alpha^2 T))$ rate where $\alpha$ is the initialization scale.
This linear convergence result in the over-parameterization case is especially
significant because one can apply the asymmetric parameterization to the
symmetric setting to speed up from $\Omega (1/T^2)$ to linear convergence. On
the other hand, we propose a novel method that only modifies one step of GD and
obtains a convergence rate independent of $\alpha$, recovering the rate in the
exact-parameterization case.

研究论文通过严格的证明展示了过参数化如何改变矩阵感知问题中梯度下降的收敛行为，论文涉及过参数化与称对称参数化以及非对称参数化，提出了线性收敛结果并给出了关键关键字。