= Solution
Let $T$ be the <support of a vector> $\hat x$. If the columns indexed by $T$ were linearly dependent, there would be a nonzero $h$ supported in $T$ with $Ah=0$. For sufficiently small real $t$, the nonzero signs of $\hat x_T$ remain fixed, so
$$
\|\hat x+th\|_1=\|\hat x\|_1+t\sum_{j\in T}\operatorname{sgn}(\hat x_j)h_j.
$$
Both positive and negative $t$ preserve the residual and hence feasibility, even with noise. A nonzero slope contradicts minimality in one direction. A zero slope gives distinct minimizers, contradicting uniqueness. Thus those columns are linearly independent, and
$$
\boxed{|\operatorname{supp}\hat x|\le\operatorname{rank}A\le m.}
$$
This proves the <sparse vector> assertion without assuming a noiseless residual.
Back to article page
