Past exam of the mathematics course of the University of Cambridge / 2013 / iii / Paper 36 / 1 / b

First the null space property implies sparse injectivity. If a nonzero $v\in \ker A$ had at most $2s$ nonzero coordinates, partition its support of a vector into disjoint $S,T$ with $|S|,|T|\le s$. Applying the null space property to each of these sets yieldswhich is impossible. Hence the null space contains no nonzero sparse vector of order $2s$.

The feasible vector $x$ has $\Vert x{\Vert }_0\le s$, where the L0 sparsity count counts its nonzero coordinates. Any different feasible $z$ with $\Vert z{\Vert }_0\le \Vert x{\Vert }_0$ would give a nonzero null space vector $z-x$ with at most $2s$ nonzero coordinates, contrary to sparse injectivity. Consequently every different feasible $z$ has strictly larger L0 sparsity count. The unique sparsest feasible vector is $x$:This proof does not treat the L0 sparsity count as a genuine norm; no triangle inequality for it is needed.