Title: The Leave-one-out Approach for Matrix Completion: Primal and Dual Analysis,
Abstract: In this paper, we introduce a powerful technique, Leave-One-Out, to the
analysis of low-rank matrix completion problems. Using this technique, we
develop a general approach for obtaining fine-grained, entry-wise bounds on
iterative stochastic procedures. We demonstrate the power of this approach in
analyzing two of the most important algorithms for matrix completion: the
non-convex approach based on Singular Value Projection (SVP), and the convex
relaxation approach based on nuclear norm minimization (NNM). In particular, we
prove for the first time that the original form of SVP, without re-sampling or
sample splitting, converges linearly in the infinity norm. We further apply our
leave-one-out approach to an iterative procedure that arises in the analysis of
the dual solutions of NNM. Our results show that NNM recovers the true $ d
$-by-$ d $ rank-$ r $ matrix with $\mathcal{O}(\mu^2 r^3d \log d )$ observed
entries, which has optimal dependence on the dimension and is independent of
the condition number of the matrix. To the best of our knowledge, this is the
first sample complexity result for a tractable matrix completion algorithm that
satisfies these two properties simultaneously.