期刊
IEEE TRANSACTIONS ON INFORMATION THEORY
卷 61, 期 5, 页码 2909-2923出版社
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TIT.2015.2415195
关键词
Matrix completion; robust PCA; incoherence; computational barrier; nuclear norm minimization
资金
- NSF [EECS-1056028]
- DTRA [HDTRA 1-08-0029]
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 orderwise 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) log(2) n) to O(nr log(2) n), and the highest allowable rank from Theta(root n/log n) to Theta(n/log(2) n). The key step in proof is to obtain new bounds in terms of the l(infinity,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 singular value decomposition projection, structured matrix completion and semisupervised clustering, for which we provide orderwise 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-omega(root 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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据