= Strict dual certificate for basis pursuit
{title2=$A_S^*h=\operatorname{sgn}(x_S),\quad\|A_{S^c}^*h\|_\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}\ne0$, and $0=\langle A^*h,v\rangle$ 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.
Back to article page
