050. Covariance estimation

Covariance estimation

Matrix algebra review

Covariance matrix estimation in the operator norm

::: {.theorem name=“Covariance estimation”}

$X_1,\cdots ,X_n\stackrel{iid}{\sim }SG(\sigma )$ s.t. $E(X_1)=0,Var(X_1)={\Sigma }_{d\times d}$.

Let sample Cov matrix $\hat{\Sigma }=\frac{1}{n}\sum X_i{X}_i^{\prime }$ based on $X_1,\cdots ,X_n$.

Then there exists a universal constant $C>0$ s.t. below holds with probabilty at least $1-\sigma$.

$$\forall \sigma \in (0,1):\frac{\Vert \hat{\Sigma }-\Sigma {\Vert }_{op}}{{\sigma }^2}\le C\max \left\{\sqrt{\frac{d+\log (\frac{2}{\sigma })}{n}},\frac{d+\log (\frac{2}{\sigma })}{n}\right\}$$

:::

• 이건 결국 ${\lim }_{n\to \infty \frac{d}{n}\to 0}$ 일 때 operator norm 안의 $\Sigma$를 계속해서 estimate 할 수 있다는 것을 말함. 실제로 추가적인 가정 없이는 이 rate 이상으로 측정을 정밀화할 수 없음.

증명을 2단계로 분할.

1. discretization argument 를 써서 문제를 finitely 많은 랜덤변수의 maximum 을 제어하는 문제로 변경. 이하의 정보와 함께 finite maximum 라는 사실 사용해서 $\Vert \hat{\Sigma }-\Sigma {\Vert }_{op}$ 에 대한 상한 생산.

let $A=A^{\prime }\in {\mathbb{R}}^{d\times d}$ 로 하고, $N_{ϵ}=\{y_1,\cdots ,y_N\}$ 을 ${\mathbb{S}}^{d-1}$ 의 $ϵ$-covering 으로 함.

이때 $\Vert A{\Vert }_{op}\le \frac{1}{1-2ϵ}\cdot {\max }_{y\in N_{ϵ}}|y^{\prime }Ay|$.

이를 증명하자. $x\in {\mathbb{S}}^{d-1}$ 에 대해 $\Vert x-y{\Vert }_2\le ϵ$ 만족하는 $y\in N_{ϵ}$ 선택. 이때 $A$는 symmetric Matrix 이므로,

여기서 $\hat{\Sigma }-\Sigma$ 는 symmetric Matrix 이므로, $\Vert \hat{\Sigma }-\Sigma {\Vert }_{op}\le \frac{1}{1-2ϵ}{\max }_{y\in N_{ϵ}}|y^{\prime }(\hat{\Sigma }-\Sigma )y|$.

\tag{5.1}

$$|x^{\text{T}}Ax-y^{\text{T}}Ay|=|x^{\text{T}}A(x-y)-y^{\text{T}}A(y-x)|\le \left|x^{\text{T}}A(x-y)\right|+\left|y^{\text{T}}A(y-x)\right|\text{\hspace{1em}(triangle ineq.)}$$ $$\begin{gathered} |x^{\text{T}}A(x-y)|\stackrel{(1)}{\le }||A(x-y)|{|}_2||x|{|}_2 \\ \stackrel{(2)}{\le }||A|{|}_{\mathrm{op}}||x-y|{|}_2 \\ \stackrel{(3)}{\le }ϵ\Vert A{\Vert }_{\mathrm{op}}\text{\hspace{1em}(Cauchy–Schwarz inequality)} \end{gathered}$$

2. $||x|{|}_2=1$, and $\forall v\in {\mathbb{R}}^d:||Av|{|}_2\le ||A|{|}_{op}||v|{|}_2$
3. $||x-y|{|}_2\le ϵ$

Applying the same argument to $|y^{T}A(y-x)|$ then gives $|x^{T}Ax-y^{T}Ay|\le 2ϵ||A|{|}_{op}$.

To complete the proof of inequality (5.1), note that

$$|x^{\text{T}}Ax|=|x^{\text{T}}Ax-y^{\text{T}}Ay+y^{\text{T}}Ay|\le \left|x^{\top }Ax-y^{\top }Ay\right|+\left|y^{\top }Ay\right|\le 2ϵ||A|{|}_{\mathrm{op}}+|y^{T}Ay|$$

This implies that $||A|{|}_{op}\le 2ϵ||A|{|}_{op}+{\max }_{y\in N_{ϵ}}|y^{T}Ay|$ and rearranging the terms yields inequality (5.1).

2. standard concentration inequality 사용.

Step 2. By choosing  = 1/4, inequality (5.2) becomes

$$||\hat{\Sigma }-\Sigma |{|}_{\mathrm{op}}\le 2\underset{y\in N_{1/4}}{\max }|y^{\top }(\hat{\Sigma }-\Sigma )y|$$

Therefore by the union bound

$$P(||\hat{\Sigma }-\Sigma |{|}_{\mathrm{op}}\ge t)\le P\left(2\underset{y\in N_{1/4}}{\max }|y^{\top }(\hat{\Sigma }-\Sigma )y|\ge t\right)\le \sum _{y\in N_{1/4}}P\left(|y^{\top }(\hat{\Sigma }-\Sigma )y|\ge \frac{t}{2}\right)$$

Note that we can write

$y^{\top }(\hat{\Sigma }-\Sigma )y=\frac{1}{n}{\sum }_{i=1}^n\left\{(y^{\top }{X}_i{)}^2-\mathbb{E}[(y^{\top }{X}_i{)}^2]\right\}$

We saw earlier in Lemma 3.3 that the square of a sub-Gaussian random variable is sub-exponential with parameters $(\nu ,\alpha )=(16{\sigma }^2,16{\sigma }^2)$. This property implies that $\left\{(y^{\top }{X}_i{)}^2-\mathbb{E}[(y^{\top }{X}_i{)}^2]\right\}$ is sub-exponential with $(16{\sigma }^2,16{\sigma }^2)$. Applying the sub-exponential tail bound, especially inequality (3.2), yields

$$\begin{gathered} \mathbb{P}(\Vert \hat{\Sigma }-\Sigma {\Vert }_{\mathrm{lop}}\ge t)\le 2\underset{\mathrm{extrianitv}}{\underbrace{\mathrm{l}{N}_{1/4}}}\times \exp (-\frac{1}{2}\min \{\frac{nt}{16{\sigma }^2},\frac{n{t}^2}{16^2{\sigma }^4}\left\}\right) \\ \le 2\times 9^d\times \exp (-\frac{1}{2}\min \{\frac{nt}{16{\sigma }^2},\frac{n{t}^2}{16^2{\sigma }^4}\left\}\right) \end{gathered}$$

where the last step uses the result in Lecture 4, which shows that the cardinality of $N_{1/4}$ is bounded by $|N_{1/4}|\le 9$. (here note that ${\mathbb{S}}^{d-1}\subset \mathbb{B}=\{\theta \in {\mathbb{R}}^d:||\theta |{|}_2\le 1\}\})$). Finally, inverting the bound gives the desired result.

Bounds for structured covariance matrices

우리의 주된 목적은 샘플 Cov를 경유하여 unstructured Cov Matrix를 estimate 하는 것. Cov Matrix 가 추가적인 structure 를 품고 있다면, 샘플 Cov 가 아니라 다른 estimator 를 사용해서 좀더 연산이 빠른 estimate 가 가능.

• Diagonal matrix

Cov Matrix 가 diagonal이라는 정보를 가지고 있다고 해보자. 이때 ${\hat{\Sigma }}_{diag}=diag\{{\hat{\Sigma }}_{11},\cdots ,{\hat{\Sigma }}_{dd}$ 로 estimate 하는 것은 자연스럽다. 이 경우 sub-Gaussinianity 를 가정한다면 어떻게 될까? unstructured 케이스에서 order 가 $\sqrt{\frac{d}{n}}$ rates (단, $d\le n$) 였던 것과 대비되게 estimation error of the order $\sqrt{\frac{\log d}{n}} 가 생산된다.

좀 더 자세히 살펴보자. diagonal 케이스에서, ${\hat{\Sigma }}_{diag}-\Sigma$ 의 operator norm 은 본질적으로 $d$ 개의 entry값 $\{|{\hat{\Sigma }}_{diag,11}-{\Sigma }_{11}|,\cdots ,|{\hat{\Sigma }}_{diag,dd}-{\Sigma }_{dd}|\}$ 중의 maximum 이다. 그렇다면 여기서 the union bound argument along with an exponential tail bound 를 통해 우리는 $\sqrt{\frac{\log d}{n}}\to 0$ 일 때 operator norm 이 0로 decay 된다는 것을 파악할 수 있다. See Theorem 2.11 for a similar argument.

• Unknown sparsity and thresholding

좀더 일반적인 케이스를 생각해보자. Cov Matrix가 상대적으로 sparse 하다는 사실이 알려져 있지만, 어느 entry가 non-zero인지는 알려져있지 않다. 이때 estimator가 thresholding 에 기반하고 있다고 생가가흔 넉승 나젼스럽다. 이때 $\lambda >0$ 라는 패러미터가 주어져 있다고 생각할 때, hard-thresholding 을 통해 얻어지는 Cov estimator 의 $(i,j)$ entry 는 $[T_{\lambda }(\hat{\Sigma }){]}_{ij}={\hat{\Sigma }}_{ij}\cdot I(|{\hat{\Sigma }}_{ij}>\lambda )$.

let $\Sigma$의 adjacency matrix $A\in {\mathbb{R}}^{d\times d}$, $A_{ij}=I({\Sigma }_{ij})\ne 0$. adjacency matrix 의 operator norm $\Vert A{\Vert }_{op}$ 는 sparsity 에 대한 natural measure 를 제공한다. 이때 우리는 $\Sigma$ 가 row 별로 $s$ 개의 non-zero entry를 갖고 있다면 $\Vert A{\Vert }_{op}\le s$ 임을 보일 수 있다. 또한 thresholded 샘플 Cov Matrix 는 다음과 같은 concentration bound를 가짐.

::: {.theorem name=“Thresholding-based covariance estimation”}

$X_1,\cdots ,X_n\stackrel{iid}{\sim }$, s.t. $E(X_1)=0,Var(X_1)={\Sigma }_{d\times d}$, and suppose each component $X_{ij}$ is sub-Gaussinian with 패러미터 at most $\sigma$.

만약 $n>16\log d$ 라면, $\forall \delta >0$에 대해, thresholded 샘플 Cov Matrix $T_{{\lambda }_n}(\hat{\Sigma })$ with $\frac{{\lambda }_n}{{\sigma }^2}=8\sqrt{\frac{\log d}{n}}+\delta$ 는 이하를 만족한다.

$$P(\Vert T_{{\lambda }_n}(\hat{\Sigma })-\Sigma {\Vert }_{op}\ge 2\Vert A{\Vert }_{op}\cdot {\lambda }_n)\le 8\exp (-\frac{n}{16}(\delta \wedge {\delta }^2))$$

:::

• 위의 부등식은 높은 확률로 $\Vert T_{{\lambda }_n}(\hat{\Sigma })-\Sigma {\Vert }_{op}\lesssim \Vert A{\Vert }_{op}\sqrt{\log d}n$ 임을 보여줌. 이에 더해서 $\sigma$ 가 row 당 최대 $s$ 개의 non-zero entry 를 가진다는 조건을 생각하자. 이는 곧 $\Vert A{\Vert }_2\le s$ 라는 의미가 됨. 그렇다면 thresholded Cov Matrix는 $s\sqrt{\frac{\log d}{n}}\to 0$ 일 때 consistent 하며, 이는 곧 특히 $s$ 가 작을 때 $\sqrt{\frac{d}{n}}$ 보다 훨씬 빠르다.

• thresholding 패러미터는 sub-Gaussian 패러미터 $\sigma$에 의존하는데, 이는 실전 상황에서는 대부분 unknown.

Proof: Let us denote the elementwise infinity norm of the error matrix $\hat{\Delta }=\hat{\Sigma }-\Sigma$ by $||\hat{\Delta }|{|}_{\infty }={\max }_{1\le j,j\le d}|{\hat{\Delta }}_{ij}|$. The proof of the theorem is based on two intermediate results:

\

1. Under the assumptions of the theorem,

\mathbb{P}(||\widehat{\Delta}||_{\infty}/\sigma^{2}\geq t)\leq8e^{-{\frac{n}{16}}\operatorname*{min}\{t,t^{2}\}+2\log d}\quad\mathrm{for~all~}t\gt 0 \tag{5.3}

2. For any choice of ${\lambda }_n$ such that $||\hat{\Delta }|{|}_{\infty }\le {\lambda }_n$ we are guaranteed that

||\widehat{\Sigma}-\Sigma||_{\mathrm{lop}}\leq\ 2||A||_{\mathrm{op}}\lambda_{n} \tag{5.4}

\

Having these results in place, the theorem follows by taking $t=\frac{{\lambda }_n}{{\sigma }^2}=8\sqrt{\frac{\log d}{n}}+\delta$in inequality (5.3) and see

$8e^{-\frac{n}{16}\min \{t,t^2\}+2\log d}<8e^{-\frac{n}{16}\min \{\delta ,{\delta }^2\}},$

, when $n>16logd$. Thus

It remains to prove inequality (5.3) and inequality (5.4), which are left as exercises (see Section 6.5 of Martin’s book)

$$|\mathbb{P}(||T_{{\lambda }_n}(\hat{\Sigma })\to \Sigma |{|}_{\mathrm{op}}\ge 2||A|{|}_{\mathrm{op}}{\lambda }_n)\le P(||\hat{\Delta }|{|}_{\infty }\ge {\lambda }_n)\le 8e^{-\frac{n}{16}min}\{\delta ,{\delta }^2{\}}_{.}$$

It remains to prove inequality (5.3) and inequality (5.4), which are left as exercises (see Section 6.5 of Martin’s book)