Deviation of squares, Exercise 9.1.10 in High Dimensional Probability

123 Views Asked by At

So let me begin by stating the matrix deviation inequality (Theorem 9.1.1) in Vershynin's High Dimensional Probability book.

Theorem 9.1.1: We have that if $A$ is an $m\times n$ matrix whose rows $A_i$ are independent, isotropic, and sub-gaussian random vectors in $\mathbb{R}^n$. Then for any subset $T\subset \mathbb{R}^n$, we have

$$E\sup_{x\in T} \left| |||Ax||_2 - \sqrt{m} ||x||_2 \right | \leq CK^2 \gamma(T)$$

where $\gamma(T)=E\sup_{t\in T}|\langle x,g\rangle|$ where $g \sim \mathcal{N}(0, I_n)$ is the Gaussian complexity and $K=max_i ||A_i||_{\psi_2}$.

Now under the same assumptions as Theorem 9.1.1 exercise 9.1.10 asks us to extend the result to squares. Namely, show that

$$E\sup_{x\in T} \left| |||Ax||_2^2 - m ||x||_2^2 \right | \leq CK^4 \gamma(T)^2+CK^2 \sqrt{m} \text{rad}(T)\gamma(T)$$

where $\text{rad}(T)=\sup_{t\in T} ||t||_2$

The idea of proof I had in mind was to rewrite the expectation as

$$ \begin{align*} E\sup_{x\in T} \left| |||Ax||_2^2 - m ||x||_2^2 \right| &= E\sup_{x\in T} \left(\left| |||Ax||_2 - \sqrt{m} ||x||_2 \right| \left| |||Ax||_2 + \sqrt{m} ||x||_2 \right|\right) \\ & \leq E\sup_{x\in T} \left(\left| |||Ax||_2 - \sqrt{m} ||x||_2 \right| \left| |||Ax||_2 + \sqrt{m} ||x||_2 \right|\right) \\ & \leq E\sup_{x\in T} \left(\left| |||Ax||_2 - \sqrt{m} ||x||_2 \right| \left| |||Ax||_2 \right|\right) + E\sup_{x\in T} \left(\left| |||Ax||_2 - \sqrt{m} ||x||_2 \right| \left|\right|\right) \sqrt{m} ||x||_2 \\ & \leq E\sup_{x\in T} \left(\left| |||Ax||_2 - \sqrt{m} ||x||_2 \right| \left| |||Ax||_2 \right|\right) + CK^2\sqrt{m}\text{rad}(T)\gamma(T) \end{align*} $$

My issue is how do I show $E\sup_{x\in T} \left(\left| |||Ax||_2 - \sqrt{m} ||x||_2 \right| \left| |||Ax||_2 \right|\right) \leq CK^4 \gamma(T)^2$