 Least-norm dual certificate

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.