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

作者：Cai T Tony^*; Zhang Anru

来源：IEEE Transactions on Information Theory, 2014, 60(1): 122-132.

DOI：10.1109/TIT.2013.2288639

• Affine rank minimization
• compressed sensing
• constrained l(1) minimization
• low-rank matrix recovery
• constrained nuclear norm minimization
• restricted isometry
• sparse signal recovery

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, delta(A)(tk)<root(t-1)/t guarantees the exact recovery of all k sparse signals in the noiseless case through the constrained l(1) minimization, and similarly, in affine rank minimization, delta(M)(tr) < root(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 epsilon > 0, delta(A)(tk) < root t-1/t + epsilon 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 delta(A)(tk) < root(t-1)/t and delta(M)(tr) < root(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.

• 出版日期2014-1