Sparse Recovery Conditions and Performance Bounds for ℓ_p-Minimization

In sparse recovery, a sparse signal x ∈ ℝ^N with K nonzero entries is to be reconstructed from a compressed measurement = Ax with A ∈ ℝ^M×N (M <N). The ℓ_p (0 ≤ p < 1) pseudonorm has been found to be a sparsity inducing function superior to the ℓ₁ 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 ℓ_p-minimization. In this paper, we study sparse recovery conditions and performance bounds for the ℓ_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 ℓ_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.