Lecture 29. 특이값 분해 (SVD)

지금까지 배운 모든 분해에는 조건이 붙어 있었다.

$A = LU$ 는 소거가 막히지 않아야 하고, $A = QR$ 은 열이 독립이어야 하고, $S = Q\Lambda Q^{\mathsf T}$ 는 대칭이어야 하고, $A = S\Lambda S^{-1}$ 은 고유벡터가 $n$ 개 있어야 한다. 지난 강의에서는 마지막 조건이 깨졌을 때 얼마나 지저분해지는지도 보았다. 조르당 형은 존재하지만 손에 쥘 수 없었다.

특이값 분해에는 조건이 없다. 정사각행렬일 필요도 없고, 대칭일 필요도 없고, 가역일 필요도 없고, 랭크가 꽉 찰 필요도 없다. $3 \times 7$ 행렬이든 랭크 1짜리든 심지어 영행렬이든 전부 된다.

이런 일이 어떻게 가능한가. 대가가 하나 있다. 지금까지는 기저를 한 벌만 썼지만, 이제 두 벌을 쓴다. 들어가는 쪽에 한 벌, 나오는 쪽에 한 벌. 그것이 전부이다.

1. 원하는 것을 먼저 적는다¶

대각화가 안 되는 이유가 무엇이었나. 곰곰이 생각하면 이렇다. 기저 한 벌로 들어가는 쪽과 나오는 쪽을 동시에 감당하려 했기 때문이다.

$A\vv{x} = \lambda\vv{x}$ 는 들어간 방향과 나온 방향이 같기를 요구한다. 그것이 안 되는 행렬이 있고, 애초에 $m \neq n$ 이면 같을 수가 없다. $\R^3$ 에서 들어가 $\R^5$ 로 나오는데 어떻게 같은 방향이겠는가.

그러니 욕심을 하나 줄이자. 들어가는 쪽 기저와 나오는 쪽 기저를 따로 두는 것이다.

대신 나머지는 다 챙긴다. $\vv{v}$ 들은 서로 정규직교, $\vv{u}$ 들도 서로 정규직교, $\sigma$ 들은 음이 아니게. 방향이 뒤집혀야 하면 $\vv{u}$ 가 뒤집으면 되니 $\sigma$ 에 부호를 줄 이유가 없다.

행렬로 묶어 보자. $\vv{v}$ 들을 열에 세운 것을 $V$, $\vv{u}$ 들을 열에 세운 것을 $U$, $\sigma$ 들을 대각에 놓은 것을 $\Sigma$ 라 하면 (1)의 식들이 한 줄이 된다.

$V$ 의 열이 정규직교이므로 $V^{-1} = V^{\mathsf T}$ 이다(L17). 오른쪽에서 곱하면 끝이다.

2. 존재 증명 — $A^{\mathsf T}A$ 가 $U$ 를 지운다¶

미지수 둘을 동시에 못 풀겠으면 어떻게 하는가. 하나를 소거한다. 연립방정식에서 늘 하던 일이다.

(3)의 식이 성립한다고 가정하고 $A^{\mathsf T}A$ 를 계산해 보자.

$U$ 가 사라졌다. $U$ 의 열이 정규직교라는 조건이 가운데에서 $I$ 를 만들어 낸 덕이다. 그리고 $\Sigma^{\mathsf T}\Sigma$ 는 대각에 $\sigma_i^2$ 이 놓인 대각행렬이다.

(4)의 오른쪽을 다시 보자. 직교행렬 · 대각행렬 · 그 전치. L25의 스펙트럼 정리와 글자 그대로 같은 모양이다.

그러므로 $V$ 는 $A^{\mathsf T}A$ 의 고유벡터이고 $\sigma_i^2$ 은 그 고윳값이다. 거꾸로 읽으면 이것이 곧 만드는 방법이다.

왜 언제나 되는가¶

여기가 이 강의의 심장이다. 위 논증이 통하려면 두 가지가 필요하다.

첫째, $A^{\mathsf T}A$ 에 직교 고유벡터가 있어야 한다. 있다. L14에서 확인한 대로 $A^{\mathsf T}A$ 는 언제나 대칭이기 때문이다. 전치해 보면 바로 나온다.

대칭이면 L25의 스펙트럼 정리가 직교 고유벡터를 보장한다.

둘째, 고윳값이 음이 아니어야 한다. $\sigma_i = \sqrt{\lambda_i}$ 로 실수를 얻어야 하기 때문이다. 음이 아니다. L27에서 확인한 대로 $A^{\mathsf T}A$ 는 언제나 양의 준정부호이다.

3. $U$ 를 구하는 올바른 방법¶

$V$ 와 $\sigma$ 는 얻었다. $U$ 는 어떻게 하는가.

$AA^{\mathsf T}$ 에서 따로 구하고 싶어진다. 실제로 $AA^{\mathsf T} = U\Sigma\Sigma^{\mathsf T}U^{\mathsf T}$ 이라 $U$ 는 $AA^{\mathsf T}$ 의 고유벡터가 맞다. 그런데 그렇게 하면 안 된다.

올바른 방법은 (1)의 소망을 그대로 정의로 삼는 것이다.

이렇게 정의하면 $A\vv{v}_i = \sigma_i\vv{u}_i$ 는 정의에 의해 성립한다. 남는 것은 이 $\vv{u}$ 들이 정말 정규직교인지 확인하는 일뿐이다. 두 줄이면 된다.

가운데에서 괄호를 옮긴 것이 전부이다. 이제 $A^{\mathsf T}A\vv{v}_j = \sigma_j^2\vv{v}_j$ 를 쓴다.

$\vv{v}$ 들이 정규직교이므로 $i \neq j$ 이면 0이고 $i = j$ 이면 $\tfrac{\sigma_i}{\sigma_i} \cdot 1 = 1$ 이다. 정규직교가 공짜로 따라 나왔다.

$\sigma_i = 0$ 인 자리는 (8)의 식으로는 정의할 수 없다. 그때는 이미 얻은 $\vv{u}$ 들에 직교하도록 아무렇게나 채우면 된다(그람-슈미트, L17). 어차피 $\Sigma$ 에서 0이 곱해지므로 무엇을 넣든 $A$ 는 복원된다.

4. 앵커로 끝까지¶

$3 \times 2$ 행렬을 하나 잡자. 정사각이 아니므로 고윳값은 아예 정의되지 않는다. 그런데도 SVD는 된다.

첫째, $C^{\mathsf T}C$ 를 만든다.

L21과 L25에서 계속 나온 그 행렬이다. 고윳값이 3과 1이고 고유벡터가 $(1,1)$ 과 $(1,-1)$ 이다.

둘째, $\sigma$ 와 $V$ 를 읽는다. 큰 것부터 세운다.

셋째, $\vv{u}$ 를 (8)의 식으로 만든다.

길이를 재 보면 $\lVert(2,1,1)\rVert = \sqrt6$ 이고 $\lVert(0,1,-1)\rVert = \sqrt2$ 라 둘 다 길이 1이다. 내적은 $\tfrac{0 + 1 - 1}{\sqrt{12}} = 0$ 이다. 3절의 계산이 맞았다.

넷째, 남은 자리를 채운다. $C$ 는 $3 \times 2$ 인데 $\vv{u}$ 가 둘뿐이다. $\R^3$ 을 채우려면 하나가 더 필요하다. 앞의 둘에 직교하는 것을 고르면 된다.

$C^{\mathsf T}\vv{u}_3 = \vv{0}$ 임을 확인해 보자. 이 벡터가 좌영공간에 있다는 뜻이고, 다음 절에서 그 자리를 찾는다.

5. 네 부분공간이 완성된다¶

L10에서 네 개의 기본 부분공간을 그렸다. 그때는 각 칸의 기저를 아무렇게나 골랐다. 소거해서 나온 것을 그냥 썼고, 직교하지도 길이가 1이지도 않았다.

SVD는 그 네 칸에 가장 좋은 기저를 채워 넣는다.

랭크를 $r$ 이라 하자. 곧 0이 아닌 특이값의 개수이다. 그러면 이렇게 갈린다.

왜 그런지 하나만 확인해 보자. $i > r$ 이면 $\sigma_i = 0$ 이므로

뒤쪽 $\vv{v}$ 들이 영공간에 있다. 그리고 $\vv{v}$ 들이 서로 직교하므로 앞쪽 $\vv{v}$ 들은 영공간에 직교하고, L14에서 배운 대로 영공간의 직교여공간이 행공간이다.

고유분해와 견주면¶

6. 모든 선형변환은 회전, 늘이기, 회전이다¶

(3)의 식을 오른쪽부터 읽어 보자.

$V^{\mathsf T}$ 는 직교행렬이니 회전이다. 길이도 각도도 바꾸지 않는다. $\Sigma$ 는 대각행렬이니 축 방향으로 늘이거나 줄이기이다. $U$ 는 다시 회전이다.

L27에서 $\vv{x}^{\mathsf T}S\vv{x} = 1$ 이 타원이고 축이 고유벡터 방향임을 보았다. 그 타원이 여기서 다시 나타난다. 다만 이번에는 대칭이라는 조건이 필요 없다.

$\sigma_1$ 은 최대 증폭률이다¶

길이 1인 $\vv{x}$ 를 넣었을 때 나오는 것이 가장 긴 경우는 언제인가. $\vv{x}$ 를 $\vv{v}$ 기저로 펼쳐 $\vv{x} = \sum c_i\vv{v}_i$ 라 하면 $\sum c_i^2 = 1$ 이고

가운데 등호에서 $\vv{u}$ 들이 정규직교라는 것을 썼다. 오른쪽은 $\sigma_i^2$ 들의 가중평균이므로 가장 큰 것을 넘지 못한다.

이 최대 증폭률을 행렬의 2-노름이라 하고 $\lVert A\rVert_2$ 로 쓴다. $\sigma_1$ 이다.

특이값의 곱이 부피 배율이다¶

정사각행렬이면 (3)의 양변에 행렬식을 취할 수 있다. L18의 곱셈 규칙과 L20에서 본 $\det Q = \pm1$ 을 쓴다.

회전은 부피를 바꾸지 않으므로 늘인 만큼만 남는다. L20에서 평행육면체를 그리며 "부피 배율은 방향별 배율을 전부 곱해 놓은 값"이라고 했는데, 그 방향별 배율이 바로 특이값이었다.

앵커 $\begin{bmatrix} 3 & 0 \\ 4 & 5\end{bmatrix}$ 에서 $\sigma_1\sigma_2 = 3\sqrt5 \cdot \sqrt5 = 15$ 이고 $\det A = 15$ 이다.

7. 랭크 1 조각의 합¶

L25에서 $Q\Lambda Q^{\mathsf T}$ 를 열 곱하기 행으로 펼쳤다. 똑같이 한다. $U\Sigma$ 의 $i$ 열이 $\sigma_i\vv{u}_i$ 이고 $V^{\mathsf T}$ 의 $i$ 행이 $\vv{v}_i^{\mathsf T}$ 이므로

L3의 “열 × 행” 관점과 L11의 랭크 1 행렬이 여기서 만난다. 각 조각은 랭크가 1이고, 그 크기가 $\sigma_i$ 이다.

8. 앞의 몇 개만 남기면 최선이다¶

앞 $k$ 개만 남긴 것을 $A_k$ 라 하자.

랭크가 $k$ 인 행렬이다. 그런데 랭크 $k$ 인 행렬은 무수히 많다. 그중에서 $A_k$ 가 $A$ 에 가장 가깝다는 것이 다음 정리이다.

증명은 하지 않는다. 다만 이것이 전혀 자명하지 않은 사실이라는 점은 짚어 두자. "큰 것부터 남기고 잘라 낸다"는 소박한 발상이 무한히 많은 후보 중에서 최선이라는 보장은 어디에도 없었다.

오차의 크기도 읽어 두자. 버린 것이 $\sum_{i>k}\sigma_i\vv{u}_i\vv{v}_i^{\mathsf T}$ 이고 그것의 2-노름이 $\sigma_{k+1}$ 이다.

버린 것 중 가장 큰 것이 곧 오차이다.

9. 그래서 무엇을 할 수 있는가¶

압축¶

$m \times n$ 행렬을 통째로 저장하면 수가 $mn$ 개 필요하다. $A_k$ 를 저장하려면 $\vv{u}$ 가 $k$ 개($mk$), $\vv{v}$ 가 $k$ 개($nk$), $\sigma$ 가 $k$ 개이다.

왜 압축이 되는가¶

여기가 중요하다. 아무 행렬이나 압축되는 것이 아니다.

Figure 5의 아래 오른쪽을 보자. 그림은 특이값 여덟 개만으로 에너지의 99%를 담는데, 무작위 잡음은 123개가 필요하다. 저장량으로 따지면 그림은 8%, 잡음은 128% 이다. 잡음은 SVD로 압축하면 오히려 손해이다.

사진에서 이웃한 화소는 서로 비슷하고, 큰 구조가 반복되고, 조명은 매끄럽게 변한다. 그 규칙성이 곧 낮은 랭크이고, 그래서 앞쪽 몇 개에 정보가 몰린다.

잡음 제거¶

같은 이야기를 거꾸로 쓰면 잡음 제거가 된다. 신호에는 구조가 있어 큰 특이값에 모이고, 잡음은 구조가 없어 작은 특이값에 골고루 퍼진다. 작은 것을 잘라 내면 잡음만 사라진다.

조건수¶

가장 큰 특이값과 가장 작은 특이값의 비를 조건수라 한다.

L27에서 대칭행렬의 조건수를 고윳값의 비로 정의했는데, 그것의 일반판이다. 가장 크게 늘이는 방향과 가장 적게 늘이는 방향의 차이이고, 이 값이 크면 수치적으로 위험하다. L33에서 정면으로 다룬다.

차원 축소¶

데이터를 행렬로 늘어놓고 SVD를 취한 뒤 앞 $k$ 개만 남기는 것이 주성분분석의 본체이다. 고차원 데이터가 사실은 낮은 차원의 구조를 갖고 있다는 가정 위에 서 있고, SVD는 그 구조를 찾아내는 가장 기본적인 도구이다.

10. 자주 하는 오해¶

특이값이 고윳값의 절댓값이라는 오해¶

대칭행렬일 때만 맞다. 대칭이면 $A = Q\Lambda Q^{\mathsf T}$ 이고 이것이 곧 SVD이므로 $\sigma_i = |\lambda_i|$ 이다. 그러나 일반적으로는 전혀 다르다.

L28의 결함 행렬 $\begin{bmatrix} 3 & 1 \\ 0 & 3\end{bmatrix}$ 을 보자. 고윳값은 3이 두 번인데 특이값은 3.541 과 2.541 이다. 곱이 $3.541 \times 2.541 = 9 = \det$ 로 맞기는 하지만 하나하나는 다르다.

$U$ 를 $AA^{\mathsf T}$ 에서 따로 구하는 실수¶

3절에서 경고했다. 부호가 어긋난다.

SVD가 유일하다는 오해¶

특이값은 유일하다. 그러나 $U$ 와 $V$ 는 아니다. $\vv{u}_i$ 와 $\vv{v}_i$ 의 부호를 함께 뒤집어도 되고, 같은 $\sigma$ 가 겹치면 그 안에서 회전할 자유가 있다. $\sigma = 0$ 인 자리는 아예 아무것이나 채워도 된다.

소프트웨어가 $V$ 를 준다고 믿는 실수¶

가장 흔한 실전 버그이다. numpy.linalg.svd 는 $V$ 가 아니라 $V^{\mathsf T}$ 를 돌려준다. 받아서 그대로 $V$ 라고 쓰면 조용히 틀린 답이 나온다. 정사각이라 크기 검사도 통과한다.

랭크 $k$ 근사가 "앞 $k$ 개 열을 남기는 것"이라는 오해¶

열이 아니라 특이값 성분을 남기는 것이다. $A$ 의 앞 $k$ 열만 떼어 낸 것은 (23)의 $A_k$ 와 전혀 다르고, 최적도 아니다.

작은 특이값을 무조건 잡음으로 보는 오해¶

문제에 따라 작은 성분이 결정적일 수 있다. 조건수를 재는 것이 정확히 그 경우이다. $\sigma_n$ 이 작다는 사실 자체가 중요한 정보이다.

마치며...¶

이번 강의에서 다룬 것을 정리하면 다음과 같다.

유도가 짧았다는 것이 이 강의의 핵심이다. 들어가는 쪽과 나오는 쪽에 각각 다른 직교기저를 쓰겠다고 마음먹은 순간, 그리고 $A^{\mathsf T}A$ 가 언제나 대칭이라는 사실을 떠올린 순간, 나머지는 저절로 따라 나왔다.

조건이 없는 이유도 분명해졌다. $A$ 가 어떻게 생겼든 $A^{\mathsf T}A$ 는 대칭이고 양의 준정부호이다. 대칭행렬에는 직교 고유벡터가 있고, 준정부호이므로 고윳값이 음이 아니어서 제곱근을 취할 수 있다. 네 강의 전에 배운 스펙트럼 정리가 여기서 모든 것을 지탱하고 있다.

그리고 우리는 L10에서 그렸던 네 부분공간 그림을 마침내 완성하였다. 그때는 비어 있던 네 칸에 이제 가장 좋은 기저가 채워졌다. 아홉 강의 전 L20에서 그린 부피 그림도 $\prod\sigma_i = |\det A|$ 로 되돌아왔고, 두 강의 전 L27의 타원도 대칭이라는 조건 없이 다시 나타났다.

여기까지가 이 교재의 정점이다. 우리는 조건 없는 분해를 손에 넣었다.

그런데 한 가지 물음이 남는다. SVD는 들어가는 쪽과 나오는 쪽에서 각각 좋은 기저를 골랐다. 그렇다면 애초에 기저를 고른다는 것이 무슨 뜻인가. 행렬이란 도대체 무엇인가. 다음 강의에서는 지금까지의 전부를 한 층 위에서 다시 본다.

이번 강의의 내용을 파이썬으로 확인해 보려면 L29 실습 노트북으로 넘어가면 된다. 정의대로 SVD를 직접 만들어 numpy.linalg.svd 와 대조하고, $U$ 를 따로 구하면 왜 어긋나는지 확인하며, 이미지를 랭크별로 압축해 에카르트-영 정리가 정말 최선인지 무작위 행렬 수천 개와 겨뤄 볼 수 있다.