Sparse Recovery Conditions and Performance Bounds for ℓ_p -Minimization

In sparse recovery, a sparse signal x ∈ ℝ^N with K nonzero entries is to be reconstructedfrom a compressed measurement y = Ax with A ∈ ℝ^M×N (M < N). The ℓ_p (0 ≤ p < 1) pseudonorm has been found to be a sparsity inducing function superior tothe ℓ₁ norm, and the nullspace constant (NSC) and restricted isometry constant (RIC) have been used askey notions in the performance analyses of the corresponding ℓ_p-minimization. In this paper, we study sparserecovery conditions and performance bounds for the ℓ_p-minimization. We devise a new NSC upper bound thatoutperforms 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 thanthe existing bound for small K. Then, we study the largest choice of p for the ℓ_p -minimization problem to recover any K-sparse signal, andthe largest recoverable K for a fixed p. Numerical experiments demonstrate the improvement of the proposed bounds in therecovery conditions over the up-to-date counterparts.