Strict dual certificate for basis pursuit ($A_S^{\ast }h=\mathrm{sgn}(x_S),\Vert A_{S^c}^{\ast }h{\Vert }_{\infty }<1$)

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.