On the Computational and Statistical Complexity of Over-Parameterized Matrix Sensing


We consider solving the low rank matrix sensing problem with Factorized Gradient Descend (FGD) method when the true rank is unknown and over-specified, which we refer to as over-parameterized matrix sensing. Our results offer a comprehensive picture of the statistical and computational complexity of FGD for the over-parameterized matrix sensing problem.