Asymmetric matrix sensing by gradient descent with small random
  initialization
Johan S. Wind
We study matrix sensing, which is the problem of reconstructing a low-rank
matrix from a few linear measurements. It can be formulated as an
overparameterized regression problem, which can be solved by factorized
gradient descent when starting from a small random initialization.
  Linear neural networks, and in particular matrix sensing by factorized
gradient descent, serve as prototypical models of non-convex problems in modern
machine learning, where complex phenomena can be disentangled and studied in
detail. Much research has been devoted to studying special cases of asymmetric
matrix sensing, such as asymmetric matrix factorization and symmetric positive
semi-definite matrix sensing.
  Our key contribution is introducing a continuous differential equation that
we call the $\textit{perturbed gradient flow}$. We prove that the perturbed
gradient flow converges quickly to the true target matrix whenever the
perturbation is sufficiently bounded. The dynamics of gradient descent for
matrix sensing can be reduced to this formulation, yielding a novel proof of
asymmetric matrix sensing with factorized gradient descent. Compared to
directly analyzing the dynamics of gradient descent, the continuous formulation
allows bounding key quantities by considering their derivatives, often
simplifying the proofs. We believe the general proof technique may prove useful
in other settings as well.