TY - JOUR
T1 - A graphical approach to the analysis of matrix completion
AU - Sun, Tingni
AU - Zhang, Cun Hui
N1 - Funding Information:
The research of Cun-Hui Zhang was supported in part by the NSF Grants DMS-12-09014 and DMS-15-13378 and NSA Grant H98230-15-1-0040 .
Publisher Copyright:
© 2016 Elsevier B.V.
PY - 2016/12/1
Y1 - 2016/12/1
N2 - This paper considers the problem of matrix completion, which is to recover a d1×d2 matrix from observations in a small proportion of indices. We study the nuclear norm minimization method with the restriction of matching the observed entries. Under certain coherence conditions, we prove that the required sample size is of order r2dlogd via a graphical approach, where d=d1+d2 and r is the rank of the target matrix.
AB - This paper considers the problem of matrix completion, which is to recover a d1×d2 matrix from observations in a small proportion of indices. We study the nuclear norm minimization method with the restriction of matching the observed entries. Under certain coherence conditions, we prove that the required sample size is of order r2dlogd via a graphical approach, where d=d1+d2 and r is the rank of the target matrix.
UR - http://www.scopus.com/inward/record.url?scp=84978881243&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84978881243&partnerID=8YFLogxK
U2 - 10.1016/j.spa.2016.04.007
DO - 10.1016/j.spa.2016.04.007
M3 - Article
AN - SCOPUS:84978881243
SN - 0304-4149
VL - 126
SP - 3935
EP - 3951
JO - Stochastic Processes and their Applications
JF - Stochastic Processes and their Applications
IS - 12
ER -