Performance analysis for matrix completion via iterative hard-thresholded SVD

The matrix completion problem addresses the recovery of a low-rank matrix from a subset of its entries. In this paper, we analyze rank-r matrix completion algorithm based on the rank-r singular value decomposition (SVD). We introduce the doubly-restricted contraction constant (DRCC), a characteristic of a matrix, which predicts the feasibility of matrix recovery from a subset of its entries. We establish results regarding the convergence rate of the algorithm using the DRCC. Numerical experiments indicate that the DRCC accurately predicts the recovery of a matrix from a subset of its entries.