행렬의 근사

Chapter 6 : Matrix Approximation

Edited by / 서원형 (wonhyeongseo)

---

• 목차

  1. 정의 4.23: 행렬의 Spectral Norm
  2. 정리 4.24: $A$ 의 spectral norm은 자신의 가장 큰 $\sigma_1$
  3. 정리 4.25: Eckart-Young 정리 (Eckart and Young, 1936)

---

SVD를 이용해 행렬 $A$ 를 $A = U \Sigma V^\top \in \mathbb{R} ^ {m \times n}$ 처럼 3개의 행렬곱으로 바꾸는 방법을 알아보았습니다. 이때 $U \in \mathbb{R} ^ {m \times m}$ 와 $V \in \mathbb{R} ^ {n \times n}$ 는 직교행렬이고 $\Sigma$ 는 주대각성분에 특이값을 지닌 행렬입니다. 지금부터 특이값 분해를 전부 하는 대신, 원리를 이용함으로써 행렬 $A$ 를 더 단순한 (저차원의) 행렬들 $A_i$ 로 어떻게 표현할 수 있는지를 보이겠습니다. 전부 계산하지 않으니 더 효율적이겠죠?

우선 계수가 1인 행렬 $A_i \in \mathbb{R} ^ {m \times n}$ 을 직교하는 행렬 $U$ 와 $V$ 의 $i$ 번째 벡터의 외적으로 구합니다.

\[A_i \coloneqq u_i v_i^{\top}\]

계수가 $r$ 인 행렬 $A \in \mathbb{R}^{m \times n}$ 은 계수가 1인 행렬의 합으로 아래와 같이 표현할 수 있습니다.

\[A = \sum_{i=1}^{r} \sigma_i u_i v_i^{\top} = \sum_{i=1}^{r} \sigma_i A_i\]

이러면 외적 행렬 $A_i$ 는 $i$ 번째 특이값 $\sigma_i$ 로 가중됩니다. 왜 위의 식이 성립할까요? 특이값 행렬 $\Sigma$ 가 동시에 대각행렬이기 때문에 $i$ 번째 좌우 직교 벡터들인 $u_i v_i^{\top}$ 만을 가져오고 마찬가지로 $i$ 번째 특이값 $\sigma_i$ 로 scale 하기 때문입니다. 다시 말하면, 모든 $\Sigma_{ij} u_i v_j^{\top}$ 는 $i \neq j$ 면 $\Sigma$ 가 대각행렬이기 때문에 사라집니다. $i > r$ 인 값들도 해당하는 특이값이 $0$ 이기 때문에 사라집니다.

이제 계수가 1인 $A_i$ 와 $r$ 개의 $A_i$ 를 합쳐 계수가 $r$인 행렬 $A$ 를 구했습니다. $i = 1, \dots , r$ , 즉 모든 계수 함수 $A_i$ 를 합치지 않고, 중간에 멈춰 $k < r$ 이면, 계수가 $k$ 인 $A$ 의 근사 행렬을 얻게 됩니다.

\[\hat{A} (k) = \sum_{i=1}^{k} \sigma_i u_i v_i^{\top} = \sum_{i=1}^{k} \sigma_i A_i\]

원래 행렬 $A$ 와 계수가 $k$ 인 근사 행렬 $\hat{A}(k)$ 의 차이 (에러)를 구하려면 norm의 개념이 필요합니다. 섹션 3.1에서 벡터의 길이를 구하는 데 이미 활용했었죠. 그럼 행렬에서의 norm을 정의해봅시다.

정의 4.23: 행렬의 Spectral Norm

$x \in \mathbb{R}^{n} \backslash { 0 }$ 일 때, 행렬 $A \in \mathbb{R} ^ {m \times n}$ 의 spectral norm 은

\[{\left\| A \right\|}_2 \coloneqq \max_{x} \frac{ {\left\| Ax \right\|_2}{ {\left\| x \right\|}_2}\]

로 정의됩니다. 그리고 벡터의 유클리드 노름을 표기할 때처럼 (수식의 오른쪽), 여기서 행렬의 아래 첨자 표기법 (수식의 왼쪽)을 소개합니다.

정리 4.24: $A$ 의 spectral norm은 자신의 가장 큰 $\sigma_1$

이 정리의 증명을 과제로 내겠습니다.

todo <> (https://en.wikipedia.org/wiki/Low-rank_approximation 이해하기)

정리 4.25: Eckart-Young 정리 (Eckart and Young, 1936)

---

---