Optimal RIP bounds for sparse signals recovery via lp minimization

In this paper, we present a unified analysis of RIP bounds for sparse signals recovery by using l(p) minimization with 0 < p <= 1 and provide optimal RIP bounds which can guarantee sparse signals recovery via l(p) minimization for each p is an element of (0, 1] in both noiseless and noisy settings. It is shown that if the measurement matrix Phi satisfies the RIP condition delta(2k) < delta(p), where delta(p) will be specified in the context, then all k-sparse signals x can be recovered stably via the constrained l(p) minimization based on b = Phi x + z, where z is one type of noise. Furthermore, we show that for any epsilon > 0, delta(2k) < delta(p) + epsilon is not sufficient to guarantee the exact recovery of all k-sparse signals. We also apply the results to the cases of low rank matrix recovery and the reconstruction of sparse vectors in terms of redundant dictionary. In particular, when p = 1, the corresponding constant delta(1) = root 2/2, this sharp bound was shown by T. Cai and A. Zhang in their work. Thus, we give a complete characterization for optimal RIP bounds delta(2k) via l(p) minimization for k-sparse signals recovery with 0 < p <= 1. Our approaches are based on some ideas of sparse representation of a given polytope, which was firstly used by T. Cai and A. Zhang. (C) 2017 Elsevier Inc. All rights reserved.