# 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\}$

## 1 Answer

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.

• I have been reading through your linked material - thank you. Here is what I'm having trouble understanding: Since A is mxN and m<N, say m = 100, N=10000 and s = 3. So are we saying that every and any set of 6 (i.e. 2x3) column vectors in A will be linearly independent?! There are 10000 columns so I'm thinking that some of these columns in a set are bound to be dependent. This is a language problem perhaps. I posted here but did not get a reply: math.stackexchange.com/questions/649656/…. – val Jan 31 '14 at 0:11
• 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