Lemma 8.5.4 — reformulation of BP-exactness via the crosspolytope

Let $A$ be a real $m\times n$ matrix with $m<n$, let $r\le m$ be a nonnegative integer, and let $L=\{x\in\mathbb{R}^n: Ax=0\}$ be the kernel of $A$. Write $\|x\|_1=\sum_i|x_i|$, $\operatorname{supp}(x)=\{i: x_i\neq0\}$, and $B^n_1=\{x:\|x\|_1\le1\}$ for the crosspolytope. Recall that $A$ is BP-exact for $r$ if for every $b\in\mathbb{R}^m$, every solution $\tilde x$ of $Ax=b$ with at most $r$ nonzero components is the unique minimizer of $\|x\|_1$ subject to $Ax=b$. Then

In words: basis pursuit recovers every $r$-sparse solution exactly if and only if every translate of the kernel through a sparse boundary point $z$ of the crosspolytope touches the crosspolytope only at $z$. This geometric characterization is the starting point of the known proofs of Theorem 8.5.2.

Formalization Note The hypotheses $m<n$ and $r\le m$ are on the page and are kept, although the equivalence does not depend on them. Indices are $0,\dots,n-1$; the $\ell_1$-norm is written out as a sum of absolute values.