A graphical approach to the analysis of matrix completion

作者：Sun Tingni; Zhang Cun Hui^*

来源：Stochastic Processes and Their Applications, 2016, 126(12): 3935-3951.

DOI：10.1016/j.spa.2016.04.007

This paper considers the problem of matrix completion, which is to recover a d(1) x d(2) 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 r(2)d log d via a graphical approach, where d = d(1) + d(2) and r is the rank of the target matrix.

• 出版日期2016-12
• 单位rutgers