Bridging matrix recovery gaps using manifolds

01/31/2012 - 12:15pm
01/31/2012 - 1:10pm
Deanna Needell (CMC)

Low-rank matrix recovery addresses the problem of recovering an unknown low-rank matrix from few linear measurements. Nuclear-norm minimization is a tractable approach with a recent surge of strong theoretical backing. Analagous to the theory of compressed sensing, these results have required random measurements. Using basic theory of manifolds, we address the theoretical question of how many measurements are needed via any method whatsoever — tractable or not. We compare our result with the best known results for guaranteed recovery using tractable methods. Surprisingly, the gap between tractability and intractability is not as large as one might think!

Millikan 208 (Pomona College)