no $k$-sparse vector in null space of $A$ where $y=Ax$

Question

Here is a part of my notes on compressed sensing. Suppose we are given an underdetermined linear system of equations $Y=AX$. For a unique solution,

What we need:

subtraction of no two $k$-sparse vectors ($x_1$, $x_2$) must be in nullspace of $A$.

What is required for the following to hold:

since the subtraction of two $k$-sparse vectors is at most $2k$-sparse, $2k$ columns of the matrix must be linearly independent then no $k$-sparse vector will be in null space of $A$.

I don't understand the part where a connection between sparsity and the columns of the matrix being linearly independent is made. An explanation would be great.

Answer 1

The $k$-sparse solution of the underdetermined system is unique if ... (each of the two given statements)

subtraction of no two $k$-sparse vectors ($x_1$, $x_2$) is in nullspace of $A$.

Assume $\mathbf{y}=\mathbf{A}\mathbf{x}_1$ and $\mathbf{y}=\mathbf{A}\mathbf{x}_2$, and $\mathbf{x}_1$ and $\mathbf{x}_1$ are $k$-sparse vectors.

Obviously, in order to the system $\mathbf{y}=\mathbf{A}\mathbf{x}$ have a unique $k$-sparse solution, we should have $\mathbf{x}_1=\mathbf{x}_2$. This implies $\mathbf{A}\mathbf{x}_1=\mathbf{A}\mathbf{x}_2$, or $$\mathbf{A}(\mathbf{x}_1-\mathbf{x}_2)=\mathbf{0} \hspace{1cm}(1)$$ Now since both $\mathbf{x}_1$ and $\mathbf{x}_2$ are $k$-sparse, then $\mathbf{x}_1-\mathbf{x}_2$ would be $2k$-sparse at most. If the nullspace of $A$ contains no $2k$-sparse vectors, then only zero vector solves system $(1)$, i.e., $\mathbf{x}_1-\mathbf{x}_2=\mathbf{0}$, or $\mathbf{x}_1=\mathbf{x}_2$ which is the desired.

This is equivalent to claim that

every set of $2k$ columns of $\mathbf{A}$ is linearly independent.

To prove it, assume $S$ is the support of the $2k$-sparse vector $\mathbf{z}=\mathbf{x}_1-\mathbf{x}_2$ (i.e. $S$ contains the nonzero indices of $\mathbf{z}$). Then $\mathbf{A}\mathbf{z}=\mathbf{A}_S\mathbf{z}_S=\mathbf{0}$ where $\mathbf{A}_S$ is a submatrix of $\mathbf{A}$ with columns indicated by $S$ (since other elements of $\mathbf{z}$ are zero). If the columns of $\mathbf{A}_S$ are linearly independent, then $\mathbf{z}_S=\mathbf{0}$ is the unique solution (consequently). Note thet $|S|=2k$ and therefore, $\mathbf{A}_S$ has $2k$ columns. The fact that $S$ is the set of all combinations of indices with cardinality $2k$ and $\mathbf{z}$ can be all possible $2k$-sparse vectors yields the expected conclusion.

Answer 2

I presume the formulation should be that every 2k columns of $A$ should be linearly independent, as this implies that there are no 2k sparse vector in the null space:

To see this, denote $(\vec{a}_1,...,\vec{a}_N)$ the column vectors of $A$ and let $X$ be a 2k-sparse vector, i.e. there are at most $2k$ nonvanishing components of $X$. This means that there is a set of at most 2k indices $i_1,\ldots,i_m$, with $m\leq 2k$ so that every component of $X$ outside this set vanishes. In order for $X$ to be in the kernel of $A$ we must have: $$ AX = \sum_{j=1}^m \vec{a}_{i_j} x_{i_j}=0 $$ But as every collecting of at most $2k$ vectors of $A$ are assumed linearly independent we must have every $x_{i_1}=...=x_{i_m}=0$. So every component of $X$ vanishes and $X$ was the zero vector.