  Recently, there has been significant progress in understanding the
convergence and generalization properties of gradient-based methods for
training overparameterized learning models. However, many aspects including the
role of small random initialization and how the various parameters of the model
are coupled during gradient-based updates to facilitate good generalization
remain largely mysterious. A series of recent papers have begun to study this
role for non-convex formulations of symmetric Positive Semi-Definite (PSD)
matrix sensing problems which involve reconstructing a low-rank PSD matrix from
a few linear measurements. The underlying symmetry/PSDness is crucial to
existing convergence and generalization guarantees for this problem. In this
paper, we study a general overparameterized low-rank matrix sensing problem
where one wishes to reconstruct an asymmetric rectangular low-rank matrix from
a few linear measurements. We prove that an overparameterized model trained via
factorized gradient descent converges to the low-rank matrix generating the
measurements. We show that in this setting, factorized gradient descent enjoys
two implicit properties: (1) coupling of the trajectory of gradient descent
where the factors are coupled in various ways throughout the gradient update
trajectory and (2) an algorithmic regularization property where the iterates
show a propensity towards low-rank models despite the overparameterized nature
of the factorized model. These two implicit properties in turn allow us to show
that the gradient descent trajectory from small random initialization moves
towards solutions that are both globally optimal and generalize well.
