Theorem 1.5: decoding by linear programming recovers the input from sparsely corrupted measurements

Read-back of decoding_by_lp

Conventions. $\mathbb{R}^k$ denotes real vectors indexed by the $k$-element index set $\{0,\dots,k-1\}$; a matrix acts by ordinary matrix–vector multiplication. Two norms from the bundle are used, written out:

$$\|c\|_1 := \sum_{j} |c_j|, \qquad \|x\|_2 := \sqrt{\sum_i x_i^2}.$$

Because a sum of squares is non-negative, $\|x\|_2^2 = \sum_i x_i^2$ exactly, and no junk value of the square root arises. A vector $c \in \mathbb{R}^m$ is supported on a set $T$ of indices when $c_j = 0$ for every index $j \notin T$; that is, the support of $c$ is contained in $T$ (it need not equal $T$; $c = 0$ is supported on every $T$, including $T = \emptyset$).

Universally quantified data and hypotheses. The statement quantifies over all of the following:

• natural numbers $p$, $m$, $n$ (each may a priori be $0$), with $n < m$;
• a real $m \times n$ matrix $A$ such that $x \mapsto Ax$ is an injective map $\mathbb{R}^n \to \mathbb{R}^m$ (i.e. $Ax = Ax'$ implies $x = x'$; equivalently $A$ has trivial kernel);
• a real $p \times m$ matrix $F$ such that the matrix product $FA$ is the $p \times n$ zero matrix;
• a natural number $S$ with $1 \le S$ and $3S \le m$ (so $m \ge 3$);
• the inequality

$$\delta_S(F) + \theta_{S,S}(F) + \theta_{S,2S}(F) < 1,$$

where $\delta_S(F)$ and $\theta_{S,S'}(F)$ are the bundle's own constants, unfolded below;

• a vector $f \in \mathbb{R}^n$;
• a vector $e \in \mathbb{R}^m$;
• a finite set $T \subseteq \{0,\dots,m-1\}$ with $|T| \le S$ (this $T$ is a variable of the theorem, distinct from the bound variables of the same name inside the definitions below);
• the assumption that $e$ is supported on $T$, i.e. $e_j = 0$ for all $j \notin T$. Together with $|T| \le S$ this says $e$ has at most $S$ non-zero coordinates; $e = 0$ and $T = \emptyset$ are permitted.

The two constants, unfolded. For a natural number $S$,

$$\delta_S(F) := \inf\Bigl\{\delta \in \mathbb{R} \;:\; \delta \ge 0,\ \text{and for every } T \subseteq \{0,\dots,m-1\} \text{ with } |T| \le S \text{ and every } c \in \mathbb{R}^m \text{ supported on } T:\ (1-\delta)\,\|c\|_2^2 \le \|Fc\|_2^2 \ \text{ and } \ \|Fc\|_2^2 \le (1+\delta)\,\|c\|_2^2 \Bigr\}.$$

For natural numbers $S, S'$,

$$\theta_{S,S'}(F) := \inf\Bigl\{\theta \in \mathbb{R} \;:\; \theta \ge 0,\ \text{and for all disjoint } T, T' \subseteq \{0,\dots,m-1\} \text{ with } |T| \le S,\ |T'| \le S', \text{ and all } c, c' \in \mathbb{R}^m \text{ with } c \text{ supported on } T,\ c' \text{ supported on } T':\ \bigl|\langle Fc,\, Fc'\rangle\bigr| \le \theta\,\|c\|_2\,\|c'\|_2 \Bigr\},$$

where $\langle u, v\rangle = \sum_i u_i v_i$ is the ordinary dot product on $\mathbb{R}^p$. In both definitions the index sets range over all subsets of size at most $S$ (resp. $S'$), including the empty set, and $c, c'$ range over all vectors supported there, not only unit vectors. In $\theta_{S,S'}$ the two sets must be disjoint, but either may be empty; for $T = \emptyset$ only $c = 0$ qualifies and the inequalities read $0 \le 0$.

About the infima. The infimum is Mathlib's infimum on $\mathbb{R}$, which returns the junk value $0$ when the set is empty or when it is not bounded below. Neither happens here: both sets lie in $[0,\infty)$, so they are bounded below, and both are non-empty (every $\delta \ge \max(1, \|F\|_{\mathrm{op}}^2)$ lies in the first set, because for $\delta \ge 1$ the left side of the lower inequality is $\le 0$; every $\theta \ge \|F\|_{\mathrm{op}}^2$ lies in the second by Cauchy–Schwarz). Each set is also closed (its defining conditions are non-strict inequalities, continuous in $\delta$ resp. $\theta$), so the infimum is attained. Hence $\delta_S(F) \ge 0$ and $\theta_{S,S'}(F) \ge 0$, and the hypothesis $\delta_S + \theta_{S,S} + \theta_{S,2S} < 1$ forces each of the three constants to be $< 1$.

Conclusion. Put $y := Af + e \in \mathbb{R}^m$. The theorem asserts that $f$ is a unique residual $\ell^1$-minimiser for $(A, y)$ in the bundle's sense, which unfolds to

$$\text{for every } g \in \mathbb{R}^n \text{ with } g \ne f: \qquad \|y - Af\|_1 \;<\; \|y - Ag\|_1 .$$

Since $y - Af = e$ identically, this is the same as

$$\forall g \in \mathbb{R}^n,\quad g \ne f \;\Longrightarrow\; \|e\|_1 \;<\; \bigl\|\,e - A(g - f)\,\bigr\|_1,$$

with a strict inequality. The comparison is over all $g \in \mathbb{R}^n$, with no constraint on $g$. Nothing is asserted about $g = f$ itself, and nothing is asserted about how $f$ might be found.

Edge cases the quantifiers include.

• $p = 0$ is allowed. Then $F$ has no rows, $Fc$ is the empty vector, $\|Fc\|_2 = 0$ and $\langle Fc, Fc'\rangle = 0$ for all $c, c'$, and $FA = 0$ holds automatically. Consequently $\theta_{S,S}(F) = \theta_{S,2S}(F) = 0$, whereas (since $S \ge 1$ and $m \ge 3$ supply a non-zero $c$ with a single non-zero coordinate) the lower inequality $(1-\delta)\|c\|_2^2 \le 0$ forces $\delta \ge 1$, so $\delta_S(F) = 1$ and the hypothesis $\delta_S + \theta_{S,S} + \theta_{S,2S} < 1$ is false. The theorem therefore asserts nothing when $p = 0$.
• $n = 0$ is allowed (only $n < m$ is required). Then $\mathbb{R}^n$ has a single element, $f$ is that element, no $g \ne f$ exists, and the conclusion holds vacuously; injectivity of $x \mapsto Ax$ and $FA = 0$ are likewise automatic.
• $m \ge 3S \ge 3$ and $n \le m-1$ always. Beyond $FA = 0$ no relation between $F$ and $A$ is assumed: nothing is assumed about the rank of $F$, about the size of $p$, or about $p$ relative to $m - n$.
• The hypothesis $3S \le m$ is not referred to by any other hypothesis or by the conclusion; it stands as an additional assumption.
• The accompanying definitions of a matrix column and of the column span do not occur anywhere in the statement.