4
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • $\begingroup$ This works if $A=0$, and if $|\{ A_{ij}\not= 0 \}|\ge 1$, then it works too with $C(m,N)=N$. $\endgroup$
    – Christian Remling
    Commented Jun 5, 2014 at 21:48

1 Answer 1

Reset to default
2
$\begingroup$

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)

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .