Past exam of the mathematics course of the University of Cambridge / 2018 / iii / Paper 340 / 4

Under the usual definition, the null space property relative to $S$ is $\Vert h_S{\Vert }_1<\Vert h_{S^c}{\Vert }_1$ for every nonzero $h\in \ker A$. It characterizes recovery by basis pursuit of every vector supported in $S$. Indeed, if it holds, then for any such $x_0$ and any nonzero $h\in \ker A$,Conversely, failure for some $h$ makes $x_0=-h_S$ and $z=h_{S^c}$ feasible with the same measurements and $\Vert z{\Vert }_1\le \Vert x_0{\Vert }_1$. ThusFor the single fixed vector in the printing, necessity is false with that definition. For example,has $\ker A=\mathrm{span}\{(1,1,1)\}$. Along its feasible line, the objective is $|1+t|+|-1+t|+|t|$, uniquely minimized at $t=0$, although the null space property would require $2<1$.

The correct fixed-sign null space condition isSufficiency follows from the supporting-line inequality for the absolute value. Necessity follows by considering $x_0\pm th$ for small positive $t$, when all signs on $S$ remain unchanged: a nonpositive directional increase gives either a decrease or another minimizer. If “relative to $S$” was intended to include these signs, this is the precise condition needed.

Let $T$ be the support of a vector $\hat{x}$. If the columns indexed by $T$ were linearly dependent, there would be a nonzero $h$ supported in $T$ with $Ah=0$. For sufficiently small real $t$, the nonzero signs of ${\hat{x}}_T$ remain fixed, soBoth positive and negative $t$ preserve the residual and hence feasibility, even with noise. A nonzero slope contradicts minimality in one direction. A zero slope gives distinct minimizers, contradicting uniqueness. Thus those columns are linearly independent, andThis proves the sparse vector assertion without assuming a noiseless residual.

The printed definition of the restricted isometry constant omits the quantifier: the two inequalities must hold for every vector with at most $s$ nonzero entries. The constant is the smallest nonnegative value, or the infimum over positive values; it can be zero.

Let $T=\mathrm{supp}u\cup \mathrm{supp}v$ and $B=A_T^{\ast }{A}_T-I$. The restricted isometry property of order $s+t$ says $|z^{\ast }Bz|\le {\delta }_{s+t}\Vert z{\Vert }_2^2$ for every $z$ supported on $T$. Since $B$ is a Hermitian matrix, the finite-dimensional spectral theorem implies $\Vert B{\Vert }_{2\to 2}\le {\delta }_{s+t}$. Disjoint supports give $⟨u,v⟩=0$, henceThis argument works over $\mathbb{C}$ and avoids the loss of a factor caused by treating real and imaginary parts separately.

The printed bound is false, even for $s=2$ and zero noise. Let $P=I_7-11^T/7$ and choose $A$ with six orthonormal rows spanning $1^{\perp }$, so $A^{T}A=P$. For a vector supported on at most $s$ entries,Take $x_0=(0,0,1,1,1,1,1)$, $s=2$, and $\eta =0$. Every feasible vector is $x_0+t1$, whose ${\ell }^1$ objective is $2|t|+5|1+t|$. Its unique minimizer is $\hat{x}=(-1,-1,0,0,0,0,0)$. YetNo choice of the noise constant repairs this example. Also $s=1$ must be excluded: $A=(1,1)$ has ${\delta }_1=0$, but its two unit-coordinate vectors have identical measurements and both minimize basis pursuit.

The corrected conclusion, for $s\ge 2$, iswith both constants depending on the restricted isometry constant. The order-$s$ threshold itself is valid for $s\ge 2$; it need not be replaced by an order-$2s$ threshold. A precise sharp robust recovery theorem gives, for $\delta ={\delta }_s<1/3$, the admissible constantsThis is the standard stable recovery result, invoked here explicitly; its order restriction and constants are given in arxiv.org/pdf/1302.1236, Theorem 3.3.

For completeness, the mechanism behind a robust null space property proof is as follows. Put $h=\hat{x}-x_0$, let $S$ index the largest $s$ entries of $x_0$, and write $\sigma =\Vert x_{0,S^c}{\Vert }_1$. Feasibility and minimality give the tube and cone inequalitiesIf $A$ has the robust null space property with $0\le \rho <1$ and $\tau >0$, namely $\Vert h_T{\Vert }_2\le \rho \Vert h_{T^c}{\Vert }_1/\sqrt{s}+\tau \Vert Ah{\Vert }_2$ for every $|T|\le s$, thenApply that property again to the largest $s$ entries $T$ of $h$. Sorted coefficients satisfy $\Vert h_{T^c}{\Vert }_2\le \Vert h{\Vert }_1/\sqrt{s}$, because each tail entry is at most $\Vert h{\Vert }_1/s$. ThereforeThis proves the usual two-constant conclusion under the explicitly stated robust null space property and explains why a fixed coefficient one is not supplied by that argument. The sharp order-$s$ theorem above supplies the conclusion for the actual printed threshold, after the necessary corrections.