On the Null Space Constant for ${\ell _p}$ Minimization

The literature on sparse recovery often adopts the ${\ell _p}$ “norm” ( $p \in [0,1]$ ) as the penalty to induce sparsity of the signal satisfying an underdetermined linear system. The performance of the corresponding ${\ell _p}$ minimization problem can be characterized by its null space constant. In spite of the NP-hardness of computing the constant, its properties can still help in illustrating the performance of ${\ell _p}$ minimization. In this letter, we show the strict increase of the null space constant in the sparsity level $k$ and its continuity in the exponent $p$ . We also indicate that the constant is strictly increasing in $p$ with probability 1 when the sensing matrix ${\bf A}$ is randomly generated. Finally, we show how these properties can help in demonstrating the performance of ${\ell _p}$ minimization, mainly in the relationship between the the exponent $p$ and the sparsity level $k$ .