Nullspace property

The null space property relative to $S$ is $\Vert h_S{\Vert }_1<\Vert h_{S^c}{\Vert }_1$ for every nonzero $h\in \ker A$. It is equivalent to exact basis pursuit recovery of every vector supported in $S$. Sufficiency follows from the triangle inequality; for necessity, compare $-h_S$ and $h_{S^c}$, which have the same image under $A$. Recovery of a single fixed signed vector can hold without this uniform property.

For $0<q\le 1$, this strict inequality for every nonzero $v\in \ker A$ and every $|S|\le s$ is equivalent to unique constrained ${\ell }^q$ recovery of every sparse vector of order $s$. For sufficiency, use $|x_i+v_i{|}^q\ge |x_i{|}^q-|v_i{|}^q$ on the support of a vector. For necessity compare $x=-v_S$ with $v_{S^c}$, which have the same measurements. The statement concerns uniform recovery over the whole sparse class, rather than a single signed vector.

If the Lq null space property holds at $q\le 1$, it holds at every $0<p<q$. Order a nonzero null vector's magnitudes $a_1\ge \cdots \ge a_N$ and put $t=a_s>0$. Since $p-q<0$, the top-$s$ $p$-power sum is at most $t^{p-q}$ times its $q$-power sum, while the tail $p$-power sum is at least that multiple of the tail $q$-power sum. The strict $q$ inequality therefore gives the strict $p$ inequality. The largest $s$ magnitudes are the worst support of a vector, so all other supports satisfy it too.

The displayed property holds for every $h$ and every $|S|\le s$, with $0\le \rho <1$ and $\tau >0$. It converts the cone inequality from basis pursuit minimality and the tube inequality from noisy feasibility into a two-constant bound $\Vert \hat{x}-x_0{\Vert }_2\le C_1\eta +C_2{\sigma }_s(x_0)/\sqrt{s}$. Both constants are needed in general; a fixed coefficient one on the approximation term does not follow.

For a real vector $x_0$ with support $S$, uniqueness in basis pursuit is equivalent to $|⟨\mathrm{sgn}(x_{0,S}),h_S⟩|<\Vert h_{S^c}{\Vert }_1$ for every nonzero $h\in \ker A$. The supporting-line inequality for the absolute value proves sufficiency. Taking small positive and negative multiples of $h$ before any active sign changes proves necessity.