= Least-norm dual certificate
{title2=$h_0=A_S(A_S^*A_S)^{-1}\operatorname{sgn}(x_S)$}
When $A_S$ is <injective>, this <vector> solves $A_S^*h_0=\operatorname{sgn}(x_S)$. Any other solution differs by a <vector> in $\ker A_S^*$, 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^*h_0$ has magnitude less than one. Failure of that test does not rule out another certificate: a <null space> component of $A_S^*$ can alter those inactive coordinates.
Back to article page
