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

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.

It is equivalent to minimize $\Vert z{\Vert }_q$ or its $q$th power $F_q(z)={\sum }_i|z_i{|}^q$, because taking the $q$th root is strictly increasing. For $q<1$, this is an Lq quasi-norm, while $q=1$ gives the L1 norm.

Assume the Lq null space property of order $s$. Let $x$ have support of a vector $S$ with $|S|\le s$, and let $z=x+v$ be any distinct feasible vector. Then $0\ne v\in \ker A$. The triangle inequality for complex magnitudes and the subadditivity $(a+b{)}^q\le a^q+b^q$ giveFor $q=1$ the same inequality follows directly from the triangle inequality. Since $x=0$ off $S$,Thus $x$ is the unique minimizer.

Conversely, suppose every $s$-sparse vector is the unique minimizer for its measurements. Fix $0\ne v\in \ker A$ and any $S$ with $|S|\le s$. The vectors $x=-v_S$ and $z=v_{S^c}$ are distinct and satisfy $Az=Ax$, since $Av=0$. Uniqueness for this $x$ therefore implies $F_q(x)<F_q(z)$, exactly the required strict inequality. HenceThe quantifier is uniform over the entire sparse class. Recovery of one particular signed vector alone would not imply this null space property.

Use the Lq null space property established above. Fix $0\ne v\in \ker A$ and order its magnitudes $a_1\ge \cdots \ge a_N\ge 0$. For a fixed exponent, the sum over the largest $s$ entries is the greatest sum over any support of a vector of size at most $s$, so it suffices to verify the property for this ordered support.

If $s\ge 1$, put $t=a_s$. We have $t>0$: otherwise $v$ would have fewer than $s$ nonzero entries, and applying the Lq null space property to its support would assert a positive number is less than zero. For $0<p<q$, the exponent $p-q$ is negative. ThusThe first inequality uses $a_i\ge t$ on the top part; the last uses $0<a_i\le t$ in the tail. Zero tail entries contribute zero without invoking a negative power of zero. Every other set of size at most $s$ has no larger top sum and no smaller complementary sum, so it too satisfies the strict $p$ inequality. The preceding equivalence provesThis is monotonicity of uniform sparse recovery in the exponent. If $\ker A=\{0\}$ the feasible vector is unique regardless of the objective; if $s=0$, only the zero vector is relevant. These cases need no threshold argument.