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

We consider solving the low-rank matrix sensing problem with the Factorized Gradient Descent (FGD) method when the specified rank is larger than the true rank. We refer to this as over-parameterized matrix sensing. If the ground truth signal X * is an element of R (d x d) is of rank r, but we try to recover it using FF (T) where F is an element of R (d x k) and k > r, the existing statistical analysis either no longer holds or produces a vacuous statistical error upper bound (infinity) due to the flat local curvature of the loss function around the global maxima. By decomposing the factorized matrix F into separate column spaces to capture the impact of using k > r, we show that || F (t) F (t) - X * ||(F) (2) converges sub-linearly to a statistical error of (O) over tilde ( kd sigma (2) /n ) after (O) over tilde ( sigma r /sigma root n/ d ) iterations, where F (t) is the output of FGD after t iterations, sigma (2) is the sigma variance of the observation noise, sigma (r) is the r-th largest eigenvalue of X * , and n is the number of samples. With a precise characterization of the convergence behavior and the statistical error, our results, therefore, offer a comprehensive picture of the statistical and computational complexity if we solve the over-parameterized matrix sensing problem with FGD.