  Recent advances have shown that implicit bias of gradient descent on
over-parameterized models enables the recovery of low-rank matrices from linear
measurements, even with no prior knowledge on the intrinsic rank. In contrast,
for robust low-rank matrix recovery from grossly corrupted measurements,
over-parameterization leads to overfitting without prior knowledge on both the
intrinsic rank and sparsity of corruption. This paper shows that with a double
over-parameterization for both the low-rank matrix and sparse corruption,
gradient descent with discrepant learning rates provably recovers the
underlying matrix even without prior knowledge on neither rank of the matrix
nor sparsity of the corruption. We further extend our approach for the robust
recovery of natural images by over-parameterizing images with deep
convolutional networks. Experiments show that our method handles different test
images and varying corruption levels with a single learning pipeline where the
network width and termination conditions do not need to be adjusted on a
case-by-case basis. Underlying the success is again the implicit bias with
discrepant learning rates on different over-parameterized parameters, which may
bear on broader applications.
