= Solution
The strict <null space property> of order $s$ is
$$
\boxed{\|v_S\|_1<\|v_{S^c}\|_1\quad\text{for every }0\ne v\in\ker A\text{ and every }|S|\le s.}
$$
Here $v_S$ agrees with $v$ on $S$ and is zero elsewhere. Suppose a nonzero null <vector> had at most $2s$ nonzero entries. Split its <support of a vector> into disjoint sets $S,T$ of size at most $s$. Applying the <null space property> to both sets would give $\|v_S\|_1<\|v_T\|_1$ and $\|v_T\|_1<\|v_S\|_1$, a contradiction. Empty parts cause the same contradiction. Thus no such nonzero null <vector> exists.
For an $s$-sparse $x$, the feasible <vector> $x$ has $\|x\|_0\le s$, where the zero-subscript quantity counts nonzero entries and is not a <norm>. Any feasible competitor $z$ with $\|z\|_0\le\|x\|_0$ also has at most $s$ nonzero entries. The difference $z-x\in\ker A$ has at most $2s$ nonzero entries, so $z=x$. Competitors with larger support have strictly larger objective. Therefore \b[every s-sparse <vector> is the unique sparsest feasible <vector>]. This is <sparse injectivity>; for $s=0$ the only sparse <vector> is zero and the conclusion is immediate.
Back to article page
