= Solution
Write $\sigma=\operatorname{sgn}(x_S)$ and $G=A_S^*A_S$. The <injectivity> of $A_S$ makes this <Gram matrix> a <positive-definite matrix>, since $u^*Gu=\|A_Su\|_2^2>0$ for $u\ne0$. Thus its <matrix inverse> exists. Construct the <least-norm dual certificate>
$$
\boxed{h=A_S(A_S^*A_S)^{-1}\sigma.}
$$
On the active coordinates, $A_S^*h=G G^{-1}\sigma=\sigma$. For $l\notin S$, symmetry of the real <Gram matrix> and its <matrix inverse> gives
$$
(A^*h)_l=a_l^*A_SG^{-1}\sigma=\langle G^{-1}A_S^*a_l,\sigma\rangle.
$$
Condition (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. \b[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.
Back to article page
