= Solution
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^*A_S$ has diagonal entries one because the columns have unit <Euclidean norm>. Each off-diagonal row sum is bounded by
$$
\sum_{j\in S\setminus\{i\}}|\langle a_i,a_j\rangle|\le\mu_1(k-1)\le\mu_1(s-1).
$$
The 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> gives
$$
(1-\mu_1(s-1))\|x\|_2^2\le x_S^*Gx_S=\|Ax\|_2^2\le(1+\mu_1(s-1))\|x\|_2^2.
$$
This 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. \b[The distortion is bounded by $\mu_1(s-1)$ on every order-$s$ sparse vector.]
Back to article page
