Skip to main content
MathOverflow

Return to Answer

broken link fixed
Source Link
Glorfindel
Glorfindel
  • 2.8k
  • 6
  • 28
  • 38

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 graphsEfficient 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 codesUnbalanced expanders and randomness extractor from Parvaresh-Vardy codes for a proof)

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)

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)

Source Link
rodms
rodms
  • 409
  • 3
  • 13

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)