  In this paper, we study the problem of recovering a low-rank matrix from a
number of noisy random linear measurements. We consider the setting where the
rank of the ground-truth matrix is unknown a prior and use an overspecified
factored representation of the matrix variable, where the global optimal
solutions overfit and do not correspond to the underlying ground-truth. We then
solve the associated nonconvex problem using gradient descent with small random
initialization. We show that as long as the measurement operators satisfy the
restricted isometry property (RIP) with its rank parameter scaling with the
rank of ground-truth matrix rather than scaling with the overspecified matrix
variable, gradient descent iterations are on a particular trajectory towards
the ground-truth matrix and achieve nearly information-theoretically optimal
recovery when stop appropriately. We then propose an efficient early stopping
strategy based on the common hold-out method and show that it detects nearly
optimal estimator provably. Moreover, experiments show that the proposed
validation approach can also be efficiently used for image restoration with
deep image prior which over-parameterizes an image with a deep network.
