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

Abstract

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 leads to 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 _1 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. Moreover, for any >0, _tk^A<t-1t+ is not sufficient to guarantee the exact recovery of all k-sparse signals for large k. Similar result also holds 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.

Tasks

Reproductions