= Solution
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 yields
$$
\|v_S\|_1<\|v_T\|_1\quad\hbox{and}\quad\|v_T\|_1<\|v_S\|_1,
$$
which is impossible. Hence the <null space> contains no nonzero <sparse vector> of order $2s$.
The feasible <vector> $x$ has $\|x\|_0\le s$, where the <L0 sparsity count> counts its nonzero coordinates. Any different feasible $z$ with $\|z\|_0\le\|x\|_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>. \b[The unique sparsest feasible vector is $x$:]
$$
\boxed{\operatorname*{arg\,min}_{Az=Ax}\|z\|_0=\{x\}.}
$$
This proof does not treat the <L0 sparsity count> as a genuine <norm>; no <triangle inequality> for it is needed.
Back to article page
