# Matrix Kintchine inequality proof Exercise 5.4.13

I have been trying to solve every question from Vershynin's book right now for self study. The following question I am having trouble proving is Exercise 5.4.13 part (b) from Vershynin's book, High Dimensional Probability.

$$\textbf{Exercise 5.4.13}$$ (Matrix Kintchine's inequality) Let $$\epsilon_1, \dots, \epsilon_N$$ be independent symmetric Bernoulli random variables and let $$A_1, \dots, A_N$$ be symmetric $$n\times n$$ matrices(deterministic)

(b) Prove that for every $$p\in[1,\infty)$$ we have

$$\left(\mathbb{E} \left|\left| \sum_{i=1}^N \epsilon_i A_i\right|\right|^p\right)^{1/p} \leq C\sqrt{p+\ln(n)} \left|\left| \sum_{i=1}^N A_i^2 \right|\right|^{1/2}$$

Where C is an absolute constant.

I have been trying to use the result of Exercise 5.4.12(Matrix Hoeffding's inequality) to solve Exercise 5.4.13 part (b).

(Matrix Hoeffding's inequality) If $$\epsilon_1,\cdots,\epsilon_N$$ are independent symmetric Bernoulli random variables and $$A_1,\cdots,A_N$$ are symmetric $$n\times n$$ matrices then for any $$t\geq 0$$ we have

$$P\left\{\left\lVert \sum_{i=1}^N \epsilon_i A_i \right\rVert \geq t\right\}\leq 2n\exp\left(-\frac{t^2}{2\sigma^2}\right)$$

where $$\sigma^2 = \left\lVert\sum_{i=1}^N A_i^2\right\rVert$$.

I have been trying to use Hoeffding's inequality above with the following simple relation

If $$X$$ is a nonnegative random variable and $$p\in [1,\infty)$$ then

$$\mathbb EX^p = \int_0^\infty pt^{p-1} P(X\geq t)dt$$

But I still haven't been able to prove the exercise. I was wondering if anyone had a hint or could sketch out a quick proof.

• The bound given in Exercise 5.4.12 is good when $t$ is large but not so much for small $t$. Letting $X=\lVert \sum_{i=1}^N\epsilon_iA_i\rVert$, we can use the bound $P(X>t)\leqslant \min\{1,2\exp\left(-\frac{t^2}72\sigma^2\right)\}$. Jan 5, 2020 at 20:32

It is a straightforward integration of the tail bound. Just note that you should upper bound the tail probability by $$1$$ for small $$t$$.
For notational convenience, let $$Z = \left\|\sum_i \epsilon_i A_i\right\|_{op}$$ and we seek to upper bound $$(\mathbb{E} Z^p)^{1/p}$$. Write $$\mathbb{E} Z^p = \int_0^\infty \Pr\{Z^p \geq t\} dt = \int_0^T \Pr\{Z^p \geq t\} dt + \int_T^\infty \Pr\{Z^p \geq t\} dt,$$ where $$T$$ is to be determined. It follows that \begin{align*} (\mathbb{E} Z^p)^{1/p} &\leq \left(\int_0^T \Pr\{Z^p \geq t\} dt\right)^{1/p} + \left(\int_T^\infty \Pr\{Z^p \geq t\} dt\right)^{1/p} \\ &\leq T^{1/p} + \left(\int_T^\infty \Pr\{Z^p \geq t\} dt\right)^{1/p}. \end{align*}
Note that when $$t \geq \sqrt{2/c}\cdot \sigma\sqrt{\ln n}$$ we have that $$\Pr\{Z \geq t\} \leq 2n\exp\left(-\frac{ct^2}{\sigma^2}\right) \leq 2 \exp\left(-\frac{c}{2}\cdot \frac{t^2}{\sigma^2}\right),$$ which agrees with the tail bound of some subgaussian variable $$Y$$ with $$\|Y\|_{\psi_2}\leq c''\sigma$$. Let $$T = (\sqrt{2/c}\cdot \sigma\sqrt{\ln n})^p$$, we have $$\left(\int_T^\infty \Pr\{Z^p \geq t\} dt\right)^{1/p} \leq \left(\int_T^\infty \Pr\{|Y|^p \geq t\} dt\right)^{1/p} \leq (\mathbb{E} |Y|^p)^{1/p} \leq C\sqrt{p}\sigma.$$ for some absolute constant $$C$$. It follows immediately that $$(\mathbb{E} Z^p)^{1/p} \leq \sqrt{\frac{2}{c}}\cdot \sqrt{\ln n}\cdot \sigma + C\sqrt{p}\sigma \leq C''(\sqrt{p + \ln n})\sigma$$ as desired.