Analysis of the equivalence relationship between l 0 $l_{0}$ -minimization and l p $l_{p}$ -minimization

Abstract

Abstract In signal processing theory, l 0 $l_{0}$ -minimization is an important mathematical model. Unfortunately, l 0 $l_{0}$ -minimization is actually NP-hard. The most widely studied approach to this NP-hard problem is based on solving l p $l_{p}$ -minimization ( 0 < p ≤ 1 $0< p\leq1$ ). In this paper, we present an analytic expression of p ∗ ( A , b ) $p^{\ast}(A,b)$ , which is formulated by the dimension of the matrix A ∈ R m × n $A\in\mathbb{R}^{m\times n}$ , the eigenvalue of the matrix A T A $A^{T}A$ , and the vector b ∈ R m $b\in\mathbb{R}^{m}$ , such that every k-sparse vector x ∈ R n $x\in\mathbb{R}^{n}$ can be exactly recovered via l p $l_{p}$ -minimization whenever 0 < p < p ∗ ( A , b ) $0< p< p^{\ast}(A,b)$ , that is, l p $l_{p}$ -minimization is equivalent to l 0 $l_{0}$ -minimization whenever 0 < p < p ∗ ( A , b ) $0< p< p^{\ast}(A,b)$ . The superiority of our results is that the analytic expression and each its part can be easily calculated. Finally, we give two examples to confirm the validity of our conclusions.

Keywords

• sparse recovery
• null space constant
• null space property
• l 0 $l_{0}$ -minimization
• l p $l_{p}$ -minimization