Incoherence-Optimal Matrix Completion

Abstract

This paper considers the matrix completion problem. We show that it is not necessary to assume joint incoherence, which is a standard but unintuitive and restrictive condition that is imposed by previous studies. This leads to a sample complexity bound that is order-wise optimal with respect to the incoherence parameter (as well as to the rank r and the matrix dimension n up to a log factor). As a consequence, we improve the sample complexity of recovering a semidefinite matrix from O(nr^2^2n) to O(nr^2n), and the highest allowable rank from (n/ n) to (n/^2n). The key step in proof is to obtain new bounds on the _,2-norm, defined as the maximum of the row and column norms of a matrix. To illustrate the applicability of our techniques, we discuss extensions to SVD projection, structured matrix completion and semi-supervised clustering, for which we provide order-wise improvements over existing results. Finally, we turn to the closely-related problem of low-rank-plus-sparse matrix decomposition. We show that the joint incoherence condition is unavoidable here for polynomial-time algorithms conditioned on the Planted Clique conjecture. This means it is intractable in general to separate a rank-(n) positive semidefinite matrix and a sparse matrix. Interestingly, our results show that the standard and joint incoherence conditions are associated respectively with the information (statistical) and computational aspects of the matrix decomposition problem.

Tasks

Reproductions