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 1


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.

  • $\begingroup$ 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/…. $\endgroup$
    – val
    Jan 31, 2014 at 0:11
  • 1
    $\begingroup$ 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. $\endgroup$
    – lp251
    Jan 31, 2014 at 0:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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