= Solution
It is equivalent to minimize $\|z\|_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$ give
$$
|x_i|^q\le(|x_i+v_i|+|v_i|)^q\le|x_i+v_i|^q+|v_i|^q.
$$
For $q=1$ the same inequality follows directly from the <triangle inequality>. Since $x=0$ off $S$,
$$
F_q(x+v)\ge F_q(x)-\sum_{i\in S}|v_i|^q+\sum_{i\notin S}|v_i|^q>F_q(x).
$$
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. Hence
$$
\boxed{\text{uniform unique }s\text{-sparse }\ell^q\text{ recovery}\ \Longleftrightarrow\ \sum_{i\in S}|v_i|^q<\sum_{i\notin S}|v_i|^q\quad(0\ne v\in\ker A,\ |S|\le s).}
$$
The quantifier is uniform over the entire sparse class. Recovery of one particular signed <vector> alone would not imply this <null space property>.
Back to article page
