= Solution
Let $u=A^*h$ be the <strict dual certificate for basis pursuit> supplied by condition (ii). For $0\ne v\in\ker A$, we have
$$
0=\langle h,Av\rangle=\langle A^*h,v\rangle=\langle\operatorname{sgn}(x_S),v_S\rangle+\sum_{l\in S^c}u_l v_l.
$$
Here the <adjoint operator> is the real transpose. The <injectivity> of $A_S$ ensures $v_{S^c}\ne0$: otherwise $A_Sv_S=0$ would force $v=0$. Thus at least one nonzero term lies outside the <support of a vector> $x$. Since $|u_l|<1$ at every such index,
$$
|\langle\operatorname{sgn}(x_S),v_S\rangle|=\left|\sum_{l\in S^c}u_l v_l\right|\le\sum_{l\in S^c}|u_l|\,|v_l|<\sum_{l\in S^c}|v_l|.
$$
This proves the <fixed-sign null space condition>, so part (a) gives uniqueness in <basis pursuit>. If $S^c$ is empty, the <injectivity> of $A_S=A$ instead means there is no nonzero <null space> <vector>, and the feasible set is a singleton. \b[<Injective> active columns and a <strict dual certificate for basis pursuit> ensure unique recovery.] Both ingredients matter: strictness outside $S$ cannot detect a nonzero <null space> direction supported entirely inside $S$.
Back to article page
