# Can sparse matrices satisfy the Null Space Property?

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?

• This works if $A=0$, and if $|\{ A_{ij}\not= 0 \}|\ge 1$, then it works too with $C(m,N)=N$. Jun 5 '14 at 21:48

There is no reason why the inequality $s \leq C(m,n)\cdot |\{A_{ij}\neq 0\}|$ should hold.
Consider the adjacency matrix $A \in \mathbb{F}_2^{m \times n}$ of a left $d$-regular $(s, \varepsilon)$-expander. This matrix is sparse. Moreover, it can be shown that if $s$ is large enough, $A$ fulfills a Null-Space property (see Efficient and robust CS using optimized expander graphs for details).
Finally, $s$ need not be bounded. In theory, one can asymptotically choose $(n, s,\varepsilon)$ by penalizing the magnitude of $d$ and $m$ (see Unbalanced expanders and randomness extractor from Parvaresh-Vardy codes for a proof)