연결 강의: MIT 18.06 Linear Algebra - Lecture 29: Singular Value Decomposition

1. 이번 글의 위치

앞 글에서는 SVD의 기본 형태와 full-rank $2\times 2$ 예시를 봤다.

SVD의 핵심 형태는 다음이었다.

$$A=U\Sigma V^T$$

그리고 핵심 관계는 다음이었다.

$$Av_i=\sigma_i u_i$$

이번 글에서는 강의의 다음 순서에 맞춰 rank가 부족한 행렬을 본다.

rank-deficient matrix에서는 null space가 등장하고, SVD는 네 기본 부분공간의 orthonormal basis를 한 번에 정리해 준다.

---

2. Rank-One Matrix 예시

다음 행렬을 보자.

$$A= \begin{bmatrix} 4 & 3 \\ 8 & 6 \end{bmatrix}$$

두 번째 행은 첫 번째 행의 2배이다.

$$\begin{bmatrix} 8 & 6 \end{bmatrix} = 2 \begin{bmatrix} 4 & 3 \end{bmatrix}$$

따라서 이 행렬의 rank는 1이다.

$$\operatorname{rank}(A)=1$$

rank가 1이므로 row space와 column space는 각각 1차원이다.

null space와 left null space도 각각 1차원이다.

---

3. Row Space와 Null Space

row space는 행벡터들의 span이다.

이 행렬의 row space는 다음 벡터의 배수들로 이루어진다.

$$\begin{bmatrix} 4 \\ 3 \end{bmatrix}$$

즉 row space는 $\mathbb{R}^2$ 안의 하나의 직선이다.

SVD에서는 row space의 unit vector가 필요하다.

벡터 $(4,3)$의 길이는 5이다.

$$\sqrt{4^2+3^2}=5$$

따라서 row space의 unit vector는 다음이다.

$$v_1= \begin{bmatrix} \frac{4}{5} \\ \frac{3}{5} \end{bmatrix}$$

null space는 row space에 수직인 방향이다.

$(4,3)$에 수직인 unit vector는 다음처럼 잡을 수 있다.

$$v_2= \begin{bmatrix} \frac{3}{5} \\ -\frac{4}{5} \end{bmatrix}$$

실제로,

$$\begin{bmatrix} 4 & 3 \end{bmatrix} \begin{bmatrix} 3 \\ -4 \end{bmatrix} = 12-12=0$$

이다.

따라서 $v_2$는 null space 방향이다.

이제 $V$는 다음과 같다.

$$V= \begin{bmatrix} \frac{4}{5} & \frac{3}{5} \\ \frac{3}{5} & -\frac{4}{5} \end{bmatrix}$$

이 행렬은 orthogonal matrix이다.

---

4. Column Space와 Left Null Space

column space는 열벡터들의 span이다.

이 행렬의 열벡터들은 모두 다음 방향의 배수이다.

$$\begin{bmatrix} 1 \\ 2 \end{bmatrix}$$

예를 들어,

$$\begin{bmatrix} 4 \\ 8 \end{bmatrix} = 4 \begin{bmatrix} 1 \\ 2 \end{bmatrix}$$

이고,

$$\begin{bmatrix} 3 \\ 6 \end{bmatrix} = 3 \begin{bmatrix} 1 \\ 2 \end{bmatrix}$$

이다.

따라서 column space의 unit vector는 다음이다.

$$u_1= \frac{1}{\sqrt{5}} \begin{bmatrix} 1 \\ 2 \end{bmatrix}$$

left null space는 column space에 수직인 방향이다.

$(1,2)$에 수직인 unit vector는 다음처럼 잡을 수 있다.

$$u_2= \frac{1}{\sqrt{5}} \begin{bmatrix} 2 \\ -1 \end{bmatrix}$$

따라서,

$$U= \frac{1}{\sqrt{5}} \begin{bmatrix} 1 & 2 \\ 2 & -1 \end{bmatrix}$$

이다.

---

5. Singular Value 계산

singular value는 $A^TA$의 eigenvalue에서 나온다.

먼저 $A^TA$를 계산하자.

$$A^T= \begin{bmatrix} 4 & 8 \\ 3 & 6 \end{bmatrix}$$

따라서,

$$A^TA = \begin{bmatrix} 4 & 8 \\ 3 & 6 \end{bmatrix} \begin{bmatrix} 4 & 3 \\ 8 & 6 \end{bmatrix}$$

계산하면,

$$A^TA= \begin{bmatrix} 80 & 60 \\ 60 & 45 \end{bmatrix}$$

이 행렬도 rank가 1이다.

따라서 eigenvalue 중 하나는 0이다.

trace는 다음이다.

$$80+45=125$$

고유값의 합은 trace와 같으므로, 다른 eigenvalue는 125이다.

$$\lambda_1=125, \qquad \lambda_2=0$$

singular values는 eigenvalue의 양의 제곱근이다.

$$\sigma_1=\sqrt{125}$$ $$\sigma_2=0$$

따라서,

$$\Sigma= \begin{bmatrix} \sqrt{125} & 0 \\ 0 & 0 \end{bmatrix}$$

이다.

---

6. Rank-One Matrix의 SVD 조립

이제 세 조각을 모으면 다음이다.

$$A=U\Sigma V^T$$

여기서,

$$U= \frac{1}{\sqrt{5}} \begin{bmatrix} 1 & 2 \\ 2 & -1 \end{bmatrix}$$ $$\Sigma= \begin{bmatrix} \sqrt{125} & 0 \\ 0 & 0 \end{bmatrix}$$

이고,

$$V^T= \begin{bmatrix} \frac{4}{5} & \frac{3}{5} \\ \frac{3}{5} & -\frac{4}{5} \end{bmatrix}$$

이다.

곱을 확인해 보자.

먼저 $U\Sigma$를 계산하면,

$$U\Sigma = \frac{1}{\sqrt{5}} \begin{bmatrix} 1 & 2 \\ 2 & -1 \end{bmatrix} \begin{bmatrix} \sqrt{125} & 0 \\ 0 & 0 \end{bmatrix}$$

$\sqrt{125}=5\sqrt{5}$이므로,

$$U\Sigma = \begin{bmatrix} 5 & 0 \\ 10 & 0 \end{bmatrix}$$

이제 $V^T$를 곱하면,

$$U\Sigma V^T = \begin{bmatrix} 5 & 0 \\ 10 & 0 \end{bmatrix} \begin{bmatrix} \frac{4}{5} & \frac{3}{5} \\ \frac{3}{5} & -\frac{4}{5} \end{bmatrix}$$

계산 결과는 다음이다.

$$U\Sigma V^T = \begin{bmatrix} 4 & 3 \\ 8 & 6 \end{bmatrix}$$

즉 원래 행렬 $A$가 복원된다.

---

7. Rank-One SVD의 의미

이 예시에서는 singular value가 하나만 양수이다.

$$\sigma_1=\sqrt{125}, \qquad \sigma_2=0$$

따라서 $A$의 핵심 작용은 하나의 방향에서만 일어난다.

입력공간의 row space 방향 $v_1$은 column space 방향 $u_1$으로 간다.

$$Av_1=\sigma_1u_1$$

반면 null space 방향 $v_2$는 0으로 간다.

$$Av_2=0$$

그래서 $\Sigma$의 두 번째 diagonal entry가 0이다.

이것이 rank-deficient matrix에서 SVD가 null space를 처리하는 방식이다.

---

8. 네 기본 부분공간과 SVD

SVD는 네 기본 부분공간의 올바른 basis를 한 번에 제공한다.

$A$가 $m\times n$ 행렬이고 rank가 $r$이라고 하자.

그러면 $V$의 열벡터들은 $\mathbb{R}^n$의 orthonormal basis를 이룬다.

앞쪽 $r$개는 row space의 basis이다.

$$v_1,\dots,v_r$$

뒤쪽 $n-r$개는 null space의 basis이다.

$$v_{r+1},\dots,v_n$$

마찬가지로 $U$의 열벡터들은 $\mathbb{R}^m$의 orthonormal basis를 이룬다.

앞쪽 $r$개는 column space의 basis이다.

$$u_1,\dots,u_r$$

뒤쪽 $m-r$개는 left null space, 즉 $N(A^T)$의 basis이다.

$$u_{r+1},\dots,u_m$$

따라서 SVD는 다음 네 공간을 모두 정리한다.

1. row space
2. null space
3. column space
4. left null space

---

9. Dimension 정리

네 기본 부분공간의 차원은 다음과 같다.

공간	위치	차원	SVD에서의 basis
row space	$\mathbb{R}^n$	$r$	$v_1,\dots,v_r$
null space	$\mathbb{R}^n$	$n-r$	$v_{r+1},\dots,v_n$
column space	$\mathbb{R}^m$	$r$	$u_1,\dots,u_r$
left null space	$\mathbb{R}^m$	$m-r$	$u_{r+1},\dots,u_m$

이 basis들이 좋은 이유는 모두 orthonormal하기 때문이다.

하지만 orthonormal인 것만으로는 충분하지 않다. Gram-Schmidt를 쓰면 어떤 subspace에서도 orthonormal basis를 만들 수 있다.

SVD의 특별한 점은 이 basis들이 행렬 $A$를 diagonal하게 만든다는 것이다.

즉,

$$Av_i=\sigma_i u_i \qquad (i=1,\dots,r)$$

이고,

$$Av_i=0 \qquad (i=r+1,\dots,n)$$

이다.

각 $v_i$는 대응되는 $u_i$ 방향으로만 간다. 서로 다른 방향끼리 섞이지 않는다.

---

10. Reduced SVD와 Full SVD

rank가 $r$인 행렬에서는 핵심 정보만 모아 reduced SVD로 쓸 수 있다.

$$A=U_r\Sigma_r V_r^T$$

여기서,

$$U_r= \begin{bmatrix} | & | & & | \\ u_1 & u_2 & \cdots & u_r \\ | & | & & | \end{bmatrix}$$ $$V_r= \begin{bmatrix} | & | & & | \\ v_1 & v_2 & \cdots & v_r \\ | & | & & | \end{bmatrix}$$

이고,

$$\Sigma_r= \begin{bmatrix} \sigma_1 & 0 & \cdots & 0 \\ 0 & \sigma_2 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & \sigma_r \end{bmatrix}$$

이다.

full SVD는 여기에 null space와 left null space의 basis까지 붙인 것이다.

$$A=U\Sigma V^T$$

계산이나 데이터 압축에서는 reduced SVD가 더 자주 쓰인다. 하지만 네 기본 부분공간을 모두 보려면 full SVD가 구조를 더 잘 보여준다.

---

11. Rank-One Terms로 보는 SVD

SVD는 다음처럼 rank-one matrix들의 합으로도 쓸 수 있다.

$$A= \sigma_1u_1v_1^T +\sigma_2u_2v_2^T +\cdots +\sigma_ru_rv_r^T$$

rank-one 예시에서는 $r=1$이므로 다음 한 항만 남는다.

$$A=\sigma_1u_1v_1^T$$

실제로,

$$\sigma_1=\sqrt{125}=5\sqrt{5}$$ $$u_1= \frac{1}{\sqrt{5}} \begin{bmatrix} 1 \\ 2 \end{bmatrix}$$ $$v_1= \begin{bmatrix} \frac{4}{5} \\ \frac{3}{5} \end{bmatrix}$$

이므로,

$$\sigma_1u_1v_1^T = 5\sqrt{5} \cdot \frac{1}{\sqrt{5}} \begin{bmatrix} 1 \\ 2 \end{bmatrix} \begin{bmatrix} \frac{4}{5} & \frac{3}{5} \end{bmatrix}$$

정리하면,

$$= 5 \begin{bmatrix} 1 \\ 2 \end{bmatrix} \begin{bmatrix} \frac{4}{5} & \frac{3}{5} \end{bmatrix} = \begin{bmatrix} 4 & 3 \\ 8 & 6 \end{bmatrix}$$

이다.

이 관점은 image compression과도 연결된다. 이미지를 행렬로 보면, 큰 singular value에 해당하는 rank-one term 몇 개만 남겨도 원래 이미지의 큰 구조를 보존할 수 있다.

---

12. 핵심 정리

SVD는 단순히 행렬을 세 조각으로 분해하는 공식이 아니다.

$$A=U\Sigma V^T$$

SVD는 네 기본 부분공간에 가장 좋은 orthonormal basis를 골라 주는 방법이다.

입력공간 쪽에서는 $V$가 다음을 제공한다.

1. row space의 basis
2. null space의 basis

출력공간 쪽에서는 $U$가 다음을 제공한다.

1. column space의 basis
2. left null space의 basis

그리고 $A$는 이 basis들 사이에서 아주 단순하게 작동한다.

$$Av_i=\sigma_i u_i$$

row space 방향은 column space 방향으로 stretching되고, null space 방향은 0으로 간다.

이것이 SVD가 네 기본 부분공간, 고유값, 직교기저, 데이터 압축을 한 번에 연결하는 이유이다.