Sparse recovery and nullspace certificates

Let $S:=\{j\in [n]:x_j^{†}\mathrm{\ne }0\}$, so $\mathrm{\mid }S\mathrm{\mid }\le s$. For any feasible $z\mathrm{\ne }{x}^{†}$, put $h:=z-x^{†}$. For each row $i$, [F5] and [F6] give $(Ah{)}_i={\sum }_{j=1}^n{A}_{ij}(z_j-x_j^{†})={\sum }_{j=1}^n{A}_{ij}{z}_j-{\sum }_{j=1}^n{A}_{ij}{x}_j^{†}=(Az{)}_i-(A{x}^{†}{)}_i=0$, so $h\in \ker A$ and $h\mathrm{\ne }0$. Hence [F1] gives $\mathrm{\parallel }{h}_S{\mathrm{\parallel }}_1<\mathrm{\parallel }{h}_{S^c}{\mathrm{\parallel }}_1$.

By [F3], $\mathrm{\parallel }\cdot {\mathrm{\parallel }}_1$ is a norm, so [F4] gives its triangle inequality. On $S$, $z_S=x_S^{†}+h_S$, hence $\mathrm{\parallel }{x}^{†}{\mathrm{\parallel }}_1=\mathrm{\parallel }{x}_S^{†}{\mathrm{\parallel }}_1=\mathrm{\parallel }{z}_S-h_S{\mathrm{\parallel }}_1\le \mathrm{\parallel }{z}_S{\mathrm{\parallel }}_1+\mathrm{\parallel }{h}_S{\mathrm{\parallel }}_1$. On $S^c$, $x^{†}$ vanishes and $z_{S^c}=h_{S^c}$, so $z=z_S+h_{S^c}$ with disjoint coordinate supports and $\mathrm{\parallel }z{\mathrm{\parallel }}_1=\mathrm{\parallel }{z}_S{\mathrm{\parallel }}_1+\mathrm{\parallel }{h}_{S^c}{\mathrm{\parallel }}_1$. By step 1.1, this is strictly greater than $\mathrm{\parallel }{z}_S{\mathrm{\parallel }}_1+\mathrm{\parallel }{h}_S{\mathrm{\parallel }}_1\ge \mathrm{\parallel }{x}^{†}{\mathrm{\parallel }}_1$. Thus every feasible vector distinct from $x^{†}$ has strictly larger objective, and $x^{†}$, which is feasible, is the unique minimizer.

If $\ker A=\{0\}$, choose $\rho =1\mathrm{/}2$. The only $h\in \ker A$ is zero, so both sides of the required inequality are zero for every $S$. Now suppose $\ker A\mathrm{\ne }\{0\}$ and define $K:=\{h\in \ker A:\mathrm{\parallel }h{\mathrm{\parallel }}_2=1\}$. This set is nonempty by normalizing a nonzero kernel vector, since [F5] makes its norm positive. To show $K$ is closed, fix $x\mathrm{\notin }K$. If $Ax\mathrm{\ne }0$, choose a row $i$ with $c:=(Ax{)}_i\mathrm{\ne }0$ and let $r_i$ be that row as a vector in ${\mathbb{R}}^n$. By [F11], [F12], and [F13], $f_i(u):=(Au{)}_i=⟨r_i,u⟩$ and $f_i(y)-f_i(x)=⟨r_i,y-x⟩$. By [F4], $\mathrm{\mid }{f}_i(y)-c\mathrm{\mid }\le \mathrm{\parallel }{r}_i{\mathrm{\parallel }}_2\mathrm{\parallel }y-x{\mathrm{\parallel }}_2$. Moreover, $\mathrm{\parallel }{r}_i{\mathrm{\parallel }}_2>0$: otherwise [F5] gives $r_i=0$, which would imply $c=⟨r_i,x⟩=0$. Thus $\delta :=\mathrm{\mid }c\mathrm{\mid }\mathrm{/}(2\mathrm{\parallel }{r}_i{\mathrm{\parallel }}_2)>0$, and whenever $\mathrm{\parallel }y-x{\mathrm{\parallel }}_2<\delta$ we have $\mathrm{\mid }{f}_i(y)-c\mathrm{\mid }<\mathrm{\mid }c\mathrm{\mid }\mathrm{/}2$, so $f_i(y)\mathrm{\ne }0$ and $y\mathrm{\notin }K$. If $Ax=0$, then $\mathrm{\parallel }x{\mathrm{\parallel }}_2\mathrm{\ne }1$; put $\delta :=\mathrm{\mid }\mathrm{\parallel }x{\mathrm{\parallel }}_2-1\mathrm{\mid }\mathrm{/}2>0$. By [F14], $\mathrm{\mid }\mathrm{\parallel }y{\mathrm{\parallel }}_2-\mathrm{\parallel }x{\mathrm{\parallel }}_2\mathrm{\mid }\le \mathrm{\parallel }y-x{\mathrm{\parallel }}_2$, so $\mathrm{\parallel }y-x{\mathrm{\parallel }}_2<\delta$ precludes $\mathrm{\parallel }y{\mathrm{\parallel }}_2=1$ and again $y\mathrm{\notin }K$. Hence every point outside $K$ has a ball disjoint from $K$, so $K$ is closed. It is bounded because every $h\in K$ has $\mathrm{\parallel }h{\mathrm{\parallel }}_2=1$ and [F5] identifies this with its Euclidean distance from $0$. By [F8], $K$ is compact.

Fix $S\subseteq [n]$ with $\mathrm{\mid }S\mathrm{\mid }\le s$ and define $P_S,P_{S^c}:{\mathbb{R}}^n\to {\mathbb{R}}^n$ by $P_{S}u:=u_S$ and $P_{S^c}u:=u_{S^c}$. For all $u,v\in {\mathbb{R}}^n$ and every coordinate $j$, $\mathrm{\mid }(P_{S}u-P_{S}v{)}_j\mathrm{\mid }\le \mathrm{\mid }{u}_j-v_j\mathrm{\mid }$; both sides are nonnegative, so the forward implication in [F15] and then [F10] give $\mathrm{\parallel }{P}_{S}u-P_{S}v{\mathrm{\parallel }}_2^2\le \mathrm{\parallel }u-v{\mathrm{\parallel }}_2^2$. Both Euclidean norms are nonnegative by [F5], so the converse implication in [F15] yields $\mathrm{\parallel }{P}_{S}u-P_{S}v{\mathrm{\parallel }}_2\le \mathrm{\parallel }u-v{\mathrm{\parallel }}_2$. The same argument applies to $P_{S^c}$, making both coordinate projections $1$-Lipschitz, hence continuous for $d_2$. Since $\mathrm{\parallel }\cdot {\mathrm{\parallel }}_1$ is a norm by [F5] and every norm on ${\mathbb{R}}^n$ is continuous for $d_2$ by [F7], the compositions $a_S(h):=\mathrm{\parallel }{h}_S{\mathrm{\parallel }}_1$ and $b_S(h):=\mathrm{\parallel }{h}_{S^c}{\mathrm{\parallel }}_1$ are continuous. For each $h\in K$, [F1] gives $a_S(h)<b_S(h)$, hence $b_S(h)>0$. To verify continuity of $r_S:=a_S\mathrm{/}{b}_S$ at any $h_0\in K$, put $a_0:=a_S(h_0)$ and $b_0:=b_S(h_0)>0$. Continuity of $b_S$ gives a neighborhood of $h_0$ in $K$ on which $b_S(h)>b_0\mathrm{/}2$. There, $\mathrm{\mid }{r}_S(h)-r_S(h_0)\mathrm{\mid }\le \frac{2}{b_0}\mathrm{\mid }{a}_S(h)-a_0\mathrm{\mid }+\frac{2a_0}{b_0^2}\mathrm{\mid }{b}_S(h)-b_0\mathrm{\mid },$ by splitting the difference of the two quotients. The right side tends to $0$ as $h\to h_0$, since $a_S$ and $b_S$ are continuous; thus $r_S$ is continuous on $K$. By [F8] it attains a maximum $q_S$ on $K$, and [F1] at a maximizing point gives $0\le q_S<1$.

There are finitely many sets $S\subseteq [n]$ with $\mathrm{\mid }S\mathrm{\mid }\le s$, and this family is nonempty because it contains $\mathrm{\varnothing }$. Therefore [F9] gives $q:={\max }_{\mathrm{\mid }S\mathrm{\mid }\le s}{q}_S<1$. Choose any $h\in K$ and a coordinate $j$ with $h_j\mathrm{\ne }0$; then $S=\{j\}$ is admissible because $s\ge 1$, and [F2] gives $r_S(h)>0$, so $q>0$. Set $\rho :=(1+q)\mathrm{/}2$; then $q<\rho <1$.

Let $h\in \ker A$. If $h=0$, the required inequality is immediate. Otherwise $\tilde{h}:=h\mathrm{/}\mathrm{\parallel }h{\mathrm{\parallel }}_2$ belongs to $K$. For every admissible $S$, [F6] gives $r_S(h)=r_S(\tilde{h})\le q<\rho$, so $\mathrm{\parallel }{h}_S{\mathrm{\parallel }}_1\le \rho \mathrm{\parallel }{h}_{S^c}{\mathrm{\parallel }}_1$. This proves the estimate with one constant for all $S$ and all kernel vectors.