Basis pursuit ($\min \{\Vert x{\Vert }_1:Ax=y\}$)

Basis pursuit minimizes an ${\ell }^1$ norm subject to exact linear measurements. Basis pursuit with a noise tolerance replaces the equality by $\Vert Ax-y{\Vert }_2\le \eta$. A unique minimizer has linearly independent active columns, and hence at most $\mathrm{rank}A$ nonzero coordinates: a null direction on its support would make the objective locally affine on a feasible line, contradicting minimality or uniqueness.

For a real vector $x$ with support of a vector $S$, this certificate is a vector $h$ whose measurements under the adjoint operator match the active sign function values and lie strictly between minus one and one on the inactive coordinates. If $A_S$ is injective, such a certificate proves that $x$ is the unique basis pursuit minimizer. For a nonzero $v\in \ker A$, injectivity ensures $v_{S^c}\ne 0$, and $0=⟨A^{\ast }h,v⟩$ implies the fixed-sign null space condition. The strict inequality is interpreted coordinatewise if $S^c$ is empty. The condition with the sign function written here is for real variables; complex basis pursuit uses the unit phases of active coordinates instead.

When $A_S$ is injective, this vector solves $A_S^{\ast }{h}_0=\mathrm{sgn}(x_S)$. Any other solution differs by a vector in $\ker A_S^{\ast }$, orthogonal to the range of $A_S$ containing $h_0$. The Pythagorean identity therefore proves that $h_0$ has the smallest Euclidean norm. It is a strict dual certificate for basis pursuit exactly when each inactive coordinate of $A^{\ast }{h}_0$ has magnitude less than one. Failure of that test does not rule out another certificate: a null space component of $A_S^{\ast }$ can alter those inactive coordinates.

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.