Proof. For simplicity, we assume that \(K \geq 1\). We shall apply Bernstein’s deviation inequality for the normalized sum of independent, mean-zero random variables \[ \frac {1}{n} \|X\|_2^2 - 1 = \frac {1}{n} \sum _{i=1}^n (X_i^2 - 1). \] Since the random variable \(X_i\) is sub-Gaussian, \(X_i^2 - 1\) is sub-exponential, and more precisely \begin{align*} \|X_i^2 - 1\|_{\psi _1} &\leq C \|X_i^2\|_{\psi _1} \\ &= C \|X_i\|_{\psi _2}^2 \\ &\leq C K^2. \end{align*}

Applying Bernstein’s inequality, we obtain for any \(u \geq 0\) that \[ \mathbb {P}\!\left \{ \left | \frac {1}{n} \|X\|_2^2 - 1 \right | \geq u \right \} \leq 2 \exp \!\left ( -\frac {c n}{K^4} \min (u^2, u) \right ). \tag {3.1} \] (Here we used that \(K^4 \geq K^2\) since we assumed that \(K \geq 1\).)

This is a good concentration inequality for \(\|X\|_2^2\), from which we are going to deduce a concentration inequality for \(\|X\|_2\). To make the link, we can use the following elementary observation that is valid for all numbers \(z \geq 0\): \[ |z - 1| \geq \delta \;\implies \; |z^2 - 1| \geq \max (\delta , \delta ^2). \tag {3.2} \] We obtain for any \(\delta \geq 0\) that \begin{align*} \mathbb {P}\!\left \{ \left | \tfrac {1}{\sqrt {n}} \|X\|_2 - 1 \right | \geq \delta \right \} &\leq \mathbb {P}\!\left \{ \left | \tfrac {1}{n} \|X\|_2^2 - 1 \right | \geq \max (\delta , \delta ^2) \right \} \\ &\leq 2 \exp \!\left ( -\frac {c n}{K^4} \cdot \delta ^2 \right ) . \end{align*}

Changing variables to \(t = \delta \sqrt {n}\), we obtain the desired sub-Gaussian tail \[ \mathbb {P}\!\left \{ \big | \|X\|_2 - \sqrt {n} \big | \geq t \right \} \leq 2 \exp \!\left ( -\frac {c t^2}{K^4} \right ) \quad \text {for all } t \geq 0. \tag {3.3} \] This is equivalent to the conclusion of the theorem. □

Proof. Let \(K = \frac {\pi }{\log (1 + \sqrt {2})}\). We first prove that there exists a Hilbert space \(H\) and maps \(\Psi , \Phi : S(\mathbb {R}^n) \to S(H)\) such that for all \(u, v \in \mathbb {R}^n\): \[ \langle u, v \rangle = \frac {2K}{\pi } \arcsin \langle \Psi (u), \Phi (v) \rangle . \] Proof. We first describe tensor inner products: for \(T = u^{\otimes 3} \in \mathbb {R}^{n \times n \times n}\) defined by \(T_{ijl} = u_i u_j u_l\), we have \(\langle T, S \rangle = \sum _{ijl} T_{ijl} S_{ijl}\). By Taylor expansion, \begin{align*} \arcsin (\langle u, v \rangle ) &= \langle u, v \rangle + \frac {1}{3!} \langle u, v \rangle ^3 + \frac {3}{5!} \langle u, v \rangle ^5 + \cdots \\ &= \langle u, v \rangle + \frac {1}{3!} \langle u^{\otimes 3}, v^{\otimes 3} \rangle + \frac {3}{5!} \langle u^{\otimes 5}, v^{\otimes 5} \rangle + \cdots \\ &= \left \langle \begin {bmatrix} u \\ \sqrt {\frac {1}{3!}}\, u^{\otimes 3} \\ \sqrt {\frac {3}{5!}}\, u^{\otimes 5} \\ \vdots \end {bmatrix}, \begin {bmatrix} v \\ \sqrt {\frac {1}{3!}}\, v^{\otimes 3} \\ \sqrt {\frac {3}{5!}}\, v^{\otimes 5} \\ \vdots \end {bmatrix} \right \rangle . \end{align*}

We define \[ \Psi (u) = \begin {bmatrix} u \\ \sqrt {\frac {1}{3!}}\, u^{\otimes 3} \\ \sqrt {\frac {3}{5!}}\, u^{\otimes 5} \\ \vdots \end {bmatrix}, \qquad \Phi (v) = \begin {bmatrix} v \\ \sqrt {\frac {1}{3!}}\, v^{\otimes 3} \\ \sqrt {\frac {3}{5!}}\, v^{\otimes 5} \\ \vdots \end {bmatrix}, \] which proves the claim. Next we prove the original inequality: \begin{align*} \sum _{i,j} B_{ij} \langle u_i, v_j \rangle &= K \sum _{i,j} B_{ij} \cdot \frac {2}{\pi } \arcsin \langle \Psi (u_i), \Phi (v_j) \rangle \\ &= K \sum _{i,j} B_{ij}\, \mathbb {E}_{w \sim \text {Gaussian}}\!\left [ \mathrm {sign}\langle w, \Phi (u_i) \rangle \cdot \mathrm {sign}\langle w, \Psi (v_j) \rangle \right ] \\ &\leq K \max _{x_i, y_j \in \{\pm 1\}} \left | \sum _{i,j} B_{ij} x_i y_j \right |. \end{align*}

This completes the proof. □