Coherent matrix completion

Rachel Ward - University of Texas
Jan 29 2014 - 3:00pm
Event type: 
110 Fine Hall

Matrix completion concerns the recovery of a low-rank matrix
from a subset of its revealed entries, and nuclear norm minimization has
emerged as an effective surrogate for this combinatorial problem. In this
talk, we show that nuclear norm minimization can recover an arbitrary n by
n matrix of rank r from O(nr log^2(n)) revealed entries, provided that
revealed entries are drawn proportionally to the row and column leverage
scores of the underlying matrix. Our results are order-optimal up to
logarithmic factors, and extend existing results for nuclear norm
minimization which require strong incoherence conditions on the types of
matrices that can be recovered, due to assumed uniformly distributed
revealed entries. We further provide extensive numerical evidence that a
proposed two-phase sampling algorithm can perform nearly as well as
leverage-score sampling and without requiring any prior knowledge of the
matrix coherence structure.
This is joint work with Srinadh Bhojanapalli, Yudong Chen, and Sujay Sanghavi