= Solution
Let $S=\operatorname{supp}x$ be the <support of a vector> $x$, with $|S|\le s$. Suppose the <null space property> holds. Every other feasible <vector> is $z=x+v$, where $0\ne v\in\ker A$. Splitting its <L1 norm> over $S$ and $S^c$ and using the <triangle inequality> gives
$$
\|x+v\|_1=\|x_S+v_S\|_1+\|v_{S^c}\|_1\ge\|x\|_1-\|v_S\|_1+\|v_{S^c}\|_1>\|x\|_1.
$$
Thus the <sparse vector> $x$ is the unique <minimizer> in <basis pursuit>. Notice that the argument works for complex coordinates: it uses the <absolute value> inequality, rather than a real <sign function>.
Conversely, suppose <basis pursuit> uniquely recovers every <sparse vector> of order $s$. Fix $0\ne v\in\ker A$ and any $S$ with $|S|\le s$. Take $x=-v_S$ and $z=v_{S^c}$. These <vectors> have the same measurements, because $Av_S+Av_{S^c}=0$, and they are distinct since $z-x=v\ne0$. The <vector> $x$ has at most $s$ nonzero coordinates, so uniqueness gives
$$
\|v_S\|_1=\|x\|_1<\|z\|_1=\|v_{S^c}\|_1.
$$
This is the <null space property> for every such $S$. \b[Uniform unique recovery by <basis pursuit> is equivalent to the order-$s$ <null space property>.]
Back to article page
