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?

  • $\begingroup$ This works if $A=0$, and if $|\{ A_{ij}\not= 0 \}|\ge 1$, then it works too with $C(m,N)=N$. $\endgroup$ 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)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.