6
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ 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)\}$. $\endgroup$ Jan 5, 2020 at 20:32

1 Answer 1

4
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

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