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 constantt≥4/3, in compressed sensing,δₜₖA<√(t-1)/tguarantees the exact recovery of allksparse signals in the noiseless case through the constrained₁minimization, and similarly, in affine rank minimization,δₜᵣM<√(t-1)/tensures the exact reconstruction of all matrices with rank at mostrin the noiseless case via the constrained nuclear norm minimization. In addition, for anyε>0,δₜₖA<√t-1t+εis not sufficient to guarantee the exact recovery of allk-sparse signals for largek. Similar results also hold for matrix recovery. In addition, the conditionsδₜₖA<√(t-1)/tandδₜᵣM<√(t-1)/tare also shown to be sufficient, respectively, for stable recovery of approximately sparse signals and low-rank matrices in the noisy case.