= Solution
Use the stated characterization by the <Lq null space property>. Raising an <Lq quasi-norm> comparison to its positive exponent preserves its order, so the hypothesis at $q$ says that, for every nonzero $v\in\ker A$ and every $|S|\le s$,
$$
\sum_{j\in S}|v_j|^q<\sum_{j\notin S}|v_j|^q.
$$
We prove the corresponding $p$ inequality; this is <monotonicity of uniform sparse recovery in the exponent>.
Fix a nonzero <null space> <vector> and arrange its coordinate magnitudes as $a_1\ge\cdots\ge a_N\ge0$. Assume $s\ge1$. The <Lq null space property> rules out a nonzero <null space> <vector> supported on at most $s$ coordinates, so $s<N$ and $t=a_s>0$. Since $p-q<0$, the factors $a_j^{p-q}$ are at most $t^{p-q}$ for $j\le s$ and at least $t^{p-q}$ for $j>s$ with $a_j>0$. Terms with $a_j=0$ contribute zero and require no negative power of zero. Thus
$$
\sum_{j=1}^s a_j^p\le t^{p-q}\sum_{j=1}^s a_j^q<t^{p-q}\sum_{j=s+1}^N a_j^q\le\sum_{j=s+1}^N a_j^p.
$$
The largest $s$ coordinates maximize the $p$-power sum on any set of size at most $s$. Its complement therefore has the smallest complementary $p$-power sum. The displayed strict inequality proves the <Lq null space property> at exponent $p$ for every allowed <support of a vector>. The stated recovery characterization now applies to the <Lq quasi-norm> at $p$.
If $\ker A=\{0\}$, the measurement constraint already singles out $x$, for every objective; if $s=0$, only the zero <sparse vector> needs recovery. These cases do not need a positive threshold. \b[Uniform recovery at $q$ implies uniform recovery at every $0<p<q$:]
$$
\boxed{q\text{-recovery of order }s\ \Longrightarrow\ p\text{-recovery of order }s.}
$$
Back to article page
