= Solution
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$. Then
$$
\|Ax\|_2^2-\|x\|_2^2=u^*(A_S^*A_S-I_{|S|})u.
$$
The <Gram matrix> $A_S^*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>, equivalently
$$
\sup_{u\ne0}\frac{|u^*(A_S^*A_S-I_{|S|})u|}{\|u\|_2^2}=\|A_S^*A_S-I_{|S|}\|_{2\to2}.
$$
Indeed, 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. \b[Therefore]
$$
\boxed{\delta_s(A)=\max_{|S|\le s}\|A_S^*A_S-I_{|S|}\|_{2\to2}.}
$$
Back to article page
