 Solution

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.