Sparse Representation of a Polytope and Recovery of Sparse Signals and Low-Rank Matrices

This paper considers compressed sensing and affine rank minimization in both noiseless and noisy cases and establishes sharp restricted isometry conditions for sparse signal and low-rank matrix recovery. The analysis relies on a key technical tool, which represents points in a polytope by convex combinations of sparse vectors. The technique is elementary while yielding sharp results. It is shown that for any given constant t ≥ 4/3, in compressed sensing, δ_tk^A <; √((t-1)/t) guarantees the exact recovery of all k sparse signals in the noiseless case through the constrained l₁ minimization, and similarly, in affine rank minimization, δ_tr^M <; √((t-1)/t) ensures the exact reconstruction of all matrices with rank at most r in the noiseless case via the constrained nuclear norm minimization. In addition, for any ε > 0, δ_tk^A <; √(^t-1/_t) + ε is not sufficient to guarantee the exact recovery of all k-sparse signals for large k. Similar results also hold for matrix recovery. In addition, the conditions δ_tk^A <; √((t-)1/t) and δ_tr^M <; √((t-1)/t) are also shown to be sufficient, respectively, for stable recovery of approximately sparse signals and low-rank matrices in the noisy case.