Problem: Let $A = (a_{ij}): l_2^k \to l_2^N$ be a random matrix whose coefficients $a_{ij}$ are independent, centered, $\psi_2$ (the definition is in this post) and satisfy.
\begin{align*}
\exists K>0, \forall i,j: \Vert a_{ij}\Vert_{\psi_2} \le K.
\end{align*}
Prove that $\exists c >0$ (independent of everything) such that $\forall t>0$
\begin{align*}
\mathbb{P}\left(\Vert A \Vert \ge cK(\sqrt{N} + \sqrt{K} + t)\right) \le 2\exp(-t^2).
\end{align*}
My attempt: There is two closely related inequality that I have proved but I have not thought how to combine it to tackle with the problem
-
$\forall x \in S^{k-1}$, $\forall y \in S^{N-1}$, $\forall t >0$
\begin{align*}
\mathbb{P}\left(\sum_{i,j}a_{ij}x_jy_i > t\right) \le \exp\left(-\dfrac{t^2}{4K^2}\right).
\end{align*} -
Let $\mathcal{N}$ be an $\varepsilon$-net of $S^{k-1}$ and $\mathcal{M}$ be an $\varepsilon$-net of $S^{N-1}$
\begin{align*}
\sup_{x \in \mathcal{N},\ y \in \mathcal{M}} \langle Ax,y\rangle \le \Vert A \Vert \le \dfrac{1}{1-2\varepsilon} \sup_{x \in \mathcal{N}, y \in \mathcal{M}} \langle Ax,y \rangle. \tag{*}
\end{align*}
I wonder is there any relation between $\mathbb{P}(\Vert A\Vert>\text{constant})$ with $\mathbb{P}\left(\sum_{i,j}a_{ij}x_jy_i > \text{constant}\right)$
Best Answer
Before starting the proof for this question, I would like to provide some following results which were proved here that we will use then in the main proof.
Corollary (Covering numbers of the Euclidean ball).The covering numbers of the unit Euclidean ball $B_2^n$ satisfy the following for any $\varepsilon>0$ : $$ \left(\frac{1}{\varepsilon}\right)^n \leq \mathcal{N}\left(B_2^n, \varepsilon\right) \leq\left(\frac{2}{\varepsilon}+1\right)^n . $$ The same upper bound is true for the unit Euclidean sphere $S^{n-1}$.
Now, let us go back to the main proof.
Step 1: Approximation. Choose $\varepsilon=1 / 4$. Using corollary 1, we can find an $\varepsilon$-net $\mathcal{N}$ of the sphere $S^{k-1}$ and $\varepsilon$-net $\mathcal{M}$ of the sphere $S^{N-1}$ with cardinalities \begin{align*} |\mathcal{N}| \leq 9^k \quad \text { and } \quad|\mathcal{M}| \leq 9^N . \tag{5.1} \end{align*}
By the inequality was proved in my attempt in the question, the operator norm of $A$ can be bounded using these nets as follows: \begin{align*} \|A\| \leq \dfrac{1}{1-2\times\dfrac{1}{4}}\max _{x \in \mathcal{N}, y \in \mathcal{M}}\langle A x, y\rangle = 2 \max _{x \in \mathcal{N}, y \in \mathcal{M}}\langle A x, y\rangle. \tag{5.2} \end{align*} Step 2: Concentration. Fix $x \in \mathcal{N}$ and $y \in \mathcal{M}$. Then, we have $$ \langle A x, y\rangle=\sum_{j=1}^k \sum_{i=1}^N a_{i j} x_i y_j $$
Recalling the result in the result in my attempt (ineq 1.), we can restate this as the tail bound \begin{align*} \mathbb{P}\{\langle A x, y\rangle \geq u\} \leq \exp \left(-u^2 / 4K^2\right), \quad u \geq 0. \tag{5.3} \end{align*}
Step 3: Union bound. Next, we unfix $x$ and $y$ using a union bound. Suppose the event $\max _{x \in \mathcal{N}, y \in \mathcal{M}}\langle A x, y\rangle \geq u$ occurs. Then there exist $x \in \mathcal{N}$ and $y \in \mathcal{M}$ such that $\langle A x, y\rangle \geq u$. Thus the union-bound yields $$ \mathbb{P}\left\{\max _{x \in \mathcal{N}, y \in \mathcal{M}}\langle A x, y\rangle \geq u\right\} \leq \sum_{x \in \mathcal{N}, y \in \mathcal{M}} \mathbb{P}\{\langle A x, y\rangle \geq u\} . $$
Using the inequality (5.3) and the estimate (5.1) on the sizes of $\mathcal{N}$ and $\mathcal{M}$, we bound the probability above by \begin{align*} 9^{k+N} \cdot \exp \left(- u^2 / 4K^2\right). \tag{5.4} \end{align*}
If we choose $u=\dfrac{1}{2}C K(\sqrt{N}+\sqrt{k}+t)$, then $u^2 \geq \dfrac{1}{4}C^2 K^2\left(k+N+t^2\right)$, and if the constant $C$ is chosen sufficiently large, the exponent in (5.4) is large enough, say $ u^2 / 4K^2 \geq 3(k+N)+t^2$. Thus \begin{align*} \mathbb{P}\left\{\max _{x \in \mathcal{N}, y \in \mathcal{M}}\langle A x, y\rangle \geq u\right\} &\leq 9^{k+N} \cdot \exp \left(-3(k+N)-t^2\right)\\ &\leq \exp \left(-t^2\right)\\ & \leq 2\exp\left(-t^2\right). \end{align*} Finally, combining this with the inequality (5.2), we can derive that $$ \mathbb{P}\{\|A\| \geq 2 u\} \leq 2 \exp \left(-t^2\right) . $$
By the choice of $u$, we finally obtain that \begin{align*} \mathbb{P}\left\{\|A\| \ge C K(\sqrt{N}+\sqrt{k}+t)\right\} \le 2\exp\left(-t^2\right). \end{align*}