Let $X^{(1)},\dots,X^{(n)}$ be a i.i.d. sample of a Gaussian distribution $\mathcal N (0,\Sigma)$ in $\mathbb{R}^p$ with $\Sigma$ nonsingular and $K = \Sigma^{-1}$ sparse. In this exercise, we investigate the estimation of $K$ with a matrix version of the Dantzig selector defined as :
(1)where $\widehat{\Sigma} = \frac{1}{n} \Sigma_{i=1}^n X^{(i)}(X^{(i)})^T$ is the empirical covariance matrix, $\lambda$ is a non negative real number and where for any $(r,s) \in {\mathbb{N}^*}^{2}$ and any matrix $A \in m_{r,s}(\mathbb{R})$, we define :
$$ \lvert A \rvert _{\infty} = \underset{(i,j) \in \{1,\dots,r\}\times\{1,\dots,s\}}{max}\left(\left\lvert A_{i,j} \right\rvert\right) $$
and
$$ \lvert A \rvert _{1,\infty} = \underset{j \in \{1,\dots,s\}}{max}\left(\Sigma_{i=1}^r\left\lvert A_{i,j} \right\rvert\right) = max(\lvert A_1 \rvert_{1},\dots,\lvert A_s \rvert_{1}). $$
Furthermore, for any $(r,s) \in {\mathbb{N}^*}^{2}$ and any matrix $A \in m_{r,s}(\mathbb{R})$, $A_j$ refers to the $j$-th column of $A$.
Before going further, we are going to prove inequalities linking the two defined matrix norms $\lvert \; \rvert _{\infty}$ and $\lvert \; \rvert _{1,\infty}$ under different assumptions and say why the solution to (1) given later by $\widetilde{K}$ is interesting in terms of computational costs.
1.
Let $(r,s,t)$ be a triple of non-negative numbers and $\left(A,B\right) \in m_{r,s}(\mathbb{R}) \times m_{s,t}(\mathbb{R})$.
- Let us prove that $\left\lvert AB \right\rvert _{\infty} \leq \left\lvert A \right\rvert _{\infty} \left\lvert B \right\rvert _{1,\infty}$.
As it holds for any $(i,j) \in \{1,\dots,r\}\times\{1,\dots,t\}$ :
(2)By definition of $\lvert AB \rvert _{\infty}$ as $max( \lvert \left( AB \right)_{i,j}\rvert / (i,j) \in \{1,\dots,r\} \times \{1,\dots,t\})$ , we conclude :
$$ \boxed{ \begin{equation} \lvert AB \rvert _{\infty} \leqslant \lvert A \rvert _{\infty} \lvert B \rvert _{1,\infty}. \end{equation} } $$
- Let us prove when $A$ is also assumed symmetric that $\left\lvert AB \right\rvert _{\infty} \leq \left\lvert A \right\rvert _{1,\infty} \left\lvert B \right\rvert _{\infty}$.
By symmetry of $A$, for any $(i,l)$ in $\{1,\dots,r\}^2, \; A_{i,l} = A_{l,i}$ and so it holds for any $(i,j) \in \{1,\dots,r\}\times\{1,\dots,t\}$ :
(3)By definition of $\lvert AB \rvert _{\infty}$ as $max( \lvert \left( AB \right)_{i,j}\rvert / (i,j) \in \{1,\dots,r\} \times \{1,\dots,t\})$, in the case $A$ is a symmetric matrix, we conclude :
$$ \boxed{ \begin{equation} \lvert AB \rvert _{\infty} \leqslant \lvert A \rvert _{1,\infty} \lvert B \rvert _{\infty}. \end{equation} } $$
2.
Writing $e_j$ the $j$-th vector of the canonical basis of $\mathbb{R}^p$, we define the matrix $\widetilde{K} \in m_{p,p}(\mathbb{R})$ where for any $(i,j) \in \{1,\dots,p\}^2$, $\widetilde{K}_{i,j} = \widehat{\beta}_i^{(j)}$ with :
(4)- Let us check first that $\widetilde{K} \in \{ B \in m_{p,p}(\mathbb{R}) / \lvert \widehat{\Sigma}B - I_p \rvert _{\infty} \leq{\lambda} \}$.
Starting from the definition of $\widetilde{K}$, it comes for any $(i,j) \in \{1,\dots,p\}^2$ :
(5)Since for any $j \in \{1,\dots,p\}$, $\widehat{\beta^{(j)}}$ is solution of optimization problem (4), it holds $\lvert \widehat{\Sigma}\widehat{\beta^{(j)}} - e_{j} \rvert_{\infty} \leqslant \lambda$ and we get $\forall (i,j) \in \{1,\dots,p\}^2\text{, }\;\lvert (\widehat{\Sigma}\widetilde{K}-I_p)_{i,j} \rvert \leqslant \lambda$.
By definition of $\lvert \; \rvert_{\infty}$, it then comes $\lvert \widehat{\Sigma}\widetilde{K}-I_p \rvert_{\infty} \leqslant \lambda$ and consequently :
$$ \boxed{ \begin{equation} \widetilde{K} \in \{ B \in m_{p,p}(\mathbb{R}) / \lvert \widehat{\Sigma}B - I_p \rvert _{\infty} \leqslant \lambda \}. \end{equation} } $$
- Let us conclude that $\widetilde{K}$ is a solution of optimization problem (1)
$\widetilde{K}$ being a solution to optimization problem (1) meaning that for any $B \in m_{p,p}(\mathbb{R})$ such that $\lvert \widehat{\Sigma}B - I_p \rvert _{\infty} \leq{\lambda}$, we have $\lvert\widetilde{K}\rvert_{1,\infty}\ = \underset{1\leqslant k \leqslant p}{max}(\lvert\widetilde{K}_j\rvert_1) \leqslant \underset{1\leqslant k \leqslant p}{max}(\lvert B_j\rvert_1) =\lvert B\rvert_{1,\infty}$, it is sufficient to prove that : $\forall B \in m_{p,p}(\mathbb{R}) / \lvert \widehat{\Sigma}B - I_p \rvert _{\infty} \leq{\lambda}, \forall j \in \{1,\dots,p\}, \lvert\widetilde{K}_j\rvert_1 \leqslant \lvert B_j\rvert_1.$
By definition of $\widetilde{K}$ and of the $\widehat{\beta^{(j)}}$ as solution of optimization problem (4), we have :
$$ \forall j \in \{1,\dots,p\}, \forall \beta \in \mathbb{R}^p / \lvert\widehat{\Sigma}\beta - e_j\rvert_{\infty} \leqslant \lambda,\; \lvert\widetilde{K}_j\rvert_1 = \lvert\widehat{\beta^{(j)}}\rvert_1 \leqslant \lvert \beta \rvert_1. $$
But for all $B \in m_{p,p}(\mathbb{R})$ and for all $j \in \{1,\dots,p\}$, it comes :
(6)and if moreover $\lvert \widehat{\Sigma}B - I_p \rvert _{\infty} \leq{\lambda}$ then for all $j \in \{1,\dots,p\},\;\lvert \widehat{\Sigma}B_j - e_j \rvert _{\infty} \leqslant \lambda$ hence $\lvert\widetilde{K}_j\rvert_1 \leqslant \lvert B_j\rvert_1.$
So we finally get that : $\forall B \in m_{p,p}(\mathbb{R}) / \lvert \widehat{\Sigma}B - I_p \rvert _{\infty} \leq{\lambda}, \forall j \in \{1,\dots,p\}, \lvert\widetilde{K}_j\rvert_1 \leqslant \lvert B_j\rvert_1.$
The proof is then complete and we have :$$ \boxed{ \begin{equation} \widetilde{K} \in \underset{B \in m_{p,p}(\mathbb{R}) / \lvert \widehat{\Sigma}B - I_p \rvert _{\infty} \leq{\lambda}}{argmin}(\lvert B \rvert _{1,\infty}). \end{equation} } $$
The so defined $\widetilde{K}$ solution to optimization problem (1) is very interesting in terms of computational costs for its computation simply amounts to compute $p$ Dantzig selectors.
In the following, $\widehat{K}$ refers to the solution $\widetilde{K}$ to optimization problem (1) defined above.
A)Deterministic bound on $\lvert \widehat{K} - K \rvert _{\infty}$
Our aim in this part is to upperbound $\lvert \widehat{K} - K \rvert _{\infty}$ deterministically.
In this part, we consider $\lambda \in \mathbb{R^{*+}}$ fulfilling the upper bound condition :
(7)1.
- Let us prove that we have $\lvert \widehat{\Sigma}K - I_p \rvert _{\infty} \leq{\lambda}$.
As $\Sigma$ is nonsingular with $\Sigma^{-1} = K$, we have : $\widehat{\Sigma}K - I_p = (\widehat{\Sigma} - K^{-1}) K = (\widehat{\Sigma} - \Sigma) K$.
$K$ being symmetric as inverse of the empirical covariance matrix, the second inequality shown above linking $\lvert \; \rvert _{\infty}$ and $\lvert \; \rvert _{1,\infty}$ for a product of 2 matrices gives $\lvert (\widehat{\Sigma} - \Sigma) K \rvert _{\infty} \leqslant \lvert (\widehat{\Sigma} - \Sigma) \rvert _{\infty} \lvert K \rvert _{1,\infty}$.
Combining those with the assumption (Eq.(7)), it finally comes : $$ \boxed{ \begin{equation} \lvert \widehat{\Sigma}K - I_p \rvert _{\infty} \leqslant \lambda \end{equation} } $$
- Let us deduce that $\forall j \in \{1,\dots,p\}, \lvert \widehat{K}_j \rvert_1 \leqslant \lvert K_j \rvert_1$.
We have shown in question 2. that :
$$ \forall B \in m_{p,p}(\mathbb{R}) / \lvert \widehat{\Sigma}B - I_p \rvert _{\infty} \leq{\lambda}, \forall j \in \{1,\dots,p\}, \lvert\widehat{K}_j\rvert_1 \leqslant \lvert B_j\rvert_1. $$
$K \in m_{p,p}(\mathbb{R})$ being up to latest result such that $\lvert \widehat{\Sigma}K - I_p \rvert _{\infty} \leq{\lambda}$, this implies that : $$ \boxed{ \begin{equation} \forall j \in \{1,\dots,p\}, \lvert\widehat{K}_j\rvert_1 \leqslant \lvert K_j\rvert_1. \end{equation} } $$
2.
- Let us prove that the following inequality holds : $\lvert \widehat{K} - K\rvert _{\infty} \leqslant \lvert\widehat{K}\rvert_{1,\infty} (\lvert\widehat{\Sigma}\widehat{K}-I_p\rvert_{\infty}+\lvert(\Sigma-\widehat{\Sigma})\widehat{K}\rvert_{\infty})$
Adding and subtracting the quantity $K\widehat{\Sigma}\widehat{K}$ from $\widehat{K}-K$ and remembering that $K = \Sigma^{-1}$ so that $K \Sigma \widehat{K} = I_p \widehat{K} = \widehat{K}$, we first get :
(8)$\lvert \; \rvert _{\infty}$ being by definition nothing but a norm on the $p^2$-dimensional real vector space $m_{p,p}(\mathbb{R})$, the subadditivity of $\lvert \; \rvert _{\infty}$ applied to latest equation (8) ensures that :
(9)Since $K$ is symmetric as inverse of the empirical covariance matrix (which is symmetric by definition), the second inequality shown above linking $\lvert \; \rvert _{\infty}$ and $\lvert \; \rvert _{1,\infty}$ for a product of two matrices applied to the two last terms of inequality (9) yields :
$\lvert K (\widehat{\Sigma}\widehat{K} - I_p) \rvert _{\infty} \leqslant \lvert K \rvert _{1,\infty} \lvert (\widehat{\Sigma}\widehat{K} - I_p) \rvert _{\infty}$ and $\lvert K (\Sigma-\widehat{\Sigma})\widehat{K} \rvert _{\infty} \leqslant \lvert K \rvert _{1,\infty} \lvert (\Sigma-\widehat{\Sigma})\widehat{K} \rvert _{\infty}$
Factoring $\lvert K \rvert _{1,\infty}$ out, we then conclude :
$$ \boxed{ \begin{equation} \lvert \widehat{K} - K\rvert _{\infty} \leqslant \lvert K \rvert _{1,\infty} (\lvert\widehat{\Sigma}\widehat{K}-I_p\rvert_{\infty}+\lvert(\Sigma-\widehat{\Sigma})\widehat{K}\rvert_{\infty}). \end{equation} } $$
- Let us then deduce that the following inequality holds : $\lvert \widehat{K} - K \rvert _{\infty} \leqslant \lvert K \rvert_{1,\infty} (\lambda+\lvert K \rvert _{1,\infty}\lvert\widehat{\Sigma}-\Sigma\rvert_{\infty})$
With question A.1 ensuring that $\forall j \in \{1,\dots,p\}, \lvert \widehat{K}_j \rvert_1 \leqslant \lvert K_j \rvert_1$ and remembering that for any matrix $A$, $\lvert A \rvert _{1,\infty} = max(\lvert A_1 \rvert_{1},\dots,\lvert A_p \rvert_{1})$, we get : $\lvert\widehat{K}\rvert_{1,\infty} \leqslant \lvert K \rvert_{1,\infty}.$
And so, concentrating on the second factor of latest result, using that $\widehat{K}$ is solution to the optimization problem (1) on the one hand and applying the first inequality shown above linking $\lvert \; \rvert _{\infty}$ and $\lvert \; \rvert _{1,\infty}$ for a product of two matrices to $(\Sigma-\widehat{\Sigma})\widehat{K}$ on the other, it comes :
$\lvert\widehat{\Sigma}\widehat{K}-I_p\rvert_{\infty}+\lvert(\Sigma-\widehat{\Sigma})\widehat{K}\rvert_{\infty} \leqslant \lambda + \lvert\Sigma-\widehat{\Sigma}\rvert_{\infty} \lvert\widehat{K}\rvert_{1,\infty} \leqslant \lambda + \lvert K\rvert_{1,\infty} \lvert\widehat{\Sigma}-\Sigma\rvert_{\infty}$
Finally, combining this bound with the first one of this question, we get : $$ \boxed{ \begin{equation} \lvert \widehat{K} - K\rvert _{\infty} \leqslant \lvert K \rvert _{1,\infty} ( \lambda + \lvert K\rvert_{1,\infty} \lvert\widehat{\Sigma}-\Sigma\rvert_{\infty}). \end{equation} } $$
3.
Let us finally conclude that we have $\lvert \widehat{K} - K \rvert _{\infty} \leq 2\lambda\lvert K \rvert_{1,\infty}$
Thanks to the upper bound on $\lvert K\rvert_{1,\infty} \lvert\widehat{\Sigma}-\Sigma\rvert_{\infty}$ assumed in (7) and the upper bound on $\lvert \widehat{K} - K\rvert _{\infty}$ provided by the result of question A.2., we conclude that : $$ \boxed{ \begin{equation} \lvert \widehat{K} - K\rvert _{\infty} \leqslant 2\lambda \lvert K\rvert _{1,\infty}. \end{equation} } $$
B) Probabilistic bound on $|\widehat{\Sigma} - \Sigma|_{\infty}$
The objective of this part is to check whether $|\widehat{\Sigma} - \Sigma|_{\infty}$ is well-controled or not.
We assume henceforth that $\forall a \in \{1,\dots,p\}, \Sigma_{aa} = 1$.
Since $\Sigma$ is nonsigular, we have $\forall (a,b) \in \{1,\dots,p\}^2/ a \neq b, \left\lvert\Sigma_{ab}\right\rvert < 1$.
1.
Let $X$ be a $\mathcal N (0,\Sigma)$ Gaussian random variable.
We set $Z_1 = (2(1+\Sigma_{12}))^{-\frac{1}{2}}(X_1+X_2)$ and $Z_2 = (2(1-\Sigma_{12}))^{-\frac{1}{2}}(X_1-X_2)$.
- First, let us prove that $Z_1$ and $Z_2$ are i.i.d. with $\mathcal N(0,1)$ Gaussian distribution.
By definition of $Z_1$ and $Z_2$, writting $Z=(Z_1,Z_2) \in \mathbb{R}^2$, $Z$ is an affine transformation of the Gaussian random variable $X$, that's to say:
(10)Stability of Gaussian distribution under affine transformation ensures that $Z$ is also a Gaussian random variable and has distribution $\mathcal N(A m,A \Sigma A^T)$.
Since basic matrix calculations yields $A \Sigma A^T = I_2$ and $A m =0$, we find that $Z$ has $\mathcal N(0,I_2)$ which amounts to say that :
$$ \boxed{ \begin{equation} Z_1 \text{ and } Z_2 \text{ are i.i.d. with } \mathcal N(0,1) \text{ Gaussian distribution}. \end{equation} } $$
- Second, let us see that $X_1 X_2 = \frac{1}{4} ( 2(1+\Sigma_{12})Z_1^2 - 2(1-\Sigma_{12})Z_2^2 )$.
It is straightforward that :
(11)So that, we finally get :
$$ \boxed{ \begin{equation} X_1 X_2 = \frac{1}{4} ( 2(1+\Sigma_{12})Z_1^2 - 2(1-\Sigma_{12})Z_2^2 ). \end{equation} } $$
2.
First of all, let us demonstrate that
$$ \forall \space 0 \leq x \leq \frac{1}{2}, -\log(1-x) \leq x + x^{2} \text{ (1) } $$
and that $$ \forall \space 0 \leq x \leq \frac{1}{2}, -\log(1+x) \leq -x + \frac{x^{2}}{2} \text{ (2) } $$
Consider the differentiable function $f(x) = x + x^{2} + log(1-x)$ on the interval $I =[0, \frac{1}{2} ]$, we have $\forall x \in I, f'(x) = \frac{x-2x^{2}}{1-x} \geq 0$. Therefore f is an increasing function on I and f(0) = 0 implying that (1) is demonstrated.
The demonstration of (2) can be done with the same fashion. Let g, a differentiable function, be defined by g(x) = $\log(1+x) - x + \frac{x^{2}}{2}$ on the interval I.
g'(x) = $\frac{x^{2}}{1+x}$. Hence, g is an increasing function and g(0)=0. Q.E.D.
Next, our aim is to compute $\mathbb{E} [e^{ s X_{1}X_{2} } ]$ $\forall 0 \leq s \leq \frac{1}{4}$.
According to the question B.2, $\mathbb{E}[e^{s X_{1}X_{2}}] =\mathbb{E}[e^{\frac{s}{4}(2(1+\Sigma_{12})Z_{1}^{2} - 2 (1-\Sigma_{12})Z_{2}^{2})}] =\mathbb{E}[e^{\frac{s}{2}(1+\Sigma_{12})Z_{1}^{2}}]\mathbb{E}[e^{-\frac{s}{2}(1-\Sigma_{12})Z_{2}^{2}}]$ as $Z_{1}$ and $Z_{2}$ are independent.
Moreover, these two variables follow a standard Gaussian distribution.
Consequently, $\mathbb{E}[e^{\frac{s}{2}(1+\Sigma_{12})Z_{1}^{2}}] = \int_{\mathbb{R}} e^{\frac{s}{2}(1+\Sigma_{12})z^{2}} \frac{e^{-z^{2}/2}}{\sqrt{2\pi}}dz = \int_{\mathbb{R}} \frac{1}{\sqrt{2\pi}} e^{-\frac{z^{2}}{2(1-(1+\Sigma_{12})s)^{-1}}}dz = (1-(1+\Sigma_{12})s)^{-1/2}$ since we recognize a nearly normal $\mathcal{N}(0,(1-(1+\Sigma_{12})s)^{-1})$ distribution.
Similarly, it can be shown that $\mathbb{E}[e^{\frac{-s}{2}(1-\Sigma_{12})Z_{2}^{2}}] = (1+(1-\Sigma_{12})s)^{-1/2}$.
We deduce that $\mathbb{E}[e^{sX_{1}X_{2}}] = (1+(1-\Sigma_{12})s)^{-1/2}(1-(1+\Sigma_{12})s)^{-1/2}$.
Now, combining (1) and (2) respectively, for $x_{1} =(1+\Sigma_{12})s$ and $x_{2} =(1-\Sigma_{12})s$, we get :
$$ - \frac{1}{2}log(1-(1+\Sigma_{12})s) -\frac{1}{2}log(1+(1-\Sigma_{12})s) \leq \Sigma_{12}s +\frac{1}{2}[(1+\Sigma_{12})s]^{2} +\frac{1}{4}[(1-\Sigma_{12})s]^{2} $$
Thus, $$ (1+(1-\Sigma_{12})s)^{-1/2}(1-(1+\Sigma_{12})s)^{-1/2}\leq e^{\Sigma_{12}s + \frac{s^{2}}{4}(3 +2\Sigma_{12}+ 3\Sigma_{12}^{2}) } $$
As $|\Sigma_{12}| < 1$, $$ (1+(1-\Sigma_{12})s)^{-1/2}(1-(1+\Sigma_{12})s)^{-1/2}\leq e^{\Sigma_{12}s + 2s^{2} } $$
We have nearly finished the demonstration but we still need to verified the inequality in the case $|\Sigma_{12}| = 1$ (as $\Sigma_{aa} = 1$, this result would be useful to continue).
- $\Sigma_{12} = 1 \Rightarrow X_{1}X_{2} = Z^{2} \Rightarrow \mathbb{E} [e^{ s X_{1}X_{2} } ] = \mathbb{E}[e^{ s Z^{2}} ] = (1-2s)^{-1/2} (*)$
- $\Sigma_{12} = -1 \Rightarrow X_{1}X_{2} = -Z^{2} \Rightarrow \mathbb{E} [e^{ s X_{1}X_{2} } ] = \mathbb{E}[e^{ -s Z^{2}} ] = (1+2s)^{-1/2}$.
(*) as it is the moment-generating function of a $\chi^{2}(1)$.
Applying (1) for the first case and (2) for the second, we obtaine :
- $\mathbb{E} [e^{ s X_{1}X_{2} } ] \leq e^{s + 2s^{2} }$
- $\mathbb{E} [e^{ s X_{1}X_{2} } ] \leq e^{-s + 2s^{2}}$
In conclusion,
$$ \boxed{\mathbb{E} [e^{ s X_{1}X_{2} } ]=(1+(1-\Sigma_{12})s)^{-1/2}(1-(1+\Sigma_{12})s)^{-1/2}\leq e^{\Sigma_{12}s + 2s^{2} } }$$
3.
Let $a,b \in${1,…,p}, $0 \leq s \leq$ $\frac{1}{4}$ and t > 0.
$$ \mathbb{P} [ \widehat{ \Sigma}_{ab}-\Sigma_{ab} > t ] = \mathbb{P}[\frac{1}{n}X_{a}^{T}X_{b} - \Sigma_{ab} > t] = \mathbb{P}[X_{a}^{T}X_{b} > n\Sigma_{ab} + nt] = \mathbb{P}[e^{sX_{a}^{T}X_{b}} \geq e^{s(n\Sigma_{ab} + nt)}] $$ as exponential is a strictly increasing function.
Hence, $e^{sX_{a}^{T}X_{b}}$ is a positive random variable and the Markov inequality gives us :
$$ \begin{array}{ll} \mathbb{P}[e^{sX_{a}^{T}X_{b}} \geq e^{s(n\Sigma_{ab} + nt)}] \leq \mathbb{E}[e^{sX_{a}^{T}X_{b}}] e^{-s(n\Sigma_{ab} + nt)} & = \mathbb{E}[e^{s \sum_{i = 1}^{n} X_{a}^{(i)}X_{b}^{(i)} }] e^{-s(n\Sigma_{ab} + nt)} \\ & = \Pi^{i = 1}_{n} \mathbb{E}[e^{s X_{a}^{(i)}X_{b}^(i)} ] e^{-s(n\Sigma_{ab} + nt)} \end{array}$$ thanks to the fact that $(X_{a}^{(i)}X_{b}^{(i)})$ are independent $\forall i$.
Applying the question B.2,
$\mathbb{P}[e^{sX_{a}^{T}X_{b}} \leq e^{s(n\Sigma_{ab} + nt)}] \leq e^{-snt -sn \Sigma_{ab}} \Pi^{i = 1}_{n} e^{\Sigma_{ab}s + 2s^{2}} = e^{-snt + 2ns^{2}}$ since $|\Sigma_{ab}| \leq 1$
To conclude,
$$ \boxed{ \begin{array}{c}\forall a,b \in \{1,...,p\}; 0 \leq s \leq 1/4, t > 0; \\ \mathbb{P}[e^{sX_{a}^{T}X_{b}} \leq e^{s(n\Sigma_{ab} + nt)}] \leq e^{-snt + 2ns^{2}} \end{array}} $$
4.
Let $0 < t \leq 1$
By definition, $|\widehat {\Sigma} - \Sigma |_{\infty} = \underset{a,b}{\text{ max }}|\widehat {\Sigma}_{ab} - \Sigma_{ab} |$.
Hence, $$ \begin{array}{ll} \mathbb{P}[|\widehat {\Sigma} - \Sigma |_{\infty} > t] & = \mathbb{P}[\exists (a,b) \in \mathbb{R}^{p^{2}} : |\widehat {\Sigma}_{ab} - \Sigma_{ab} | > t] \\ & = \mathbb{P}[\exists (a,b) \in \mathbb{R}^{p^{2}} : \{\widehat {\Sigma}_{ab} - \Sigma_{ab} > t \}\cup \{\widehat {\Sigma}_{ab} - \Sigma_{ab} < -t\}] \\ & =\mathbb{P}[\cup_{a,b} \{\widehat {\Sigma}_{ab} - \Sigma_{ab} > t \}] + \mathbb{P}[\cup_{a,b} \{\Sigma_{ab} - \widehat {\Sigma}_{ab} > t \}] \\ & =\sum_{a,b \in J_{1} }\mathbb{P}[\widehat {\Sigma}_{ab} - \Sigma_{ab} > t ] + \sum_{a,b \in J_{2} }\mathbb{P}[ \Sigma_{ab} -\widehat {\Sigma}_{ab} > t ] \end{array} $$
where $J_{1} , J_{2} \subset \{1,\ldots,p\} \times \{1,\ldots,p\}$.
Note that it is not only $\widehat {\Sigma}$ that is symetric (by definition) but also $\Sigma$ as it is the covariance matrix. The system of coordinates (a,b) and (b,a) are thus the same for $\widehat {\Sigma} - \Sigma$ or $\Sigma - \widehat {\Sigma}$. We only need to consider "half" of the matrix ( i.e. the diagonal elements and the upper elements of the matrix ) and therefore, $|J_{1}| = \frac{p^{2} - p}{2} + p = \frac{p^(p+1)}{2} = |J_{2}|$.
Consequently,
$$ \begin{array}{ll} \mathbb{P}[|\widehat {\Sigma} - \Sigma |_{\infty} > t] & \leq \underbrace{ |J_{1}| \underset{a,b}{\text{ max }} \mathbb{P}[\widehat {\Sigma}_{ab} - \Sigma_{ab} > t ]}_{\text{(*)}} + \underbrace{|J_{2}| \underset{a,b}{\text{ max }}\mathbb{P}[ \Sigma_{ab} -\widehat {\Sigma}_{ab} > t ]}_{(**)} \end{array}$$
By B.3, for s = t/4 such that 0 < t $\leq$ 1, $\text{(*)} \leq |J_{1}|e^{-nt^{2}/8}$.
The main difficulty is setting an upper bound for (**). Note that
$$ \forall a,b \in \text{ {1,...,p} } \Sigma_{ab} -\widehat {\Sigma}_{ab} = -\widehat {\Sigma}_{ab} + \Sigma_{ab} = \frac{1}{n}(-X_{a}^{T})X_{b} - (-\Sigma_{ab}) $$
At this stage, we must distinguished two cases : the diagonal elements (a=b) and the upper elements (a < b).
Concerning the upper elements, let $\tilde{X_{a}} = -X_{a}^{T}$, then $\tilde{X_{a}} \sim X_{a}^{T}$. We will used the same method used in B.1 and B.2 for a more general case (for a instead of 1 and b instead of 2). Note that for $\tilde{Z}_{a} = \sqrt{2(1-\Sigma_{ab})}(-X_{a} + X_{b})$ and $\tilde{Z}_{b} = \sqrt{2(1+\Sigma_{ab})}(-X_{a} - X_{b})$, we still have $\tilde{Z}_{a}, \tilde{Z}_{b} \sim \mathcal{N}(0,1)$.
NB : We only need to see that $\tilde{Z}_{a} = Z_{b}$ where $Z_{b} \sim \mathcal{N}(0,1)$ and this can be proved easily using the method as B.1. . Similarly, $\tilde{Z}_{b} = -Z_{a}$ where $Z_{a}$ is a gaussian centered-reduced random variable.
Hence, $\mathbb{P}[ \Sigma_{ab} -\widehat {\Sigma}_{ab} > t ] \leq e^{-nt^{2}/8}$
On the other hand, for the diagonal elements a $\in$ {1,…,p}; $\Sigma_{aa} -\widehat {\Sigma}_{aa} = -\widehat {\Sigma}_{aa} + \Sigma_{aa} = \frac{1}{n}(-X_{a}^{T})X_{a} - (-1)$. Similarly to B.1. in the case of $\Sigma_{12} = -1$, we conclude that $\mathbb{E}[ e^{-X_{a}X_{a}}] \leq exp(-s + 2s^{2})$.
Hence, for s = t/4, $$ \mathbb{P}[ \Sigma_{aa} -\widehat {\Sigma}_{aa} > t ] \leq e^{-nt^{2}/8}$$
Finally,
$$ \begin{array}{ll} \mathbb{P}[|\widehat {\Sigma} - \Sigma |_{\infty} > t] & \leq 2\frac{p(p+1)}{2} e^{-nt^{2}/8} \end{array}$$
In conclusion,
$$ \boxed{ \begin{array}{c} \forall t \in ] 0, 1] \\ \mathbb{P}[|\widehat {\Sigma} - \Sigma |_{\infty} > t] \leq p(p+1) e^{-nt^{2}/8} \end{array} } $$
5.
Suppose that $log(p) \leq n/32$.
Then,$$ P[ |\tilde{\Sigma} - \Sigma|_{\infty} > 4 \sqrt{\frac{2log(p)}{n}}] \leq p(p+1) e^{- 2n \frac{2log(p)}{n}} = \frac{p(p+1)}{p^{4}} $$
Note that $\frac{p(p+1)}{p^{4}} \leq \frac{2}{p^{2}} \Leftrightarrow p^{2}-p \geq 0$ is verified when $p \geq 1$.
Hence, we deduced a probabilistic bound for $|\tilde{\Sigma} - \Sigma|_{\infty}$
$$ \boxed{ \text{For } log(p) \leq \text{n/32 : } P[ |\tilde{\Sigma} - \Sigma|_{\infty} > 4 \sqrt{\frac{2log(p)}{n}}] \leq \frac{2}{p^{2}} } $$
NB : Note that such a condition on the number of parameters p and the number of observations n authorises n to be smaller than p, which is one of the aim of the Gaussian Graphical Model.
C) Bounds in sup norm and Frobenius norm
The aim of this part is to get a probabilistic bound for $\widehat{K}-K$ concidering the sup norm or the Frobenius norm.
1.
According to part A, $\lambda \geq |K|_{1,\infty}|\widehat{\Sigma}-\Sigma|_{\infty} \Rightarrow |\widehat{K}-K|_{\infty} \leq 2 \lambda |K|_{1,\infty}$.
And, according to part B, $\mathbb{P}[|\widehat{\Sigma}-\Sigma|_{\infty} \leq 4 \sqrt{\frac{2log(p)}{n}}] \geq 1 - \frac{2}{p^{2}}$
$$ \boxed{ \text{Lemma : If } A \Rightarrow B \text{ and } \mathbb{P}[A] \geq t \text{ then,} \mathbb{P}[B] \geq t } $$
Proof : This lemma can be proved using sets. A$\Rightarrow$B means that {A} is included in {B}. Hence, $\mathbb{P}[A] \leq \mathbb{P}[B]$. Note that in most of cases, more conditions are required to go from B to A.
Let $\lambda = 4|K|_{1,\infty} \sqrt{\frac{2log(p)}{n}}$ and applying the lemma, we have :
$$ \boxed{ \mathbb{P}[ |\widehat{K}-K|_{\infty} \leq 8 |K|_{1,\infty}^{2} \sqrt{\frac{2log(p)}{n}} ] \geq 1 - \frac{2}{p^{2}} } $$
2.
Let $\lambda \geq |K|_{1,\infty}|\widehat{K}-K|_{\infty}$.
Let $J = \{(i,j) : |\widehat{K_{ij}}| > |\widehat{K}-K|_{\infty} \}$ and $j \in \{1,...,p\}$.
As $J^{c} \cap J = \emptyset$, $\forall A \in \mathbb{R}^{p}, |A|_{1} = |A^{J^{c}}|_{1} + |A^{J}|_{1}$. In particular, for $A = \widehat{K}_{j}$, $$ |\widehat{K}_{j}^{J^{c}}|_{1} = |\widehat{K}_{j}|_{1} - |\widehat{K}^{J}_{j}|_{1} \leq |K_{j}|_{1} - |\widehat{K}^{J}_{j}|_{1}\leq |K_{j} - \widehat{K}^{J}_{j}|_{1} $$
due to question A.1.
By the definition of the $|.|_{1,\infty}$,
$$ |\widehat{K}^{J^{c}}|_{1,\infty} = \underset{j}{\operatorname{max}} |\widehat{K}^{J^{c}}_{j}|_{1}\leq \underset{j}{\operatorname{max}} |K_{j} - \widehat{K}^{J}_{j}|_{1} = |K - \widehat{K}^{J}|_{1,\infty}$$
3.
In the first instance, assure ourself that $(i,j) \in J, K_{ij} \neq 0$ ad absurdum. Let $(i,j) \in J$ such that $K_{ij} = 0$. Since $(i,j) \in J, |\widehat{K_{ij}}| > |\widehat{K} - K|_{\infty} = \underset{m,n}{\operatorname{max}} |\widehat{K_{mn}} - K_{mn}| \geq |\widehat{K_{ij}}|$.
Hence, the contradiction $|\widehat{K_{ij}}| < |\widehat{K_{ij}}|$ leads to conclude that $K_{ij} \neq 0$. Note that being in a Gaussian Graphical Model, the subset J represents a part of the nodes linked in the minimal graph g* which is encoded in the precision matrix K (Lemma 7.2).
Next, let us take a closer look at an upper bound of $|\widehat{K}-K|_{1,\infty}$.
$$ |\widehat{K}-K|_{1,\infty} = |\widehat{K^{J}}+\widehat{K^{J^{c}}}-K|_{1,\infty} \leq |\widehat{K^{J}}-K|_{1,\infty} + \underbrace{ |\widehat{K^{J^{c}}}|_{1,\infty} }_{\text{according to the previous question }\leq |K - \widehat{K}^{J}|_{1,\infty}} $$
Hence, $$ |\widehat{K}-K|_{1,\infty} \leq 2 |\widehat{K^{J}}-K|_{1,\infty} $$
The next step consists of demonstrating that $$ |\widehat{K^{J}}-K|_{1,\infty} \leq d|\widehat{K^{J}}-K|_{\infty} $$
where $d = \underset{j=1,...,p}{\operatorname{max}} |K_{j}|_{0}$ corresponds to the degree of the minimal graph associated to the Gaussian distribution $\mathcal{N}(0,\Sigma)$.
Let A $\in \mathbb{R}^{p \times p}$ and $j \in \{1,...,p\}$.
Then, $|A_j|_{1} = \sum_{i \in I_{j}} |A_{ij}| \leq |I_{j}| |A|_{\infty}$ where $I_{j} = \{ i \in \{1,...,p \} : A_{ij} \neq 0 \}$
Thus,$$ \underset{j}{\operatorname{max}} |A_j|_{1} \leq \underset{j}{\operatorname{max}} |I_{j}| |A|_{\infty} = \underset{j}{\operatorname{max}} |A_{j}|_{0}|A|_{\infty} $$
We have prove that :
$$ |\widehat{K^{J}}-K|_{1,\infty} \leq d|\widehat{K^{J}}-K|_{\infty} $$
Hence, $$ 2 |\widehat{K^{J}}-K|_{1,\infty} \leq 2d |\widehat{K^{J}}-K|_{\infty} \leq 2d (|\widehat{K}-K|_{\infty} + \underbrace{|\widehat{K^{J^{c}}}|_{\infty})}_{(*)} $$
We need an upper bound of (*). From the definition of the set $J$, we have
$$|\widehat{K^{J^{c}}}|_{\infty} \leq |\widehat{K}-K|_{\infty} $$
Finally,
$$ 2 d|\widehat{K^{J}}-K|_{\infty} \leq 4d |\widehat{K}-K|_{\infty} $$
In conclusion, $$ \boxed{ |\widehat{K}-K|_{1,\infty}\leq 2|\widehat{K^{J}}-K|_{1,\infty}\leq 2 d|\widehat{K^{J}}-K|_{\infty} \leq 4d |\widehat{K}-K|_{\infty}}$$
4.
By the definition of the Frobenius norm,
$||\widehat{K}-K||^{2}_{F} = \sum_{ij}|[\widehat{K}-K]_{ij}|^{2} \leq p \sum_{i} \underset{j}{\operatorname{max}} |[\widehat{K}-K]_{ij}|^{2}\leq p \underset{i,j}{\operatorname{max}} |[\widehat{K}-K]_{ij}| \sum_{i} \underset{j}{\operatorname{max}} |[\widehat{K}-K]_{ij}|$
In conclusion, $$ \boxed{||\widehat{K}-K||^{2}_{F} \leq p|\widehat{K}-K|_{\infty} |\widehat{K}-K|_{1,\infty} \leq \underbrace{4pd|\widehat{K}-K|^{2}_{\infty}}_{\text{ using the previous question}}} $$
5.
By C.1. $$ \mathbb{P}[|\widehat{K}-K|_{\infty} \leq 8 |K|^{2}_{1,\infty}\sqrt{\frac{2log(p)}{n}}] \geq 1-\frac{2}{p^{2}} $$
By C.4. for $\lambda = |K|_{1,\infty} \sqrt{\frac{2log(p)}{n}}$,
$$ |\widehat{K}-K|_{\infty} \leq 8 |K|^{2}_{1,\infty}\sqrt{\frac{2log(p)}{n}} \Rightarrow ||\widehat{K}-K||^{2}_{F} \leq 4\times 8^{2} pd|K|^{4}_{1,\infty}\frac{2log(p)}{n} = 512pd|K|^{4}_{1,\infty}\frac{log(p)}{n}$$
Using the lemma demonstrated at C.1, we deduce that
$$ \boxed{ \begin{equation} \mathbb{P}[||\widehat{K}-K||^{2}_{F} \leq 512pd|K|^{4}_{1,\infty}\frac{log(p)}{n}] \geq 1-\frac{2}{p^{2}} \end{equation} } $$