Past exam of the mathematics course of the University of Cambridge / 2017 / iii / Paper 340 / 3 / a

The strict null space property of order $s$ isHere $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 $\Vert v_S{\Vert }_1<\Vert v_T{\Vert }_1$ and $\Vert v_T{\Vert }_1<\Vert v_S{\Vert }_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 $\Vert x{\Vert }_0\le s$, where the zero-subscript quantity counts nonzero entries and is not a norm. Any feasible competitor $z$ with $\Vert z{\Vert }_0\le \Vert x{\Vert }_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 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.