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

1. 이번 강의의 위치

이번 강의는 singular value decomposition, 즉 SVD를 다룬다.

SVD는 행렬분해 중에서도 가장 중요한 분해 중 하나이다. 강의에서는 SVD를 “final and best factorization”이라고 표현한다.

지금까지 여러 행렬분해를 봤다.

1. elimination에서 나온 $A=LU$
2. orthonormal basis에서 나온 $A=QR$
3. 고유값 분해에서 나온 $A=S\Lambda S^{-1}$
4. 대칭행렬에서 나온 $A=Q\Lambda Q^T$

SVD는 이 흐름을 가장 일반적인 행렬까지 확장한다.

핵심 형태는 다음이다.

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

여기서 $U$와 $V$는 orthogonal matrix이고, $\Sigma$는 diagonal에 가까운 직사각 대각행렬이다.

SVD의 가장 강한 점은 $A$가 어떤 행렬이어도 가능하다는 것이다.

$$A \in \mathbb{R}^{m\times n}$$

이어도 SVD는 존재한다.

---

2. 대칭 양의 정부호 행렬과 SVD의 관계

먼저 익숙한 경우부터 보자.

$A$가 symmetric positive definite matrix라면 다음처럼 분해할 수 있다.

$$A=Q\Lambda Q^T$$

대칭행렬이므로 eigenvector를 orthonormal하게 잡을 수 있고, positive definite이므로 eigenvalue가 모두 양수이다.

이 경우에는 SVD가 거의 eigenvalue decomposition과 같다.

$$A=Q\Lambda Q^T$$

여기서 왼쪽 orthogonal matrix와 오른쪽 orthogonal matrix가 같은 $Q$이다.

하지만 일반적인 행렬에서는 이렇게 하나의 $Q$만으로는 부족하다. 행렬이 대칭이 아닐 수도 있고, 정사각행렬이 아닐 수도 있기 때문이다.

그래서 SVD에서는 두 개의 orthogonal matrix가 필요하다.

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

$U$는 column space 쪽의 orthonormal basis를 담고, $V$는 row space 쪽의 orthonormal basis를 담는다.

---

3. SVD의 그림: Row Space에서 Column Space로

행렬 $A$는 선형변환이다.

$$A:\mathbb{R}^n \rightarrow \mathbb{R}^m$$

즉 $A$는 입력공간의 벡터를 출력공간의 벡터로 보낸다.

SVD는 이 선형변환을 가장 좋은 basis에서 보는 방법이다.

입력 쪽에서는 row space의 orthonormal basis를 고른다.

$$v_1,v_2,\dots,v_r$$

출력 쪽에서는 column space의 orthonormal basis를 고른다.

$$u_1,u_2,\dots,u_r$$

여기서 $r$은 rank이다.

SVD의 목표는 다음이 성립하도록 basis를 고르는 것이다.

$$Av_1=\sigma_1u_1$$ $$Av_2=\sigma_2u_2$$

계속해서,

$$Av_r=\sigma_ru_r$$

이다.

즉 입력공간의 직교기저 $v_i$들이 $A$에 의해 출력공간의 직교기저 $u_i$ 방향으로 이동한다.

$\sigma_i$는 그 방향에서 얼마나 늘어나는지를 나타내는 값이다.

이 값을 singular value라고 한다.

---

4. Singular Value의 의미

고유값 분해에서는 다음 식을 봤다.

$$Ax=\lambda x$$

즉 어떤 특별한 방향 $x$는 행렬 $A$를 곱해도 방향이 바뀌지 않고 크기만 $\lambda$배 된다.

SVD에서는 조금 다르다.

$$Av_i=\sigma_i u_i$$

여기서는 입력 방향 $v_i$가 출력 방향 $u_i$로 간다.

$A$가 일반적인 직사각행렬이면 입력공간과 출력공간의 차원 자체가 다를 수 있다. 따라서 같은 방향으로 남는다는 eigenvector 관점이 항상 맞지 않는다.

대신 SVD는 입력공간의 좋은 방향 $v_i$와 출력공간의 좋은 방향 $u_i$를 따로 찾는다.

그리고 그 사이의 stretching factor가 $\sigma_i$이다.

---

5. Matrix Form

위 식들을 한 번에 모으면 다음과 같다.

$$A \begin{bmatrix} | & | & & | \\ v_1 & v_2 & \cdots & v_r \\ | & | & & | \end{bmatrix} = \begin{bmatrix} | & | & & | \\ u_1 & u_2 & \cdots & u_r \\ | & | & & | \end{bmatrix} \begin{bmatrix} \sigma_1 & 0 & \cdots & 0 \\ 0 & \sigma_2 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & \sigma_r \end{bmatrix}$$

이를 간단히 쓰면,

$$AV_r=U_r\Sigma_r$$

이다.

full SVD에서는 null space와 left null space까지 포함해서 $V$와 $U$를 전체 orthogonal matrix로 확장한다.

그러면 최종적으로 다음이 된다.

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

$A$가 $m\times n$ 행렬이면,

$$U \in \mathbb{R}^{m\times m}$$ $$\Sigma \in \mathbb{R}^{m\times n}$$ $$V \in \mathbb{R}^{n\times n}$$

이다.

$U$와 $V$는 orthogonal matrix이므로,

$$U^TU=I$$ $$V^TV=I$$

이다.

---

6. Null Space는 어떻게 들어가는가

$A$의 rank가 $r$이면 row space의 차원은 $r$이다.

나머지 $n-r$차원은 null space이다.

null space에 있는 벡터 $v$는 다음을 만족한다.

$$Av=0$$

따라서 SVD에서 null space 방향은 singular value가 0인 방향으로 들어간다.

즉 $\Sigma$의 diagonal 뒤쪽에는 0이 들어간다.

이 때문에 null space는 SVD에서 자연스럽게 처리된다.

row space의 basis는 양수 singular value를 만들고, null space의 basis는 0 singular value를 만든다.

---

7. $A^TA$로 $V$를 구하는 이유

SVD를 다음처럼 쓰자.

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

이때 $U$와 $V$를 동시에 찾는 것은 어렵다.

그래서 먼저 $V$만 남기는 조합을 만든다.

그 조합이 바로 다음이다.

$$A^TA$$

계산해 보자.

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

따라서,

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

$U$는 orthogonal matrix이므로,

$$U^TU=I$$

이다.

따라서,

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

$\Sigma^T\Sigma$는 diagonal matrix이고, 대각성분은 singular value의 제곱이다.

$$\Sigma^T\Sigma= \begin{bmatrix} \sigma_1^2 & 0 & \cdots & 0 \\ 0 & \sigma_2^2 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & \sigma_n^2 \end{bmatrix}$$

즉 $A^TA$의 eigenvector가 $V$의 열벡터이고, $A^TA$의 eigenvalue가 $\sigma_i^2$이다.

$$A^TA v_i=\sigma_i^2 v_i$$

따라서,

$$\sigma_i=\sqrt{\lambda_i(A^TA)}$$

이다.

---

8. $AA^T$로 $U$를 구하는 이유

이번에는 반대로 $AA^T$를 본다.

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

$V$는 orthogonal matrix이므로,

$$V^TV=I$$

이다.

따라서,

$$AA^T = U\Sigma\Sigma^T U^T$$

즉 $AA^T$의 eigenvector가 $U$의 열벡터이고, eigenvalue는 마찬가지로 $\sigma_i^2$이다.

$$AA^T u_i=\sigma_i^2 u_i$$

정리하면 다음과 같다.

1. $V$는 $A^TA$의 orthonormal eigenvectors이다.
2. $U$는 $AA^T$의 orthonormal eigenvectors이다.
3. singular values는 $A^TA$ 또는 $AA^T$의 eigenvalue의 양의 제곱근이다.

---

9. 예시 1: Full-Rank $2\times 2$ Matrix

다음 행렬을 생각하자.

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

이 행렬은 invertible이므로 rank가 2이다.

따라서 row space와 column space는 모두 $\mathbb{R}^2$ 전체이다.

SVD를 위해 다음을 찾는다.

1. row space의 orthonormal basis $v_1,v_2$
2. column space의 orthonormal basis $u_1,u_2$
3. singular values $\sigma_1,\sigma_2$

---

10. $A^TA$ 계산

먼저 $A^TA$를 계산한다.

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

따라서,

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

계산하면,

$$A^TA = \begin{bmatrix} 25 & 7 \\ 7 & 25 \end{bmatrix}$$

이 행렬은 대칭행렬이고 positive definite이다.

이제 이 행렬의 eigenvectors가 $v_1,v_2$가 된다.

---

11. $A^TA$의 Eigenvalues와 $V$

행렬

$$\begin{bmatrix} 25 & 7 \\ 7 & 25 \end{bmatrix}$$

의 고유벡터는 익숙한 형태이다.

첫 번째 고유벡터는 다음이다.

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

실제로,

$$\begin{bmatrix} 25 & 7 \\ 7 & 25 \end{bmatrix} \begin{bmatrix} 1 \\ 1 \end{bmatrix} = \begin{bmatrix} 32 \\ 32 \end{bmatrix} = 32 \begin{bmatrix} 1 \\ 1 \end{bmatrix}$$

따라서 첫 번째 eigenvalue는 32이다.

두 번째 고유벡터는 다음이다.

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

실제로,

$$\begin{bmatrix} 25 & 7 \\ 7 & 25 \end{bmatrix} \begin{bmatrix} 1 \\ -1 \end{bmatrix} = \begin{bmatrix} 18 \\ -18 \end{bmatrix} = 18 \begin{bmatrix} 1 \\ -1 \end{bmatrix}$$

따라서 두 번째 eigenvalue는 18이다.

unit vector로 만들면,

$$v_1= \frac{1}{\sqrt{2}} \begin{bmatrix} 1 \\ 1 \end{bmatrix}$$ $$v_2= \frac{1}{\sqrt{2}} \begin{bmatrix} 1 \\ -1 \end{bmatrix}$$

이다.

따라서,

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

이다.

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

$$\sigma_1=\sqrt{32}$$ $$\sigma_2=\sqrt{18}$$

---

12. $AA^T$ 계산

이제 $U$를 구하기 위해 $AA^T$를 계산한다.

$$AA^T = \begin{bmatrix} 4 & 4 \\ -3 & 3 \end{bmatrix} \begin{bmatrix} 4 & -3 \\ 4 & 3 \end{bmatrix}$$

계산하면,

$$AA^T= \begin{bmatrix} 32 & 0 \\ 0 & 18 \end{bmatrix}$$

이번 예시는 운 좋게 $AA^T$가 이미 diagonal matrix이다.

따라서 eigenvectors는 표준기저이다.

첫 번째 eigenvector는 다음이다.

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

두 번째 eigenvector는 부호 선택을 고려해서 다음처럼 잡는다.

$$\begin{bmatrix} 0 \\ -1 \end{bmatrix}$$

고유벡터의 부호는 자유롭게 바꿀 수 있다. 여기서는 최종 곱이 원래 $A$와 맞도록 두 번째 vector의 부호를 음수로 잡는다.

따라서,

$$U= \begin{bmatrix} 1 & 0 \\ 0 & -1 \end{bmatrix}$$

이다.

---

13. SVD 조립

이제 세 조각을 모은다.

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

여기서,

$$U= \begin{bmatrix} 1 & 0 \\ 0 & -1 \end{bmatrix}$$ $$\Sigma= \begin{bmatrix} \sqrt{32} & 0 \\ 0 & \sqrt{18} \end{bmatrix}$$ $$V^T= \frac{1}{\sqrt{2}} \begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix}$$

이다.

곱하면,

$$\Sigma V^T = \begin{bmatrix} \sqrt{32} & 0 \\ 0 & \sqrt{18} \end{bmatrix} \frac{1}{\sqrt{2}} \begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix}$$ $$= \begin{bmatrix} 4 & 4 \\ 3 & -3 \end{bmatrix}$$

여기에 $U$를 곱하면,

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

따라서 원래 행렬 $A$가 복원된다.

이 예시에서 중요한 점은 고유벡터의 부호 선택이다. $u_i$나 $v_i$는 eigenvector이므로 부호를 바꿔도 여전히 eigenvector이다. SVD에서는 singular value를 양수로 유지하고, 필요한 부호는 $U$나 $V$의 vector 쪽에서 조정한다.

---

14. Image Processing 관점의 연결

Reading 제목이 “Image Processing by Linear Algebra”인 이유는 SVD가 이미지 처리에서 바로 쓰이기 때문이다.

흑백 이미지는 숫자 행렬로 볼 수 있다. 각 entry는 pixel의 밝기이다.

SVD는 이미지를 다음처럼 여러 rank-one matrix의 합으로 분해한다.

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

큰 singular value에 해당하는 항들은 이미지의 중요한 구조를 많이 담고, 작은 singular value에 해당하는 항들은 상대적으로 덜 중요한 세부 정보를 담는다.

그래서 큰 singular value 몇 개만 남기면 이미지를 압축할 수 있다.

즉 SVD는 단순한 분해 공식이 아니라, 행렬 안의 중요한 방향과 크기를 순서대로 꺼내는 방법이다.

---

15. 핵심 정리

SVD는 임의의 행렬 $A$를 다음처럼 분해한다.

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

$V$는 입력공간, 특히 row space와 null space 쪽의 orthonormal basis를 담는다.

$U$는 출력공간, 즉 column space와 left null space 쪽의 orthonormal basis를 담는다.

$\Sigma$의 대각성분은 singular values이다.

핵심 관계는 다음이다.

$$Av_i=\sigma_i u_i$$

또 $V$와 $U$는 각각 다음에서 나온다.

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

즉,

1. $A^TA$의 eigenvectors가 $V$이다.
2. $AA^T$의 eigenvectors가 $U$이다.
3. eigenvalues의 양의 제곱근이 singular values이다.

다음 글에서는 rank가 부족한 행렬에서 null space가 SVD에 어떻게 들어가는지, 그리고 SVD가 네 기본 부분공간의 좋은 basis를 어떻게 만들어 주는지 본다.