Sharp RIP Bound for Sparse Signal and Low-Rank Matrix Recovery

• Activity Number: 28
• Type: Contributed
• Date/Time: Sunday, July 29, 2012 : 2:00 PM to 3:50 PM
• Sponsor: Section on Nonparametric Statistics
• Author(s): Anru Zhang*+ and Tony Cai
• Companies: University of Pennsylvania and University of Pennsylvania
• Keywords: Compressed sensing ; Dantzig selector ; Low-rank matrix recovery ; restricted isometry ; sparse signal recovery

Abstract

We establish a sharp condition on the restrict isometry property (RIP) for both the sparse signal recovery and low-rank matrix recovery. It is shown that if the measurement matrix A satisfies the RIP condition \delta^A_k < 1/3, then all k-sparse signals beta can be recovered exactly via the constrained l_1 minimization based on y = A\beta. Similarly, if the linear map M satisfies the RIP condition \delta^M_r < 1/3, then all matrices X of rank at most r can be recovered exactly via the constrained nuclear norm minimization based on b = M(X). Furthermore, in both cases it is not possible to do so in general when the condition does not hold. In addition, noisy cases are considered and oracle inequalities are given under the sharp RIP condition. This is joint work with T. Tony Cai.