Abstract
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.
Original language | English (US) |
---|---|
Pages (from-to) | 3935-3951 |
Number of pages | 17 |
Journal | Stochastic Processes and their Applications |
Volume | 126 |
Issue number | 12 |
DOIs | |
State | Published - Dec 1 2016 |
All Science Journal Classification (ASJC) codes
- Statistics and Probability
- Modeling and Simulation
- Applied Mathematics