Sparse Recovery Conditions and Performance Bounds for l(p)-Minimization

In sparse recovery, a sparse signal x is an element of R-N with K nonzero entries is to be reconstructed from a compressed measurement y = Ax with A is an element of R-M x N (M < N). The l(p) (0 <= p < 1) pseudonorm has been found to be a sparsity inducing function superior to the l(1) norm, and the null space constant (NSC) and restricted isometry constant (RIC) have been used as key notions in the performance analyses of the corresponding l(p)-minimization. In this paper, we study sparse recovery conditions and performance hounds for the l(p)-minimization. We devise a new NSC upper bound that outperforms the state-of-the-art result. Based on the improved NSC upper bound, we provide a new RIC upper bound dependent on the sparsity level K as a sufficient condition for precise recovery, and it is tighter than the existing bound for small K. Then, we study the largest choice of p for the l(p)-minimization problem to recover any K-sparse signal, and the largest recoverable K for a fixed p. Numerical experiments demonstrate the improvement of the proposed bounds in the recovery conditions over the up-to-date counterparts.