Some Solutions to High dimensional probability (Vershynin)

I give you no guarantees on the correctness of these solutions.

1. 5.4.5


1.1. F

If \(Y = I\), then

\begin{align*} 0 &\preceq X \preceq I \\ \iff 0 &\preceq I \preceq X ^{-\frac{1 }{2 }} X ^{- \frac{1}{2}} \\ \iff 0 &\preceq I \preceq X ^{-1} \end{align*}

\(X ^{-\frac{1}{2}}\) exist since \(X \succeq 0\) is positive semi-definite. Then

\begin{align*} 0 &\preceq X \preceq Y \\ \iff 0 &\preceq Y ^{-\frac{1 }{2 }} X Y ^{- \frac{1}{2}} \preceq I \\ \end{align*}

Suppose \(X = Y ^{-\frac{1 }{2 }} X Y ^{- \frac{1}{2}} \)

\begin{align*} &0 \preceq I \preceq X ^{-1} \\ &0 \preceq I \preceq \left( Y ^{-\frac{1 }{2 }} X Y ^{- \frac{1}{2}} \right) ^{-1} \\ &0 \preceq I \preceq Y ^{\frac{1 }{2 }} X ^{-1} Y ^{\frac{1}{2}} \\ &0 \preceq Y ^{-\frac{1}{2}} Y ^{-\frac{1}{2}} \preceq X ^{-1}\\ &\iff Y ^{-1} \preceq X ^{-1} \end{align*}

1.2. G

\begin{align*} \log \left( X \right) &= \int _{0} ^{\infty} \left( \frac{1}{1 + t } - \frac{1}{X + t} \right) dt \\ \log \left( X \right) - \log \left( Y \right) &= \int _{0} ^{\infty} \left( \frac{1}{Y + t } - \frac{1}{X + t} \right) dt \\ \log \left( X \right) - \log \left( Y \right) &= \int _{0} ^{\infty} \left( \left( Y + t \right) ^{-1} - \left( X + t \right) ^{-1} \right) dt \end{align*}

We have

\begin{align*} 0 \preceq & X \preceq Y \\ \iff t \preceq X + t &\preceq Y + t \\ \iff \left( X + t \right) ^{-1} &\succeq \left( Y + t \right) ^{-1} \\ \iff \left( Y + t \right) ^{-1} &- \left( X + t \right) ^{-1} \preceq 0 \end{align*}


\begin{align*} \log \left( X \right) - \log \left( Y \right) &= \int _{0} ^{\infty} \left( \left( Y + t \right) ^{-1} - \left( X + t \right) ^{-1} \right) dt \\ \log \left( X \right) - \log \left( Y \right) &\preceq 0 \\ \log \left( X \right) &\preceq \log \left( Y \right) \end{align*}

2. 5.4.11


Given the Matrix Bernstein's Inequality, where \(X_1 , \dots, X_N\) are independent, mean zero, \(n\times n\) symmetric random matrices for \(t \geq 0\). We assert that

\begin{align*} \mathbb{P} \left\{ \left\| X \right\| \geq t \right\} \leq 2 n \exp \left\{ \frac{- t^2/2}{σ^2 + K \left( \frac{t}{3} \right)} \right\} &\leq 2 e ^{-u} \\ \iff \log \left( 2 \right) + \log \left( n \right) - \frac{t^2/2}{σ^2 + K \left( \frac{t}{3} \right)} &\leq \log \left( 2 \right) - u \end{align*}

Set \(t = \sqrt{2} \left[ \sqrt{ σ^2 \left( \log \left( n \right) + u \right)} + K \left( u + \log \left( n \right) \right) \right]\), then

\begin{align*} \frac{-t^2}{2} &= - \left( σ^2 \left( \log \left( n \right) + u \right) + 2K \left( \log \left( n \right) + u \right) \sqrt{ σ^2 \left( \log \left( n \right) + u \right)} + K^2 \left( \log \left( n \right) + u \right)^2 \right)\\ σ^2 + K \left( \frac{t}{3} \right) &= σ^2 + \frac{2K}{3} \left( \sqrt{\sigma ^2 \left( \log \left( n \right) + u \right) } + K \left( \log \left( n \right) + u \right) \right) \end{align*} \begin{align*} - \frac{t^2/2}{σ^2 + K \left( \frac{t}{3} \right)} &= \frac{-\left( σ^2 \left( \log \left( n \right) + u \right) + 2K σ \left( \log \left( n \right) + u \right) \sqrt{ \left( \log \left( n \right) + u \right)} + K^2 \left( \log \left( n \right) + u \right)^2 \right)} {σ^2 + \frac{2Kσ}{3} \sqrt{ \sigma ^2 \left( \log \left( n \right) + u \right) } + \frac{2K^2}{3} \left( \log \left( n \right) + u \right) } \\ &\approx -\left( \log \left( n \right) + u \right) \left( \frac{σ^2 + 2K σ \sqrt{ \log \left( n \right) + u } + K^2 \left( \log \left( n \right) + u \right) } {σ^2 + \frac{2Kσ}{3} \sqrt{\log \left( n \right) + u } + \frac{2K^2}{3} \left( \log \left( n \right) + u \right) } \right) \\ & \lesssim - \left( \log \left( n \right) + u \right) \end{align*}

We can verify whether our previous assertion by

\begin{align*} \log \left( n \right) - \frac{t^2/2}{σ^2 + K \left( \frac{t}{3} \right)} &\leq -u \\ \log \left( n \right) - \left( \log \left( n \right) + u \right) &\leq - u \\ -u &\leq -u \end{align*}


\begin{align*} \mathbb{P} \left\{ \left\| \sum _{i=1} ^{N} X_i \right\| \geq \sqrt{2} \left( σ \sqrt{ \log \left( n \right) + u } + K \left( u + \log \left( n \right) \right) \right) \right\} &\leq \mathbb{P} \left\{ \left\| \sum _{i=1} ^{N} X_i \right\| \geq σ \sqrt{ \log \left( n \right) + u } + K \left( u + \log \left( n \right) \right) \right\} \end{align*}


\begin{align*} \left\| \sum _{i=1} ^{N} X_i \right\| &\leq t \\ &\leq σ \sqrt{ \log \left( n \right) + u } + K \left( u + \log \left( n \right) \right) \\ &\leq \left( \left\| \sum _{i=1} ^{N} \mathbb{E} X_i^2 \right\| \right) ^{\frac{1}{2}} \sqrt{u + \log \left( n \right)} + K \left( u + \log \left( n \right) \right) \end{align*}

with probability at least \(1 - 2 e ^{-u}\). We can calculate the expectation directly by

\begin{align*} \mathbb{E} X &= \int _{0} ^{∞} \mathbb{P} \left\{ X > t \right\} dt \\ \mathbb{E} \left\| \sum _{i=1} ^{N} X_i \right\| &= \int _{0} ^{∞} \mathbb{P} \left\{ \left\| \sum _{i=1} ^{N} X_i \right\| > t \right\} dt \\ %% &= \int _{0} ^{t_0} \mathbb{P} \left\{ \left\| \sum _{i=1} ^{N} X_i \right\| \geq t \right\} dt + \int _{t_0} ^{∞} \mathbb{P} \left\{ \left\| \sum _{i=1} ^{N} X_i \right\| \geq t \right\} dt \\ &\leq \int _{0} ^{∞} 2 e ^{-u} dt \\ \text{Differentiating } u &\Longrightarrow t = σ \sqrt{ \log \left( n \right) + u } + K \left( u + \log \left( n \right) \right) \\ &\Longrightarrow \frac{dt}{du} = \frac{σ}{2} \left( \log \left( n \right) + u \right) ^{-\frac{1}{2}} + K \\ &\leq \int _{0} ^{∞} 2 e ^{-u} \left( \frac{σ}{2 \sqrt{ \log \left( n \right) + u }} +K \right) du \\ &\leq \int _{0} ^{∞} \left( \frac{ σ e ^{-u}}{ \sqrt{ u }} + 2K e ^{-u} \right) du \\ &= σ\sqrt{\pi} + 2K \\ &\lesssim σ \sqrt{ \log \left( n \right) + u } + K \left( \log \left( n \right) + u \right) \end{align*}

To conclude

\begin{align*} \mathbb{E} \left\| \sum _{i=1} ^{N} X_i \right\| \lesssim \left( \left\| \sum _{i=1} ^{N} \mathbb{E} X_i^2 \right\| \right) ^{\frac{1}{2}} \sqrt{u + \log \left( n \right)} + K \left( u + \log \left( n \right) \right) \end{align*}

Let \(u = 1\), then

\begin{align*} \mathbb{E} \left\| \sum _{i=1} ^{N} X_i \right\| ≲ \left\| \sum _{i=1} ^{N} \mathbb{E} X_i^2 \right\| ^{\frac{1}{2}} \sqrt{ 1 + \log \left( n \right)} + K \left( 1 + \log \left( n \right) \right) \end{align*}

3. 5.4.13


3.1. A

We know that

\begin{align*} σ^2 &= \left\| \mathbb{E} \left(\sum _{i=1} ^{N} ϵ_i A_i \right)^2 \right\| \\ &= \left\| \sum _{i=1} ^{N} \sum _{j=1} ^{N} \mathbb{E} \left[ ϵ_i ϵ_j \right] A_i A_j \right\| \\ &= \left\| \sum _{i=1} ^{N} A_i ^2 \right\| \end{align*}

We can approximate for the expectation directly

\begin{align*} \mathbb{E} \left\| \sum _{i=1} ^{N} ϵ_i A_i \right\| &\approx \mathbb{E} \left\| \sum _{i=1} ^{n} a_i A_i \right\| & \text{Central limit Theorem} \\ &= \mathbb{E} \left[ \max _{i=1, \dots, d} \left| a_i \right|^2 \right]\\ &\approx 2 σ^2 \log \left( n \right) \end{align*}

where \(a_i\) are independent standard normal variables. Therefore

\begin{align*} \left( \mathbb{E} \left\| \sum _{i=1} ^{N} ϵ_i A_i \right\|^2 \right) ^{\frac{1}{2}} \approx \sqrt{2 σ^2 \log (n)} \end{align*}

The last approximation we can be proven as follows:
Let \(X_1 , \dots , X_n\) be a sequence of zero mean sub-Gaussian random variables with parameter \(σ\)

\begin{align*} e ^{λ \mathbb{E} \left[ \max \left\{ X_1, \dots, X_n \right\} \right]} &\leq \mathbb{E} \left[ e ^{λ \max \left\{ X_1, \dots, X_n \right\} } \right] & \text{Jensen's Inequality} \\ &= \mathbb{E} \left[ \max \left\{ e ^{λ X_1} , \dots , e ^{λ X_n} \right\} \right] \\ &\leq \sum _{i=1} ^{n} \mathbb{E} \left[ e ^{λ X_i} \right] &\text{Union Bound} \\ &\leq n e ^{\frac{λ^2 σ^2}{2}} & \text{SubGaussian Definition} \\ \iff λ \mathbb{E} \left[ \max \left\{ X_1, \dots , X_n \right\} \right] &\leq \log \left( n \right) + \frac{λ^2 σ^2}{2} \\ \mathbb{E} \left[ \max \left\{ X_1, \dots , X_n \right\} \right] &\leq \frac{\log \left( n \right)}{λ} + \frac{λ σ^2}{2} \\ \text{Differentiating } λ &\Longrightarrow - \frac{\log \left( n \right)}{λ^2} + \frac{σ^2}{2} \\ & \Longrightarrow λ^* = \sqrt{\frac{2 \log \left( n \right)}{σ^2}} \\ \mathbb{E} \left[ \max \left\{ X_1, \dots , X_n \right\} \right] &\leq \frac{\log \left( n \right)}{\sqrt{\frac{2 \log \left( n \right)}{σ^2}}} + \frac{σ^2 \sqrt{\frac{2 \log \left( n \right)}{σ^2}}}{2} \\ &= σ \sqrt{2 \log \left( n \right)} \end{align*}

Since \(1 + \log \left( n \right) \geq 2 \log \left( n \right)\) for \(n \geq 1\), we can conclude the proof

\begin{align*} \mathbb{E} \left\| \sum _{i=1} ^{N} ϵ_i A_i \right\| &\leq \left( \mathbb{E} \left\| \sum _{i=1} ^{N} ϵ_i A_i \right\|^2 \right) ^{\frac{1}{2}} &\text{Jensen's Inequality} \\ &\approx σ \sqrt{2 \log (n)} \\ &\leq C σ \sqrt{ 1 + \log \left( n \right) } \\ &= C \sqrt{ 1 + \log \left( n \right) } \left\| \sum _{i=1} ^{N} A_i^2 \right\| ^{\frac{1}{2}} \end{align*}

3.2. B

We know that for \(X_1, \dots , X_n \) sequence of subgaussian random variables with parameter \(σ\).

\begin{align*} \mathbb{P} \left\{ X \geq a \right\} &= \mathbb{P} \left\{ \exp \left\{ tX \right\} \geq \exp \left\{ t a \right\} \right\} \\ &\leq \frac{\mathbb{E} \left[ \exp \left\{ tX \right\} \right]}{\exp \left\{ ta \right\} } & \text{Markov's Inequality} \\ &\leq \exp \left\{ \frac{σ^2 t^2}{2} - t a \right\} & \text{SubGaussian Definition} \\ \text{Differentiating } t &\Longrightarrow t^* = \frac{a}{σ^2} \\ \mathbb{P} \left( X \geq a \right) &\leq \exp \left\{ -\frac{a^2 }{2 σ^2 } \right\} & \text{Chernoff Inequality} \\ \mathbb{E} \left| X \right| ^{p} &= \int _{0} ^{∞} \mathbb{P} \left( \left| X \right|^p \geq t \right) dt \\ &= \int _{0} ^{∞} \mathbb{P} \left( \left| X \right| \geq t ^{\frac{1}{p}} \right) dt \\ &\leq 2 \int _{0} ^{∞} \exp \left\{ -\frac{ t ^{\frac{2}{p}}}{2 σ^2 } \right\} dt \\ &\leq C σ ^{p} p ^{\frac{p}{2}} \\ \left( \mathbb{E} \left| X \right| ^{p} \right) ^{\frac{1}{p}} &\leq C σ \sqrt{p} \\ \end{align*}

Therefore, using similar argument as part (a), we have

\begin{align*} \mathbb{E} \left\| \sum _{i=1} ^{N} ϵ_i A_i \right\| &\leq \left( \mathbb{E} \left\| \sum _{i=1} ^{N} ϵ_i A_i \right\| ^{p} \right) ^{\frac{1}{p}} & \text{Jensen's Inequality} \\ &\approx C σ \sqrt{p} \\ &\leq C σ \sqrt{p + \log \left( n \right)} \\ &= C \sqrt{p + \log \left( n \right)} \left\| \sum _{i=1} ^{N} A_i^2 \right\| ^{\frac{1}{2}} \end{align*}

4. 5.4.15




\begin{align*} Z_i = \begin{bmatrix} 0 _{n \times n} & \left( X _{i} ^{T} \right) _{n \times m} \\ \left(X_i \right)_{ m \times n} & 0 _{m \times m} \end{bmatrix} \in \mathbb{S} ^{m + n} \end{align*}

Since the block matrix is symmetric we can apply matrix Bernstein's inequality and \(\left\| Z_i \right\|\leq K\),

For \( Z_1 , \dots , Z_N \in \mathbb{S} ^{m + n}\)

\begin{align*} \mathbb{P} \left\{ \left\| \sum _{i=1} ^{N} Z_i \right\| \geq t \right\} &\leq 2 \left( m + n \right) \exp \left\{ \frac{-t^2/2}{σ^2 + K \left( \frac{t}{3} \right)} \right\} \\ &= 2 \left( m + n \right) \exp \left\{ -c \left( \frac{t^2}{σ^2} \wedge \frac{t}{K} \right) \right\} \end{align*}

The non-zero eigenvalues of \(Z_i\) are the same as the singular values of \(X_i\) due to the block matrix structure of \(Z_i\),

\begin{align*} \left\| \sum _ {i=1} ^{N} Z_i \right\| &= \left\| \begin{bmatrix} 0 _{n \times n} & \left( \sum _{i = 1} ^{N} X _{i} ^{T} \right) _{n \times m} \\ \left( \sum _{i=1} ^{N} X_i \right)_{ m \times n} & 0 _{m \times m} \end{bmatrix} \right\| \\ &= \left\| \sum _{i=1} ^N X_i \right\| = \left\| \sum _{i = 1} ^N X_i^T \right\| \end{align*}


\begin{align*} \mathbb{P} \left\{ \left\| \sum _{i=1} ^{N} X_i \right\| \geq t \right\} &\leq 2 \left( m + n \right) \exp \left\{ \frac{-t^2/2}{σ^2 + K \left( \frac{t}{3} \right)} \right\} \end{align*}


\begin{align*} Z_i ^2 = Z_i Z_i &= \begin{bmatrix} 0 _{n \times n} & \left( X _{i} ^{T} \right) _{n \times m} \\ \left(X_i \right)_{ m \times n} & 0 _{m \times m} \end{bmatrix} \begin{bmatrix} 0 _{n \times n} & \left(X_i ^T \right)_{ n \times m} \\ \left( X _{i} \right) _{m \times n} & 0 _{m \times m} \end{bmatrix} \\\ &= \begin{bmatrix} \left( X_i X_i ^T \right)_{ n \times n } & 0 _{n \times m} \\ 0 _{m \times n} & \left( X_i ^T X _{i} \right) _{m \times m} \end{bmatrix} \end{align*} \begin{align*} σ^2 &= \left\| \sum _{i=0} ^{N} \mathbb{E} Z_i^2 \right\| \\ &= \left\| \begin{bmatrix} \sum _{i=0} ^{N} \mathbb{E} \left( X_i X_i ^T \right)_{ n \times n } & 0 _{n \times m} \\ 0 _{m \times n} & \sum _{i=0} ^{N} \mathbb{E} \left( X_i ^T X _{i} \right) _{m \times m} \end{bmatrix} \right\| \\ &= \max \left\{ \left\| \sum _{i=0} ^{N} \mathbb{E} \left[ X_i^T X_i \right] \right\| , \left\| \sum _{i=0} ^{N} \mathbb{E} \left[ X_i X_i^T \right] \right\| \right\} & \text{By definition} \end{align*}

Created: 2024-04-19 Fri 14:33