**Definition** A matrix $A \in \mathbb{C}^{m \times N}$ with $m < N$ satisfies the Null Space Property (NSP) of order $s$ if
$$\|x_S\|_1 < \|x_{\bar{S}}\|_1, \quad \forall x \in \ker A \setminus \{0\}, \forall S\subseteq\{1,\ldots,N\} \text{ s.t. } |S| \leq s, $$
where $x_{S} = (x_i)_{i \in S}$.

I think that the NSP order $s$ should be bounded by the sparsity level of $A$. Something like the following inequality should hold: $$s \leq C(m,N) \cdot |\{A_{ij}\neq 0\}|.$$ Does anyone have any reference in this direction?