Sharp Restricted Isometry Thresholds for Global Minima of Rank-Restricted Matrix LASSO

We determine the sharp restricted isometry threshold for recovery at global minima of the rank-restricted matrix LASSO. For target rank rstar, if the rank-k RIP constant satisfies δ<δsharp(k/rstar), where δsharp(t)=t/(4-t) for 0<t<4/3 and δsharp(t)=√(t-1)/t for t≥4/3, then every global minimizer has Frobenius error lesssim√rstarλ for all λgtrsim|A*(xi)|op and at every search rank r≥ rstar. The constants depend only on the RIP constant and t=k/rstar, and in particular are independent of the search rank. When the rank restriction is inactive, the result specializes to the ordinary convex matrix LASSO. We also obtain the analogous results for sparsity-restricted vector LASSO. Conversely, we show that the threshold δ<δsharp(k/rstar) cannot be improved, due to the existence of counterexamples whose global minimizers fail to recover the ground truth.