Decoding by Linear Programming

Theorem 1.4 (exact recovery). If $\delta_S+\theta_S+\theta_{S,2S}\lt1$, then every $c$ supported on at most $S$ indices is the unique minimizer of $\min\|d\|_{\ell_1}$ subject to $Fd=Fc$. By the link above the hypothesis follows from $\delta_S+\delta_{2S}+\delta_{3S}\lt1$, which is what Section 3 uses. Theorem 1.5 (decoding). If $FA=0$, $F$ satisfies the hypothesis, and $e$ has at most $S$ nonzero entries, then $f$ is the unique minimizer of $\min_g\|y-Ag\|_{\ell_1}$. Both statements are deterministic, with no failure probability once $F$ is known to satisfy the hypothesis.

Theorem 1.6 (Gaussian matrices). If $F$ is $p\times m$ with i.i.d. $N(0,1/p)$ entries, the hypothesis of Theorem 1.4 holds with probability at least $1-e^{-cm}$ whenever $r=S/m\lt r^*(p/m)$, with $r^*\approx3.6\cdot10^{-4}$, $3.2\cdot10^{-4}$, $2.3\cdot10^{-4}$ for $p/m=3/4,\,2/3,\,1/2$. Corollary 1.7. For a Gaussian coding matrix $A$ ($m\times n$) and $p=m-n$, $\ell_1$ decoding recovers $f$ exactly whenever at most $r^*m$ entries are corrupted. The reason is that the program sees $F$ only through its null space, the range of $A$, which for Gaussian $A$ is a uniformly random $n$-dimensional subspace, the same law as the null space of a Gaussian $F$. In experiments $\ell_1$ decoding recovers $f$ every time up to about 17% corrupted entries when $m=2n$.

Decoding is sparse recovery, and both are linear programs. Write $g=f+h$, so $\min_g\|y-Ag\|_1=\min_h\|e-Ah\|_1$. The constraint $Fd=Fe$ says exactly that $d=e-Ah$ for some $h$, so decoding over $g$ and recovery over $d$ are one problem, and $f$ is recovered exactly when $e$ is. The decoding form is the linear program $$\min_{g,t}\ \mathbf 1^\top t\qquad\text{subject to}\quad -t\le y-Ag\le t,$$ which never needs $F$; $F$ enters only the analysis.

A dual certificate proves uniqueness. By the optimality condition of $\ell_1$, $c$ is the unique minimizer if $F_T$ is injective and some $w$ has $\langle w,v_j\rangle=\mathrm{sgn}(c_j)$ on $T$ and $|\langle w,v_j\rangle|\lt1$ off $T$, a strictly feasible dual vector of the linear program. For any feasible $d$, $$\|d\|_1\ \ge\ \sum_{j\in T}\mathrm{sgn}(c_j)\,d_j+\sum_{j\notin T}d_j\langle w,v_j\rangle=\langle w,Fd\rangle=\langle w,Fc\rangle=\|c\|_1,$$ so if $d$ is also a minimizer every inequality is an equality, the strict bound off $T$ forces $d_j=0$ there, and $F_T(d-c)=0$ with $\delta_S\lt1$ gives $d=c$. The remaining steps construct $w$.

The least-norm interpolant of the signs is small off the support in $\ell_2$. Take $w=F_T(F_T^*F_T)^{-1}c_T$, the minimum-norm vector with inner products $c_T$ against the columns in $T$; restricted isometry gives $\|(F_T^*F_T)^{-1}\|\le1/(1-\delta_S)$. For $T'$ disjoint from $T$ with $|T'|\le S'$, $\langle w,F_{T'}d\rangle$ is a cross term between spans of disjoint supports, so restricted orthogonality bounds it, and duality turns that into a bound on the $\ell_2$ mass of $w$'s inner products with any $S'$ columns off the support: $$\Big(\sum_{j\in T'}\langle w,v_j\rangle^2\Big)^{1/2}\le\frac{\theta_{S,S'}}{1-\delta_S}\,\|c\|.$$ By pigeonhole at most $S'$ indices off $T$ exceed $\theta_{S,S'}\|c\|/\big((1-\delta_S)\sqrt{S'}\big)$ in absolute value, and the rest are uniformly small. Call these at most $S'$ indices the exceptional set; an $\ell_2$ bound cannot keep their entries below 1.

Correcting the exceptional set repeatedly gives the $\ell_\infty$ certificate and the hypothesis. Correct the interpolant on its exceptional set, correct the correction, and sum the alternating series. Let $w_1$ be the vector of Step 3 and $T_1$ its exceptional set (with $S'=S$); build $w_2$ the same way to agree with $w_1$ on $T_1$ and vanish on $T_0=T$, with its own exceptional set $T_2$, and so on, and set $w=\sum_{n\ge1}(-1)^{n-1}w_n$. On $T_0$ only $w_1$ contributes, giving $c$. Off $T_0$, the $n$-th and $(n+1)$-st terms cancel wherever $j\in T_n$, and every surviving term is at most the uniform bound of Step 3 for that $w_n$. Each correction is driven only by the previous exceptional values, so these bounds shrink geometrically with ratio $\theta_{S,2S}/(1-\delta_S)$, and summing gives $$|\langle w,v_j\rangle|\le\frac{\theta_S}{1-\delta_S-\theta_{S,2S}}\cdot\frac{\|c\|}{\sqrt S}\qquad(j\notin T).$$ For the certificate $c=\mathrm{sgn}(c)$ on $T$, so $\|c\|\le\sqrt S$, and the bound is below 1 exactly when $\delta_S+\theta_S+\theta_{S,2S}\lt1$.

Restricted orthogonality is controlled by restricted isometry. For unit $c,c'$ on disjoint supports $T,T'$, both $F_Tc\pm F_{T'}c'$ are $F$ applied to an $(S+S')$-sparse vector of norm $\sqrt2$, so their squared norms lie in $[2(1-\delta_{S+S'}),\,2(1+\delta_{S+S'})]$, and the parallelogram identity $\langle f,g\rangle=(\|f+g\|^2-\|f-g\|^2)/4$ gives $\theta_{S,S'}\le\delta_{S+S'}$. Hence $\delta_S+\theta_S+\theta_{S,2S}\le\delta_S+\delta_{2S}+\delta_{3S}$, and only the extreme singular values of column submatrices of size up to $3S$ need bounding.

Gaussian submatrices are near-isometries uniformly over all supports. For a fixed $T$ with $|T|=S$, the extreme singular values of $F_T$ are $1\pm\sqrt{S/p}$ to first order (the Marchenko-Pastur edges), and as Lipschitz functions of a Gaussian matrix each exceeds that by $t$ with probability at most $e^{-pt^2/2}$ (Gaussian concentration). Monotonicity in $T$ reduces the uniform statement to supports of size exactly $S$, and the union bound over $\binom mS=e^{mH(r)+O(\log m)}$ of them is absorbed by taking $t$ just above $\sqrt{2mH(r)/p}$. So with probability $1-e^{-cm}$, up to a factor $1+\epsilon$ on $f$, $$1+\delta_S\le\big(1+f(r)\big)^2,\qquad f(r)=\sqrt{m/p}\,\Big(\sqrt r+\sqrt{2H(r)}\Big),$$ and likewise at $2r$ and $3r$, so Theorem 1.4 applies once $\sum_{j=1}^3\big[(1+f(jr))^2-1\big]\lt1$. Solving it numerically reproduces the paper's thresholds (my check: $3.66\cdot10^{-4}$, $3.21\cdot10^{-4}$, $2.34\cdot10^{-4}$). The entropy term dominates, $\sqrt{2H(r)}\approx\sqrt{2r\log(1/r)}$ being about four times $\sqrt r$ at these $r$, so the requirement of uniformity over supports is what sets $r^*$.

Consequences and limits. A constant fraction of arbitrarily corrupted entries can be corrected by a linear program, with a deterministic guarantee on any matrix that meets the condition, and the restricted isometry property becomes the organizing hypothesis of compressed sensing. A companion result, proved elsewhere, gives compressible signals $\ell_1$ recovery errors as good as knowing the largest coefficients in advance, up to a log factor in the number of measurements. The limit is the gap between $r^*\approx2\cdot10^{-4}$ and the 17% seen in experiments, and the authors show that part of it lies in the sufficient condition itself: even with exact limiting values of the constants, $\delta_S+\theta_S+\theta_{S,2S}$ stays above 1 once $(m/p)\,r$ exceeds about 0.0236. Sharp answers came later, about $2s\log(N/s)$ measurements for $s$-sparse vectors in dimension $N$. For superposition (a network storing more features than it has dimensions), the columns $v_j$ are the feature directions: far more of them than dimensions is harmless as long as any few are nearly orthogonal, which random directions satisfy with high probability, though a network decodes with only one linear map and a ReLU.