Basics of matrix analysis

Perturbation

실행렬 $M^{\star}$와 교란(perturbed)된 실행렬 $M$ 에 대해 다음 관계를 가정하자.

여기서 $E$는 perturbation matrix 라고 하며, 통계학적인 관점에서 $M, M^{\star}$ 이 각각 관측치와 기댓값이라면 $E$를 오차 정도로 볼 수 있다(아래).

이때 우리의 관심사는 관측치 $M$을 바탕으로 기댓값 행렬 (일반적으로 low-rank인) $M^{\star}$을 추정하는 것이며, 이 과정에서 고유값공간(혹은 특이값공간)의 성질을 이용하는데 이러한 접근 방식을 Spectral Analysis라고 한다.

Unitarily invariant matrix norm

Definition

$\mathbb{R}^{m\times n}$ 에서 정의되는 행렬 노음 $\Vert\cdot\Vert$ 가 unitarily invariant 하다는 것은 임의의 두 정규직교행렬 $U\in \mathcal{O}^{m\times m},V\in\mathcal{O}^{n\times n}$ 에 대해 다음이 성립하는 것을 의미한다.

Lemma. Weyl's inequality

$A,E\in\mathbb{R}^{n\times n}$ 이 대칭 실행렬이고, $\lambda_{i}(A)$ 를 행렬 $A$의 $i$번째로 큰 고유값이라고 하자. 그러면 다음 부등식이 성립한다.

이때 우변의 노음 $\Vert\cdot\Vert$ 은 spectral norm으로, 행렬의 가장 큰 특이값(singular value) $\max_{i}\sigma_{i}(E)$를 의미한다. 대칭실행렬 외에 일반적인 행렬 $A,E\in\mathbb{R}^{m\times n}$ 에 대해서도 고유값 대신 특이값을 이용한 다음의 부등식이 성립한다.

Distance between subspaces

$\mathbb{R}^n$ 에서의 두 r-dimensional 부분공간 $\mathcal{U}^{\star},\mathcal{U}$ 를 생각하자. 각 부분공간의 정규직교기저(orthonormal basis)를 각각 $U^{\star},U\in\mathbb{R}^{n\times r}$ 라고 하고, $n\times n$ 정규직교행렬을 만들기 위해 각 기저에 대한 직교행렬 $U_{\perp}^{\star},U_{\perp}$ 를 구성하자. 그러면 행렬 $[U^{\star},U^{\star}_{\perp}], [U,U_{\perp}]$ 는 각각 $n\times n$ 정규직교행렬이 된다.

두 부분공간 $\mathcal{U^{\star},U}$ 의 거리를 측정하기 위해서는 새로운 metric을 정의해야하는데, 기존에 사용하는 spectral norm 혹은 Frobenius norm은 회전변환을 고려하지 못하기 때문이다. 즉, 회전변환 $R\in\mathcal{O}^{r\times r}$ 에 대해 $UR$은 $U$와 같은 basis를 가지지만, $\Vert UR-U\Vert\neq 0$ 이 되어 두 공간의 기저가 같음에도 거리가 0이 아닌 문제가 발생한다. 일반적으로 이 문제를 해결하기 위해, 다음과 같이 회전변환에 영향을 받지 않는 $UU^{T}$를 이용한다.

이를 이용해 다음과 같이 두 부분공간 $\mathcal{U^{\star},U}$ 의 거리를 다음과 같이 정의한다.

여기서 matrix norm $\Vert\cdot\Vert$ 는 주로 spectral norm 혹은 Frobenius norm을 사용한다.

Angle between subspaces

$U^T U^{\star}$ 의 특이값들이 $\sigma_{1}\geq\sigma_{2}\geq\cdots\geq\sigma_{r}\geq 0$ 으로 주어진다고 하자. $U,U^{\star}$ 의 노음이 1이므로, 모든 특이값들은 0과 1사이의 값을 갖는다. 이점에서 아이디어를 얻어, 각 특이값들을 어떤 각도의 코사인 값으로 볼 수 있는데, 이를 이용해 두 부분공간의 각도를 다음과 같이 정의하고, 이를 principal angles 라고 한다.

또한, 각도들로 이루어진 행렬을 다음과 같이 정의한다면

$U^{T}U^{\star}$ 의 특이값분해(SVD)를 다음과 같이 쓸 수 있다.

Relationship between Angle and Distance

대각행렬 $\sin\Theta=\mathrm{diag}(\sin\theta_{i})$ 를 $cos\Theta$ 와 마찬가지로 정의하면, Spectral norm $\Vert\cdot\Vert$과 Frobenius norm $\Vert\cdot\Vert_F$ 에 대해 다음 관계식이 성립한다.

따라서, 두 부분공간의 거리를 측정하기 위해서는 위 동치인 것들 중 하나를 선택해서 사용하면 된다.

Perturbation Theory

Setup

$\mathbb{R}^{n\times n}$ 에서의 두 대칭실행렬 $M=M^{\star}+E$ 에 대해 다음과 같은 고유값분해(eigendecomposition)을 고려하자.

Davis-Kahan's Theorem

Davis-Kahan의 $\sin\Theta$ 정리는 대칭실행렬의 eigenspace에 대한 성질을 다루는 정리이다. 우선 Eigengap $\Delta>0$ 와 위 setup의 고유값행렬에 대해 다음 성질이 성립한다고 하자.

이 경우 다음과 같은 부등식이 성립한다.

추후에 다루겠지만, $E$가 sparse한 경우 위 부등식의 상한이 더욱 유용해지는 결과를 갖는다. 또한, 위 정리로부터 더 사용하기 편한 따름정리를 얻을 수 있는데, 다음과 같다.

Corollary. 행렬 $M^{\star},M$ 의 고유값들이 각각 $|\lambda_{1}^{\star}|\geq\cdots\geq|\lambda_{r}^{\star}|>|\lambda_{r+1}^{\star}|\geq\cdots\geq|\lambda_{n}^{\star}|$ 와 $|\lambda_{1}|\geq\cdots\geq|\lambda_{r}\}|>|\lambda_{r+1}|\geq\cdots\geq|\lambda_{n}|$ 으로 주어진다고 하자.

만일 perturbation $E$에서 다음 성질이 성립하면

$$$$

\Vert E\Vert<(1-1/\sqrt{2})(|\lambda_{r}^{\star}|-|\lambda_{r+1}^{*}|)

$$이로부터 다음 부등식이 성립한다.$$

\begin{aligned} \mathrm{dist}(U,U^{\star})\leq\sqrt{2}\Vert\sin\Theta\Vert\leq\frac{\sqrt{2}\Vert EU^{\star}\Vert}{|\lambda_{r}^{\star}|-|\lambda_{r+1}^\star|}\leq \frac{\sqrt{2}\Vert E\Vert}{|\lambda_{r}^{\star}|-|\lambda_{r+1}^\star|}\ \mathrm{dist}(U,U^{\star})\leq\sqrt{2}\Vert\sin\Theta\Vert_F\leq\frac{\sqrt{2}\Vert EU^{\star}\Vert_F}{|\lambda_{r}^{\star}|-|\lambda_{r+1}^\star|}\leq \frac{\sqrt{2r}\Vert E\Vert_F}{|\lambda_{r}^{\star}|-|\lambda_{r+1}^\star|} \end{aligned}

Wedin's Theorem

David-Kahan Theorem을 일반 실행렬공간과 그것의 특이값공간(singular subspace)로 확장한 정리가 바로 Wedin's $\sin\Theta$ theorem이다. 우선 다음과 같은 $M=M^{\star}+E$ 에 대한 특이값분해를 가정하자.

그러면 다음과 같은 부등식이 성립한다(Wedin's $\sin\Theta$ Theorem).

References

• Yuxin Chen et al. - Spectral Methods for Data Science: A Statistical Perspective (2021)
• KOCW 현대통계학(김충락) 강의