Past exam of the mathematics course of the University of Cambridge / 2013 / iii / Paper 36 / 2

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.