# recovery of sparse vectors

When looking for a sparse solution to $\ Az = y$, under what condition(s) does the nullspace $\ N(A)$ of a matrix $\ A$ not contain any $\ 2s$-sparse vector other than the zero vector, i.e $\ N(A) \cap \{z \in \mathbb{R}^N: \|z\|_0 \le 2s\} = \{0\}$

The simplest answer- when every set of $2s$ columns of $A$ are linearly independent.
That's not a practically useful answer, though, because it requires testing every set of $2s$ columns for independence. Some other conditions to consider- the null space property, the restricted isometry property, and conditions based on mutual coherence.
Section 2 of the paper Compressive Sensing and Structured Random Matrices provides a good overview, although it is primarily focused on sparse recovery bel $\ell_1$ minimization.
• No, that is exactly the condition you need. If there is a linearly dependent set of 2s columns, we could find a 2s-sparse vector $z$ such that Az = 0. This is why only 'special' matrices work for sparse recovery. – lp251 Jan 31 '14 at 0:30