Matrix Completion via Max-Norm Constrained Optimization
Tony Cai and Wenxin Zhou
-
Abstract:
This paper studies matrix completion under a general sampling model using the max-norm as a convex relaxation for the rank of the matrix. The optimal rate of convergence is established for the Frobenius norm loss. It is shown that the max-norm constrained minimization method is rate-optimal and it yields a more stable approximate recovery guarantee, with respect to the sampling distributions, than previously used trace-norm based approaches. The computational effectiveness of this method is also studied, based on a first-order algorithm for solving convex programs involving a max-norm constraint.
- Paper: pdf file.