Technical NotebookDDangchani's DataLog

Archive

Spectral Analysis - Low-rank matrix denoising

Preliminary Matrix Bernstein Inequality Theorem Independent random matrix sequence $$\lbrace X{i}\rbrace {1\leq i\leq m}, X{i}\in\mathbb{R}^{n{1}\times n{2}}$$ 에 대해 다음을 가정하자. $$ \begin{aligned} \mathbb{P}(\Vert X{i}-\...

2023. 8. 3.3 min read

Preliminary

Matrix Bernstein Inequality

Theorem

Independent random matrix sequence {Xi}1≤i≤m,Xi∈Rn1×n2\lbrace X_{i}\rbrace _{1\leq i\leq m}, X_{i}\in\mathbb{R}^{n_{1}\times n_{2}} 에 대해 다음을 가정하자.

P(∥Xi−EXi∥≥L)≤q0∥EXi−EXiI(∥Xi∣∥<L)∥≤q1 \begin{aligned} \mathbb{P}(\Vert X_{i}-\mathbb{E}X_{i}\Vert\geq L)\leq q_{0}\\ \Vert\mathbb{E}X_{i}-\mathbb{E}X_{i}I(\Vert X_{i}\vert\Vert<L)\Vert\leq q_{1} \end{aligned}

여기서 0≤q0≤10\leq q_{0}\leq 1, q1≥0q_{1}\geq 0 이다. 또한, 행렬에 대한 분산 통계량(matrix variance statistic) vv를 다음과 같이 정의하자.

v:=max⁡{∥∑i=1mE[(Xi−EXi)(Xi−EXi)T]∥,∥∑i=1mE[(Xi−EXi)T(Xi−EXi)]∥} v:= \max\bigg\lbrace \bigg\Vert\sum_{i=1}^{m}\mathbb{E}\big[(X_{i}-\mathbb{E}X_{i})(X_{i}-\mathbb{E}X_{i})^{T}\big]\bigg\Vert, \\ \bigg\Vert\sum_{i=1}^{m}\mathbb{E}\big[(X_{i}-\mathbb{E}X_{i})^{T}(X_{i}-\mathbb{E}X_{i})\big]\bigg\Vert\bigg\rbrace

그러면 모든 t≥mq1t\geq mq_{1} 에 대해 다음과 같은 부등식이 성립한다.

P(∥∑i=1m(Xi−EXi)∥≥t)≤(n1+n2)exp⁡(−(t−mq1)2/2v+L(t−mq1)/3)+mq0 \mathbb{P}\bigg(\bigg\Vert\sum_{i=1}^{m}(X_{i}-\mathbb{E}X_{i})\bigg\Vert\geq t\bigg)\leq (n_{1}+n_{2})\exp\bigg(\frac{-(t-mq_{1})^{2}/2}{v+L(t-mq_{1})/3}\bigg)+mq_{0}

Corollary

위 정리를 실제로 사용하기 위해 몇 가지 가정을 추가하여 다음과 같이 보다 user-friendly한 형태의 부등식을 얻을 수 있다. 우선 random matrix sequence에 다음과 같은 가정을 추가하자.

EXi=0,∥Xi∥≤L,∀i \mathbb{E}X_{i}=\mathbf{0},\quad \Vert X_{i}\Vert\leq L,\quad \forall i

그러면 n=max⁡{n1,n2}n=\max\lbrace n_1,n_2\rbrace 라고 둘 때 임의의 a≥2a\geq 2 에 대해 다음이 성립한다.

P(∥∑i=1mXi∥≤2avlog⁡n+2a3Llog⁡n)>1−2n−a+1 \mathbb{P}\bigg(\bigg\Vert\sum_{i=1}^{m}X_{i}\bigg\Vert\leq\sqrt{2av\log n}+\frac{2a}{3}L\log n\bigg)>1-2n^{-a+1}

Spectral Norm inequality

Bernstein inequality를 이용하면, 랜덤행렬 X=[Xi,j]\mathbf{X}=[X_{i,j}] 에서 각 원소들이 독립일 때 다음과 같은 정리가 성립한다는 것을 도출할 수 있다.

정리. 대칭 랜덤행렬 X=[Xi,j]∈Rn×n\mathbf{X}=[X_{i,j}]\in\mathbb{R}^{n\times n}이 다음 성질을 만족한다고 하자.

EXi,j=0,∣Xi,j∣≤B \mathbb{E}X_{i,j}=0,\quad \vert X_{i,j}\vert\leq B

이때 matrix variance statistic

v:=max⁡i∑jEXi,j2 v:=\max_{i}\sum_{j}\mathbb{E}X_{i,j}^{2}

를 정의하면 spectral norm에 대해 모든 t≥0t\geq 0 에 대해 다음 부등식을 만족하는 universal constant c>0c>0 이 존재한다.

P(∥X∥≥4v+t)≤nexp⁡(−t2cB2) \mathbb{P}(\Vert X\Vert\geq 4\sqrt{v}+t)\leq n\exp\big(-\frac{t^{2}}{cB^{2}}\big)

Low-rank matrix Denoising

Perturbation theory를 사용하는 데이터사이언스 분야로 우선 Low-rank matrix denoising 을 다루어보도록 하자. Low-rank matrix denoising이란, 주어진 관측 행렬에서 노이즈를 제거한 Low-rank matrix를 추정하는 과정이라고 생각하면 된다. 이전 Perturbation Theory에서 고려한 다음과 같은 모델을 생각하자.

M=M⋆+E M=M^{\star}+E

여기서 행렬 MM이 관측치를 의미하고, EE는 노이즈에 해당하는 행렬이다. 따라서 우리가 추정해야할 대상 행렬은 M⋆M^{\star} 인데, 이를 위해서 우선 eigendecomposition M⋆=U⋆Λ⋆U⋆TM^{\star}=U^{\star}\Lambda^{\star}{U^{\star}}^{T} 를 생각하자. 또한, 고유값이 ∣λ1⋆∣≥⋯≥∣λr⋆∣>0\vert\lambda_{1}^{\star}\vert\geq\cdots\geq\vert\lambda_{r}^{\star}\vert>0 으로 주어진다고 가정하자. 일반적으로 노이즈 행렬은 다음과 같은 랜덤 행렬로 가정한다.

Ei,j∼i.i.dN(0,σ2) E_{i,j}\overset{\mathrm{i.i.d}}{\sim}N(0,\sigma^{2})

How to

관측 행렬 MM으로부터 노이즈가 제거된 행렬 M⋆M^{\star}를 추정하는 것은 어려워 보이지만, 해답은 비교적 간단하다. 만일 추정해야할 행렬 M⋆M^{\star}의 계수가 rr이라면, 단지 관측행렬 MM에서 rr개의 고유값 및 고유벡터를 취하는 것으로 해결된다. 즉, 만일 MM의 고유값들이 다음과 같이 정렬된다면

∣λ1∣≥∣λ2∣≥⋯≥∣λn∣ \vert\lambda_{1}\vert\geq\vert\lambda_{2}\vert\geq\cdots\geq \vert\lambda_{n}\vert

여기서 큰 고유값 순으로 rr개를 취한 후, 각 고유값에 대응되는 고유벡터로 공간으로 만든 행렬

[u1,u2,…,ur]∈Rn×r[u_{1},u_{2},\ldots,u_{r}]\in\mathbb{R}^{n\times r} 은 행렬 U⋆U^{\star}의 추정치가 된다.

Performance

방식은 매우 간단한 반면, 실제로 위와 같은 방법이 얼마나 효과적인지를 파악하기 위해서는 이전 글에서 다룬 David-Kahan sin⁡Θ\sin\Theta 정리를 이용하면 된다. David-Kahan theorem으로 부터 다음과 같은 부등식을 얻을 수 있는데, 이는 추정해야할 부분공간 U⋆U^\star 와 추정치로 제시된 부분공간 UU 의 거리가 매우 높은 확률로 가깝게 도출될 수 있음을 의미한다.

P(dist(U,U⋆)≤2∥E∥∣λr⋆∣)>1−O(n−8) \mathbb{P}\bigg(\mathrm{dist}(U,U^{\star})\leq \frac{2\Vert E\Vert}{\vert\lambda_{r}^{\star}\vert}\bigg)>1-O(n^{-8})

또한, 이 과정에서 노이즈 행렬에 대해 σn≤1−1/25∣λr⋆∣\sigma\sqrt{n}\leq\frac{1-1/\sqrt{2}}{5}\vert\lambda_{r}^{\star}\vert 을 가정하면 Weyl 부등식으로부터 다음이 확률 1−O(n−8)1-O(n^{-8}) 로 성립한다.

∣λi∣≤∥E∥≤5σn∀i≥r+1 \vert\lambda_{i}\vert\leq \Vert E\Vert\leq 5\sigma\sqrt{n}\quad \forall i\geq r+1

Euclidean Accuracy

앞선 추정방법을 종합하여, 알려지지 않은 행렬 M⋆M^{\star} 를 추정치 M^=UΛUT\hat M=U\Lambda U^{T} 로 추정하는 과정에서의 정확성을 살펴보면 다음과 같다. 우선 삼각부등식을 이용하면 다음 부등식을 얻을 수 있는데,

∥UΛUT−M⋆∥≤∥M−M⋆∥+∥UΛUT−M∥=∥E∥+∣λr+1∣≤2∥E∥ \begin{aligned} \Vert U\Lambda U^{T}-M^{\star}\Vert&\leq \Vert M-M^{\star}\Vert+\Vert U\Lambda U^{T}-M \Vert\\ &= \Vert E\Vert +\vert\lambda_{r+1}\vert\\ &\leq 2\Vert E\Vert \end{aligned}

행렬 UΛUT−M⋆U\Lambda U^{T -}M^{\star} 의 계수가 최대 2r2r 이므로, 다음이 성립한다.

P(∥UΛUT−M⋆∥F≤10σ2nr)>1−O(n−8) \mathbb{P}\bigg(\bigg\Vert U\Lambda U^{T}-M^{\star}\bigg\Vert_{F}\leq 10\sigma\sqrt{2nr}\bigg)> 1-O(n^{-8})

References

  • Yuxin Chen et al. - Spectral Methods for Data Science: A Statistical Perspective (2021)