S-semigoodness for Low-Rank Semidefinite Matrix Recovery

Abstract

We extend and characterize the concept of s-semigoodness for a sensing matrix in sparse nonnegative recovery (proposed by Juditsky , Karzan and Nemirovski [Math Program, 2011]) to the linear transformations in low-rank semidefinite matrix recovery. We show that ssemigoodnessis not only a necessary and sufficient condition for exact s-rank semidefinitematrix recovery by a semidefinite program, but also provides a stable recovery under someconditions. We also show that both s-semigoodness and semiNSP are equivalent.