18장. 특잇값 분해 (SVD)

모든 행렬은 '회전 → 축 방향 늘이기 → 회전'의 세 단계로 쪼갤 수 있습니다. 이것이 특잇값 분해(SVD)이고, 선형대수에서 가장 쓸모 있는 정리 가운데 하나입니다. 이 장에서는 SVD를 대칭행렬의 고윳값으로 구하고, 이미지 압축, 유사역행렬, 데이터의 주성분 분석(PCA)에 적용합니다.

18.1 모든 행렬을 위한 대각화

질문. 대칭행렬은 $Q\Lambda Q^T$로 아름답게 분해되었습니다. 하지만 대부분의 행렬은 대칭이 아니고, 직사각형이기도 합니다. $m \times n$ 행렬 $A$에 대해서도 “서로 수직인 축들을 서로 수직인 축들로 보내는” 좌표계를 찾을 수 있을까요?

대각화 $A = X\Lambda X^{-1}$에는 세 가지 한계가 있었습니다. 정사각행렬이어야 하고, 고유벡터가 충분해야 하고, 고유벡터가 보통 수직이 아닙니다. 특잇값 분해(SVD)는 세 한계를 한꺼번에 넘습니다. 대가는 입력 공간과 출력 공간에 서로 다른 기저를 쓰는 것입니다. 그 대가를 치르면 모든 행렬이 대각행렬이 됩니다.

$A\mathbf{v}_i = \sigma_i\mathbf{u}_i$: 정규직교인 입력 기저 $\mathbf{v}_i$가, 정규직교인 출력 기저 $\mathbf{u}_i$의 $\sigma_i$배로 갑니다.

18.2 원을 타원으로

그림 18.1. $A = \begin{bmatrix} 3 & 0 \\ 4 & 5 \end{bmatrix}$. 단위원은 타원이 됩니다. 수직인 $\mathbf{v}_1, \mathbf{v}_2$는 타원의 두 축 방향 $\mathbf{u}_1, \mathbf{u}_2$로 가고, 반축의 길이가 특잇값 $\sigma_1 = 3\sqrt5$, $\sigma_2 = \sqrt5$입니다.

어떤 행렬이든 단위원(구)을 타원(타원체)으로 보냅니다. 타원에는 서로 수직인 축이 있습니다. 원 위에서 그 축의 끝으로 가는 점들이 $\mathbf{v}_1, \mathbf{v}_2$입니다. 그런데 이 점들도 원 위에서 서로 수직입니다. 이것이 SVD의 그림입니다.

$A = \begin{bmatrix} 3 & 0 \\ 4 & 5 \end{bmatrix}$를 예로 듭시다. 대칭이 아니고, 고유벡터 $(0, 1)$과 $(1, -2)$는 수직이 아닙니다. 그래도 수직인 $\mathbf{v}_1 = \frac{1}{\sqrt2}(1, 1)$, $\mathbf{v}_2 = \frac{1}{\sqrt2}(-1, 1)$을 넣으면

두 출력의 내적은 $\frac12(-9 + 9) = 0$으로 수직입니다. 길이는 $\sigma_1 = \sqrt{45} = 3\sqrt5$, $\sigma_2 = \sqrt5$입니다. 정규화하면 $\mathbf{u}_1 = \frac{1}{\sqrt{10}}(1, 3)$, $\mathbf{u}_2 = \frac{1}{\sqrt{10}}(-3, 1)$.

이 $\mathbf{v}_i$는 어떻게 찾았을까요? 다음 절의 답: $A^TA$의 고유벡터입니다.

18.3 SVD의 구성

정리 18.1 (특잇값 분해). 랭크가 $r$인 $m \times n$ 실수 행렬 $A$는

로 쓸 수 있습니다. $U$는 $m \times m$ 직교행렬, $V$는 $n \times n$ 직교행렬, $\Sigma$는 $m \times n$ 행렬로 대각에 $\sigma_1 \ge \sigma_2 \ge \cdots \ge \sigma_r > 0$이 있고 나머지는 0입니다. $\sigma_i$를 $A$의 특잇값(singular values), $U$와 $V$의 열을 왼쪽·오른쪽 특이벡터(singular vectors)라 합니다.

증명. 1단계. $A^TA$는 $n \times n$ 대칭이고 양반정치입니다(문제 17.9). 스펙트럴 정리에 의해 정규직교 고유벡터 $\mathbf{v}_1, \ldots, \mathbf{v}_n$과 고윳값 $\lambda_1 \ge \cdots \ge \lambda_n \ge 0$이 있습니다. $N(A^TA) = N(A)$ (정리 13.9의 증명)이고 차원이 $n - r$이므로, 양수인 고윳값은 정확히 $r$개입니다. $\sigma_i = \sqrt{\lambda_i}$로 둡니다.

2단계. $i \le r$에 대해 $\mathbf{u}_i = A\mathbf{v}_i/\sigma_i$로 정의합니다. 이들은 정규직교입니다.

3단계. $\mathbf{u}_1, \ldots, \mathbf{u}_r$을 $\mathbb{R}^m$의 정규직교 기저 $\mathbf{u}_1, \ldots, \mathbf{u}_m$으로 확장합니다. $i > r$이면 $A\mathbf{v}_i = \mathbf{0}$입니다($\lVert A\mathbf{v}_i \rVert^2 = \lambda_i = 0$). 따라서 모든 $i$에 대해 $A\mathbf{v}_i = \sigma_i\mathbf{u}_i$ ($i > r$이면 $\sigma_i = 0$)이고, 행렬로 $AV = U\Sigma$. $V$가 직교이므로 $A = U\Sigma V^T$. ■

예제 18.2. $A = \begin{bmatrix} 3 & 0 \\ 4 & 5 \end{bmatrix}$: $A^TA = \begin{bmatrix} 25 & 20 \\ 20 & 25 \end{bmatrix}$, 고윳값 45, 5, 고유벡터 $\frac{1}{\sqrt2}(1, 1)$, $\frac{1}{\sqrt2}(-1, 1)$. 앞 절의 계산과 함께

검산: $\sigma_1\sigma_2 = 15 = \lvert \det A \rvert$.

직관. $A = U\Sigma V^T$를 오른쪽부터 읽으면 세 단계의 변환입니다.

1. $V^T$: 입력을 회전(또는 반사)해서 $\mathbf{v}_i$들을 좌표축에 맞춥니다.
2. $\Sigma$: 각 축 방향으로 $\sigma_i$배 늘입니다(차원이 다르면 축을 추가하거나 버립니다).
3. $U$: 출력을 회전해서 좌표축을 $\mathbf{u}_i$들에 맞춥니다.

모든 선형변환은 “회전 → 늘이기 → 회전”입니다.

$AA^T = U\Sigma\Sigma^TU^T$이므로 $\mathbf{u}_i$는 $AA^T$의 고유벡터이고 고윳값은 같은 $\sigma_i^2$입니다. 계산할 때는 $\mathbf{v}_i$를 먼저 구하고 $\mathbf{u}_i = A\mathbf{v}_i/\sigma_i$로 구하는 것이 부호를 맞추기 쉽습니다. $\mathbf{u}_i$를 따로 $AA^T$에서 구하면 $\pm$부호가 어긋날 수 있습니다.

▶ 문제 18.1–18.4

18.4 SVD와 4대 부분공간

SVD는 4대 부분공간의 정규직교 기저를 한꺼번에 줍니다.

$\mathbf{v}_i$ ($i \le r$)는 $\mathbf{u}_i$의 $\sigma_i$배로 갑니다. 12장의 그림 12.2에서 “행공간이 열공간으로 갑니다”를 정확히 그린 것입니다. SVD는 행공간과 열공간에 기저를 짝지어 깔아서, 그 사이의 변환을 대각으로 만듭니다.

▶ 문제 18.5

18.5 랭크 1 조각들의 합과 근사

$A = U\Sigma V^T$를 열×행의 합으로 쓰면

각 조각은 랭크 1이고, 크기 순서로 정렬되어 있습니다. 첫 $k$개만 남긴

는 랭크 $k$입니다.

정리 18.3 (에카르트–영). 랭크가 $k$ 이하인 모든 행렬 $B$ 중에서, $A$와의 거리 $\lVert A - B \rVert$가 가장 작은 것은 $A_k$입니다. 이때 오차는 $\sigma_{k+1}$입니다.

(행렬의 거리 $\lVert A - B \rVert$는 “$\lVert (A - B)\mathbf{x} \rVert$의 최댓값, 단 $\lVert \mathbf{x} \rVert = 1$”로 정의하며 30장에서 자세히 다룹니다. 증명도 그때 합니다.)

예제 18.4 (이미지 압축). 흑백 사진은 각 픽셀의 밝기를 성분으로 하는 큰 행렬입니다. $1000 \times 1000$ 사진을 저장하려면 수 100만 개가 필요합니다. 그런데 실제 사진은 특잇값이 빠르게 작아지는 경우가 많아서, 처음 50개 조각만 남긴 $A_{50}$도 원본과 거의 구별되지 않습니다. $A_{50}$을 저장하는 데는 $\mathbf{u}_i, \mathbf{v}_i, \sigma_i$ 50세트, 약 $50 \times 2001 \approx 10$만 개면 됩니다. 10분의 1입니다.

같은 아이디어가 자료 분석의 주성분 분석(PCA, 31장)입니다. 자료 행렬의 첫 몇 개 특이벡터가 자료가 가장 많이 퍼져 있는 방향들입니다.

▶ 문제 18.6–18.7

18.6 특잇값의 의미

• $\sigma_1 = \max_{\lVert \mathbf{x} \rVert = 1}\lVert A\mathbf{x} \rVert$: $A$가 벡터를 가장 크게 늘이는 배율(문제 18.8).
• 정사각 가역 $A$에서 $\sigma_n = \min_{\lVert \mathbf{x} \rVert = 1}\lVert A\mathbf{x} \rVert$: 가장 작게 줄이는 배율.
• $\lvert \det A \rvert = \sigma_1\sigma_2 \cdots \sigma_n$ (정사각): 직교행렬은 부피를 바꾸지 않으므로.
• $\sigma_1/\sigma_n$을 조건수(condition number)라 합니다. 이 값이 크면 $A\mathbf{x} = \mathbf{b}$의 해가 $\mathbf{b}$의 작은 오차에 민감합니다(30장).

고윳값과 특잇값은 다릅니다. $A = \begin{bmatrix} 3 & 0 \\ 4 & 5 \end{bmatrix}$의 고윳값은 3, 5이고 특잇값은 $3\sqrt5 \approx 6.7$, $\sqrt5 \approx 2.2$입니다. 대칭 양반정치 행렬에서만 둘이 같습니다(문제 18.3).

18.7 유사역행렬

$A$가 가역이 아니어도 SVD로 “거의 역행렬”을 만들 수 있습니다.

정의 18.5 (유사역행렬). $A = U\Sigma V^T$에 대해 $A^+ = V\Sigma^+U^T$를 $A$의 유사역행렬(pseudoinverse)이라 합니다. $\Sigma^+$는 $\Sigma$를 전치하고 0이 아닌 $\sigma_i$를 $1/\sigma_i$로 바꾼 $n \times m$ 행렬입니다.

$A^+$는 $\mathbf{u}_i$를 $\mathbf{v}_i/\sigma_i$로 보내고 ($i \le r$), $\mathbf{u}_i$ ($i > r$)는 $\mathbf{0}$으로 보냅니다. 즉 열공간에서 행공간으로 되돌리고, 왼쪽 영공간은 버립니다. $A$가 가역이면 $A^+ = A^{-1}$입니다.

$A\mathbf{x} = \mathbf{b}$에 대해 $\mathbf{x}^+ = A^+\mathbf{b}$는

• $\mathbf{b}$가 열공간에 있든 없든 언제나 정의되고,
• 최소제곱 해 중 하나이며 (오차 $\lVert A\mathbf{x} - \mathbf{b} \rVert$를 최소로),
• 그런 해가 여럿이면 그중 길이가 가장 짧은 것입니다(영공간 성분이 0이므로).

열이 독립이면 $A^+ = (A^TA)^{-1}A^T$로 13장의 최소제곱 공식과 같습니다(문제 18.10).

▶ 문제 18.8–18.10

쓰이는 곳. 주성분 분석(PCA), 이미지·데이터 압축, 잠재 의미 분석, 추천 시스템, 최소제곱의 유사역행렬이 모두 SVD입니다. 논문에서 $A = U\Sigma V^T$를 보면 '회전–늘이기–회전'으로 읽습니다.

이 장의 요약

• 모든 $m \times n$ 행렬은 $A = U\Sigma V^T$. $U$, $V$는 직교, $\Sigma$는 대각에 $\sigma_1 \ge \cdots \ge \sigma_r > 0$.
• $\mathbf{v}_i$: $A^TA$의 고유벡터, $\sigma_i = \sqrt{\lambda_i(A^TA)}$, $\mathbf{u}_i = A\mathbf{v}_i/\sigma_i$.
• 그림: 회전 → 늘이기 → 회전. 단위구는 반축 $\sigma_i$인 타원체가 됩니다.
• $\mathbf{v}$들과 $\mathbf{u}$들이 4대 부분공간의 정규직교 기저를 줍니다.
• $A = \sum\sigma_i\mathbf{u}_i\mathbf{v}_i^T$. 앞의 $k$개가 가장 좋은 랭크 $k$ 근사입니다.
• 유사역행렬 $A^+ = V\Sigma^+U^T$는 최소제곱 해 중 가장 짧은 것을 줍니다.

문제

3.162
0

3
2

3
1x1
1x3
3x3

3/2
3/2
9/2
9/2

0.2
0.2