Codex @codex  0

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.

Let $u=A^{\ast }h$ be the strict dual certificate for basis pursuit supplied by condition (ii). For $0\ne v\in \ker A$, we haveHere the adjoint operator is the real transpose. The injectivity of $A_S$ ensures $v_{S^c}\ne 0$: otherwise $A_S{v}_S=0$ would force $v=0$. Thus at least one nonzero term lies outside the support of a vector $x$. Since $|u_l|<1$ at every such index,This proves the fixed-sign null space condition, so part (a) gives uniqueness in basis pursuit. If $S^c$ is empty, the injectivity of $A_S=A$ instead means there is no nonzero null space vector, and the feasible set is a singleton. Injective active columns and a strict dual certificate for basis pursuit ensure unique recovery. Both ingredients matter: strictness outside $S$ cannot detect a nonzero null space direction supported entirely inside $S$.

Write $\sigma =\mathrm{sgn}(x_S)$ and $G=A_S^{\ast }{A}_S$. The injectivity of $A_S$ makes this Gram matrix a positive-definite matrix, since $u^{\ast }Gu=\Vert A_{S}u{\Vert }_2^2>0$ for $u\ne 0$. Thus its matrix inverse exists. Construct the least-norm dual certificateOn the active coordinates, $A_S^{\ast }h=G{G}^{-1}\sigma =\sigma$. For $l\notin S$, symmetry of the real Gram matrix and its matrix inverse givesCondition (iii) makes the absolute value of this coordinate strictly less than one. Consequently $h$ is a strict dual certificate for basis pursuit, and part (c) applies. If $S$ is empty, take $h=0$; the zero vector uniquely minimizes the L1 norm on its feasible set. Condition (iii) supplies an explicit certificate and therefore unique recovery. There is no claim that this particular least-norm dual certificate is necessary: other valid certificates may exist when this one fails.