Past exam of the mathematics course of the University of Cambridge / 2013 / iii / Paper 36 (Contemporary Sampling Techniques and Compressed Sensing)

Let $S=\mathrm{supp}x$ be the support of a vector $x$, with $|S|\le s$. Suppose the null space property holds. Every other feasible vector is $z=x+v$, where $0\ne v\in \ker A$. Splitting its L1 norm over $S$ and $S^c$ and using the triangle inequality givesThus the sparse vector $x$ is the unique minimizer in basis pursuit. Notice that the argument works for complex coordinates: it uses the absolute value inequality, rather than a real sign function.

Conversely, suppose basis pursuit uniquely recovers every sparse vector of order $s$. Fix $0\ne v\in \ker A$ and any $S$ with $|S|\le s$. Take $x=-v_S$ and $z=v_{S^c}$. These vectors have the same measurements, because $A{v}_S+A{v}_{S^c}=0$, and they are distinct since $z-x=v\ne 0$. The vector $x$ has at most $s$ nonzero coordinates, so uniqueness givesThis is the null space property for every such $S$. Uniform unique recovery by basis pursuit is equivalent to the order-$s$ null space property.

First the null space property implies sparse injectivity. If a nonzero $v\in \ker A$ had at most $2s$ nonzero coordinates, partition its support of a vector into disjoint $S,T$ with $|S|,|T|\le s$. Applying the null space property to each of these sets yieldswhich is impossible. Hence the null space contains no nonzero sparse vector of order $2s$.

The feasible vector $x$ has $\Vert x{\Vert }_0\le s$, where the L0 sparsity count counts its nonzero coordinates. Any different feasible $z$ with $\Vert z{\Vert }_0\le \Vert x{\Vert }_0$ would give a nonzero null space vector $z-x$ with at most $2s$ nonzero coordinates, contrary to sparse injectivity. Consequently every different feasible $z$ has strictly larger L0 sparsity count. The unique sparsest feasible vector is $x$:This proof does not treat the L0 sparsity count as a genuine norm; no triangle inequality for it is needed.

Use the stated characterization by the Lq null space property. Raising an Lq quasi-norm comparison to its positive exponent preserves its order, so the hypothesis at $q$ says that, for every nonzero $v\in \ker A$ and every $|S|\le s$,We prove the corresponding $p$ inequality; this is monotonicity of uniform sparse recovery in the exponent.

Fix a nonzero null space vector and arrange its coordinate magnitudes as $a_1\ge \cdots \ge a_N\ge 0$. Assume $s\ge 1$. The Lq null space property rules out a nonzero null space vector supported on at most $s$ coordinates, so $s<N$ and $t=a_s>0$. Since $p-q<0$, the factors $a_j^{p-q}$ are at most $t^{p-q}$ for $j\le s$ and at least $t^{p-q}$ for $j>s$ with $a_j>0$. Terms with $a_j=0$ contribute zero and require no negative power of zero. ThusThe largest $s$ coordinates maximize the $p$-power sum on any set of size at most $s$. Its complement therefore has the smallest complementary $p$-power sum. The displayed strict inequality proves the Lq null space property at exponent $p$ for every allowed support of a vector. The stated recovery characterization now applies to the Lq quasi-norm at $p$.

If $\ker A=\{0\}$, the measurement constraint already singles out $x$, for every objective; if $s=0$, only the zero sparse vector needs recovery. These cases do not need a positive threshold. Uniform recovery at $q$ implies uniform recovery at every $0<p<q$:

Work in ${\mathbb{C}}^N$, the domain of the matrix $A$; the printed ${\mathbb{C}}^n$ in the introduction is a dimension typo. For a fixed nonempty support of a vector $S$, write $u$ for the coordinates of $x$ in $S$. ThenThe Gram matrix $A_S^{\ast }{A}_S$ is a Hermitian matrix, so its difference from the identity matrix is also a Hermitian matrix. By the finite-dimensional spectral theorem, its matrix 2-norm is the largest absolute eigenvalue, equivalentlyIndeed, an expansion in an orthonormal eigenbasis bounds every Rayleigh quotient by the largest absolute eigenvalue, and an appropriate eigenvector attains that bound. The restricted isometry constant must bound this quantity for every $S$ of size at most $s$, and the maximum of these quantities suffices for all sparse vectors of order $s$. There are finitely many sets, so the maximum exists. The empty set contributes zero. Therefore

Use the natural empty-sum convention ${\mu }_1(0)=0$ for cumulative coherence. This is needed for the printed case $s=1$. For $x=0$ the conclusion is immediate. Otherwise let $S$ be its support of a vector, with $k=|S|\le s$. The Gram matrix $G=A_S^{\ast }{A}_S$ has diagonal entries one because the columns have unit Euclidean norm. Each off-diagonal row sum is bounded byThe last inequality uses monotonicity of cumulative coherence: enlarging an index set only adds nonnegative summands. There are enough indices to enlarge it because $s\le N$.

The Gershgorin circle theorem places every eigenvalue of $G$ within distance ${\mu }_1(s-1)$ of one. Since $G$ is a Hermitian matrix, its eigenvalues are real, and the finite-dimensional spectral theorem givesThis is the cumulative coherence bound for restricted isometry. The lower bound remains valid when ${\mu }_1(s-1)>1$, although it is then nonpositive. No assumption that the matrix is already a near isometry is required. The distortion is bounded by ${\mu }_1(s-1)$ on every order-$s$ sparse vector.

For one-column Gram matrices, unit Euclidean norm of the columns gives $A_S^{\ast }{A}_S=1$. The restricted isometry constant formula therefore gives ${\delta }_1=0$. For a two-column Gram matrix, put $c=⟨a_i,a_j⟩$. The difference from the identity matrix has the formup to the convention for the complex inner product. Its characteristic polynomial is ${\lambda }^2-|c{|}^2$, so the eigenvalues are $\pm |c|$ and its matrix 2-norm is $|c|$. Maximizing over pairs gives ${\delta }_2=\mu$, where $\mu$ is the mutual coherence.

Part (b), together with the minimality defining the restricted isometry constant, gives ${\delta }_s\le {\mu }_1(s-1)$. Every summand defining cumulative coherence is at most the mutual coherence, so ${\mu }_1(s-1)\le (s-1)\mu$. Thus, for normalized columns and $N\ge 2$,The upper range $s\le N$ matters because the printed definition of cumulative coherence stops at $N-1$. For $N=1$, only ${\delta }_1=0$ is needed; the maximum over pairs defining mutual coherence is otherwise empty.

Let $\sigma =\mathrm{sgn}(x_S)$, using the real sign function on the support of a vector $x$. The fixed-sign null space condition in the PDF uses $S^c$ on its right-hand side. This complement is essential. For any real coordinate $x_j\ne 0$, the supporting-line inequality for the absolute value isEvery distinct feasible vector is $x+v$ with $0\ne v\in \ker A$. Summing the coordinate inequalities on $S$ and adding the L1 norm on $S^c$ givesThe strict final inequality is precisely the fixed-sign null space condition. Hence $x$ is the unique basis pursuit minimizer. Unlike the null space property of Question 1, this condition concerns the particular sign function values of $x$, rather than every vector supported in $S$.

Assume $x$ is the unique basis pursuit minimizer. Fix $0\ne v\in \ker A$ and setThere is $\epsilon >0$ such that the sign function of $x_j+t{v}_j$ equals that of $x_j$ at every $j\in S$ whenever $|t|<\epsilon$. To choose it, take less than the minimum of $|x_j|/|v_j|$ over the nonzero $v_j$ in $S$; if that set is empty, any positive $\epsilon$ works. On this interval the L1 norm has the exact expressionFor $0<t<\epsilon$, both $x+tv$ and $x-tv$ are distinct feasible vectors. Uniqueness forces their objective differences to be strictly positive, so $\alpha +\beta >0$ and $-\alpha +\beta >0$. ThereforeThe fixed-sign null space condition is necessary as well as sufficient. This argument also covers an empty support of a vector: then $\alpha =0$ and the nonzero null space vector has $\beta >0$. Strictness is indispensable: equality would make a sufficiently short feasible segment have the same objective as $x$.

Let $u=A^{\ast }h$ be the strict dual certificate for basis pursuit supplied by condition (ii). For $0\ne v\in \ker A$, we haveHere the adjoint operator is the real transpose. The injectivity of $A_S$ ensures $v_{S^c}\ne 0$: otherwise $A_S{v}_S=0$ would force $v=0$. Thus at least one nonzero term lies outside the support of a vector $x$. Since $|u_l|<1$ at every such index,This proves the fixed-sign null space condition, so part (a) gives uniqueness in basis pursuit. If $S^c$ is empty, the injectivity of $A_S=A$ instead means there is no nonzero null space vector, and the feasible set is a singleton. Injective active columns and a strict dual certificate for basis pursuit ensure unique recovery. Both ingredients matter: strictness outside $S$ cannot detect a nonzero null space direction supported entirely inside $S$.

Write $\sigma =\mathrm{sgn}(x_S)$ and $G=A_S^{\ast }{A}_S$. The injectivity of $A_S$ makes this Gram matrix a positive-definite matrix, since $u^{\ast }Gu=\Vert A_{S}u{\Vert }_2^2>0$ for $u\ne 0$. Thus its matrix inverse exists. Construct the least-norm dual certificateOn the active coordinates, $A_S^{\ast }h=G{G}^{-1}\sigma =\sigma$. For $l\notin S$, symmetry of the real Gram matrix and its matrix inverse givesCondition (iii) makes the absolute value of this coordinate strictly less than one. Consequently $h$ is a strict dual certificate for basis pursuit, and part (c) applies. If $S$ is empty, take $h=0$; the zero vector uniquely minimizes the L1 norm on its feasible set. Condition (iii) supplies an explicit certificate and therefore unique recovery. There is no claim that this particular least-norm dual certificate is necessary: other valid certificates may exist when this one fails.

Interpret the angle as the directed subspace angle defined by the infimum of projected unit vectors; it is different from the smallest angle between two subspaces. WriteConsider the bounded linear operator $T:W⟶V^{\perp }$ given by $Tw=P_{V^{\perp }}w$. Its adjoint operator, between these two Hilbert spaces, is $T^{\ast }u=P_{W}u$: for $w\in W$ and $u\in V^{\perp }$, the orthogonal projections give $⟨Tw,u⟩=⟨w,u⟩=⟨w,P_{W}u⟩$. The two positive directed subspace angle cosines yieldThe first bound makes $T$ injective and gives a closed range. Explicitly, if $T{w}_j$ converges, then $\Vert w_j-w_k\Vert \le a^{-1}\Vert T{w}_j-T{w}_k\Vert$, so $(w_j)$ is a Cauchy sequence. The closed subspace of a Hilbert space $W$ is complete, and its limit maps to the proposed range limit. The second bound gives $\ker T^{\ast }=\{0\}$. A vector $u\in V^{\perp }$ orthogonal to the range has $T^{\ast }u=0$, so it must be zero. The range is therefore dense as well as closed in $V^{\perp }$, and $T$ is onto. This is the mechanism of invertibility from lower bounds on an operator and its adjoint.

For any $f\in H$, choose the unique $w\in W$ with $Tw=P_{V^{\perp }}f$. Then $P_{V^{\perp }}(f-w)=0$, so $f-w\in V$. Moreover, if $w\in W\cap V$, then $Tw=0$ and hence $w=0$. Every vector has a unique decomposition, andThe direct sum is a topological one as well: the component $w=T^{-1}{P}_{V^{\perp }}f$ depends boundedly on $f$, with operator norm at most $a^{-1}$.

For precision, the quoted equality of the norms of complementary oblique projections needs both summands nonzero. For example, with $H=\mathbb{R}$, $V=H$ and $W=\{0\}$, the oblique projection is $I$, so $\Vert I\Vert =1$ but $\Vert I-I\Vert =0$. The secant function has value one here, so the second equality in the quoted formula fails. With nonzero complementary summands its intended version is valid. The proof above does not use that formula. The angle itself is undefined on a zero source space because it has no unit vectors; expressing the hypotheses as the two lower bounds handles zero spaces without ambiguity.

Use $T=P_{V^{\perp }}{|}_U:U⟶V^{\perp }$. Positivity of the directed subspace angle cosine givesso $T$ is injective. The two vector spaces have the same finite dimension, $n$. By the rank-nullity theorem, $T$ is also surjective. There is no need to assume a second positive directed subspace angle cosine in this finite-dimensional case.

For any $f\in H$, find $u\in U$ with $Tu=P_{V^{\perp }}f$. Then $f-u\in V$. If $u\in U\cap V$, then $Tu=0$, and injectivity gives $u=0$. HenceThe direct sum is again bounded: $u=T^{-1}{P}_{V^{\perp }}f$. If $n=0$, then $U=\{0\}$ and $V^{\perp }=\{0\}$, so closedness of $V$ gives $V=H$ and the conclusion directly; no angle of an empty unit sphere is needed. Equal finite dimensions are essential to the surjectivity argument, whereas mere injectivity between infinite-dimensional Hilbert spaces is insufficient.

The linear independence of the first $n$ elements of each orthonormal system shows that $T_n$ and $S_n$ have the same finite dimension $n$ and are closed subspaces of a Hilbert space. Apply part (b) with $U=T_n$ and $V=S_n^{\perp }$. Since $(S_n^{\perp }{)}^{\perp }=S_n$, the positive directed subspace angle cosine givesLet $Q$ be the oblique projection onto $T_n$ along $S_n^{\perp }$. Define ${\tilde{f}}_n=Qf$. Its residual $f-Qf$ is orthogonal to every ${\psi }_j$ with $1\le j\le n$, so the required measurements agree. Conversely, if $g\in T_n$ has the same measurements, then $f-g\in S_n^{\perp }$; uniqueness of the direct sum decomposition gives $g=Qf$. Thus this is finite-dimensional Hilbert sampling reconstruction.

There is also an explicit coefficient description. Use the inner product convention linear in its first entry and putThen $Cc=b$. The orthonormal systems show $\Vert P_{S_n}{\sum }_k{c}_k{\varphi }_k\Vert =\Vert Cc{\Vert }_2$ and $\Vert {\sum }_k{c}_k{\varphi }_k\Vert =\Vert c{\Vert }_2$, so the smallest singular value of $C$ is $\cos {\theta }_{T_n,S_n}>0$. Hence $c=C^{-1}b$, another direct proof of existence and uniqueness.

For $n\ge 1$, both summands of this direct sum are nonzero: the infinite orthonormal system $({\psi }_j)$ contains ${\psi }_{n+1}\in S_n^{\perp }$. The permitted oblique projection norm formula therefore applies without its degenerate exception, givingThe operator norm immediately yields the stability estimate $\Vert {\tilde{f}}_n\Vert \le \sec {\theta }_{T_n,S_n}\Vert f\Vert$. For the approximation bounds, put $e=f-P_{T_n}f$. Because $Q$ fixes $T_n$, we haveso the operator norm estimate gives $\Vert f-Qf\Vert \le \sec {\theta }_{T_n,S_n}\Vert e\Vert$. For the lower bound, $e\perp T_n$ while $P_{T_n}f-Qf\in T_n$. The Pythagorean identity givesThe unique measurement-matching reconstruction is stable and within the secant function factor of the best orthogonal projection approximation:If a zero-dimensional reconstruction is admitted, it is simply ${\tilde{f}}_0=0$ and its error equals the norm of $f$; that case is best stated directly instead of using the angle of a zero space.