Let $A \in \mathbb R^{n\times m}$ be a matrix with independent $1-$subgaussian entries. I have the following bound on the expectation which I derived using a discretization bound:

$$\mathbb E \|A\|_{op} \leq C (\sqrt n + \sqrt m)$$

for some constant $C>0$.

From this we have the obvious concentration inequality using a Markov bound. But this seems very coarse.

Seeking to apply a chernoff bound, I tried to bound the moment generating function of $\|A\|_{op}$, since I expect it to at least be subexponential, but had difficulty deriving a bound that depends on the operator norm, not the frobenius norm.

My question

How can I bound the deviation probability of $\|A\|_{op}$? A bound on the moment generating function would be enough for me, but if there is another method, that would be helpful too.


1 Answer 1


This can be done by recognizing that:

$$\|x\|=\sup_{\|y\|=1} \langle x, y \rangle \leq \frac{1}{1-\epsilon}\max_{ y \in \mathcal N_\epsilon} \langle x, y \rangle$$

where $\mathcal N_\epsilon$ is an $\epsilon$-cover of the unit euclidean ball.

This leads to the following bound on the operator norm:

$$\|A\|_{op} \leq \frac{1}{1-2\epsilon} \max_\theta \langle A, \theta\rangle$$

where the max is taken over an $\epsilon$ cover of the set of rank 1 matrices with frobenius norm 1.

From here it's clear to apply a union bound after recognizing that the inner product is subgaussian.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .