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. If the ground truth signal ${\mathbf{X}}^{\ast }\in {\mathbb{R}}^{d\ast d}$ is of rank $r$, but we try to recover it using $\mathbf{F}{\mathbf{F}}^{\mathrm{\top }}$ where $$\mathbf{F}$ \in $\mathbb{R}$^{dk}$and$k>r$, the existing statistical analysis falls short, due to a flat local curvature of the loss function around the global maxima. By decomposing the factorized matrix $\mathbf{F}$ into separate column spaces to capture the effect of extra ranks, we show that $|$\mathbf{F}$_t $\mathbf{F}$_t - $\mathbf{X}$^|{F}^2$convergestoastatisticalerrorof$\tilde{$\mathcal{O}$} ({k d \sigma^2/n})$after$\tilde{$\mathcal{O}$}(\frac{\sigma{r}}{\sigma}\sqrt{\frac{n}{d}})$ number of iterations where ${\mathbf{F}}_t$ is the output of FGD after $t$ iterations, ${\sigma }^2$ is the variance of the observation noise, ${\sigma }_r$ is the $r$-th largest eigenvalue of ${\mathbf{X}}^{\ast }$, and $n$ is the number of sample. Our results, therefore, offer a comprehensive picture of the statistical and computational complexity of FGD for the over-parameterized matrix sensing problem.