- 선형대수 강의 43–45강 정리
- KAIST DAVIAN Lab 기초 과목 스터디의 선형대수 강의다
SVD의 형태와 고유값 분해와의 비교
정의와 크기
고유값 분해(eigendecomposition)와 대각화는 정사각행렬에서만 정의된다. 이를 임의의 직사각행렬로 확장한 것이 특이값 분해(singular value decomposition, SVD) 다. \(m \times n\) 행렬 \(A\)의 SVD는 \(A\)를 세 행렬의 곱으로 나타낸다.
\[A = U \Sigma V^T\]각 행렬의 크기와 성질은 다음과 같다.
- \(U\): \(m \times m\) 직교행렬(orthogonal matrix). 열이 정규직교(orthonormal)다.
- \(\Sigma\): \(A\)와 같은 \(m \times n\) 크기. 주대각선 위치 \((i, i)\)에만 0이 아닌 값이 올 수 있고 나머지는 모두 0이다.
- \(V\): \(n \times n\) 직교행렬. 따라서 \(V^T\)의 행들은 정규직교다.
엄밀히 말해 대각행렬은 정사각행렬에서 정의되지만, \(\Sigma\)처럼 직사각형이면서 대각 위치에만 값이 있는 행렬도 같은 방식으로 생각한다. 예를 들어 \(m = 3\), \(n = 2\)이면 \(\Sigma\)는 위쪽 \(2 \times 2\) 대각 블록 아래에 영인 행이 하나 붙은 형태다.
\[\Sigma = \begin{bmatrix} \sigma_1 & 0 \\ 0 & \sigma_2 \\ 0 & 0 \end{bmatrix}\]\(\Sigma\)의 대각성분은 \(m\)과 \(n\) 중 작은 수만큼 있다.
고유값 분해와의 비교
세 분해를 나란히 놓아 보자.
| 분해 | 형태 | 입력 | 양쪽 행렬 | 존재 |
|---|---|---|---|---|
| 고유값 분해 | \(A = VDV^{-1}\) | 정사각행렬 | 같은 \(V\), 서로 역행렬 | 독립인 고유벡터가 \(n\)개일 때만 |
| 스펙트럼 분해 | \(A = PDP^T\) | 대칭행렬 | 같은 \(P\), 직교행렬 | 항상 |
| SVD | \(A = U\Sigma V^T\) | 임의의 행렬 | 서로 다른 \(U\), \(V\), 둘 다 직교행렬 | 항상 |
공통점은 가운데 행렬이 대각 형태라는 것이다. 차이는 양쪽을 감싸는 행렬에 있다.
- 고유값 분해에서는 하나의 행렬 \(V\)와 그 역행렬로 양쪽을 모두 해결해야 한다. \(V\)가 가역이려면 선형독립인 고유벡터 \(n\)개가 필요하고, 이것이 항상 가능하지는 않다.
- 대칭행렬의 스펙트럼 분해에서는 \(V\)가 직교행렬 \(P\)가 되어 \(P^{-1} = P^T\)다.
- SVD에서는 왼쪽의 \(U\)와 오른쪽의 \(V\)를 따로 고를 수 있다.
SVD는 조절할 수 있는 행렬이 하나 더 많으므로 자유도가 더 크다. 식을 만족시키는 데 쓸 수 있는 카드가 더 많은 셈이다. 그 결과 고유값 분해는 일부 정사각행렬에만 존재하지만, SVD는 모든 행렬에 대해 항상 존재한다.
외적의 합으로 보기
\(\Sigma V^T\)를 먼저 계산해 보자. 행렬 곱을 행의 선형결합으로 보면, \(\Sigma\)의 각 행은 \(V^T\)의 행들을 결합하는 가중치를 준다. \(\Sigma\)의 \(i\)번째 행에서 0이 아닌 성분은 \(\sigma_i\) 하나뿐이므로, \(\Sigma V^T\)의 \(i\)번째 행은 \(\sigma_i v_i^T\)다. 대각성분이 없는 아래쪽 행들은 영인 행이 된다.
이제 \(U(\Sigma V^T)\)를 (열)×(행) 외적(outer product)의 합으로 본다. \(U\)의 열 \(u_i\)와 \(\Sigma V^T\)의 행 \(\sigma_i v_i^T\)를 짝지어 더하면 된다. 영인 행과 짝지어지는 \(u_i\)는 영행렬만 만들므로 빠진다. 따라서 \(k = \min(m, n)\)으로 두면 다음과 같다.
\[A = \sigma_1 u_1 v_1^T + \sigma_2 u_2 v_2^T + \cdots + \sigma_k u_k v_k^T\]스펙트럼 분해 \(A = \sum_j \lambda_j u_j u_j^T\)와 같은 모양이다. 차이는 랭크 1(rank 1) 조각의 왼쪽 벡터와 오른쪽 벡터가 서로 다르다는 점이다. 가운데 대각성분은 각 조각의 가중치 역할을 한다.
축약된 SVD
외적의 합에서 쓰이지 않는 부분을 잘라내면 더 작은 형태를 얻는다. \(m > n\)이면 \(\Sigma\)의 아래쪽 영인 블록과 그에 곱해지는 \(U\)의 마지막 \(m - n\)개 열을 버릴 수 있다.
\[A = U_n \Sigma_n V^T\]여기서 \(U_n\)은 \(m \times n\), \(\Sigma_n\)은 \(n \times n\) 대각행렬, \(V\)는 \(n \times n\)이다. 곱은 원래 SVD와 정확히 같다. 대각성분 중 0인 것까지 버리면 다음 강의에서 볼 축약된 SVD(reduced SVD) \(A = U_r D V_r^T\)가 된다.
특이값과 열공간의 직교기저
\(A^TA\)에서 출발한다
SVD를 구할 때는 \(A^TA\)에서 시작한다. \(A\)가 \(m \times n\) 직사각행렬이어도 \(A^TA\)는 \(n \times n\) 대칭행렬이다. 따라서 스펙트럼 정리에 의해 항상 직교대각화 가능하다. \(A^TA\)의 고유값 \(\lambda_1, \dots, \lambda_n\)과 정규직교 고유벡터 \(v_1, \dots, v_n\)을 잡는다.
이 고유값들은 모두 0 이상이다. \(A^TA v_i = \lambda_i v_i\)이고 \(\lVert v_i \rVert = 1\)이면 다음이 성립한다.
\[\lVert Av_i \rVert^2 = (Av_i)^T(Av_i) = v_i^T A^TA v_i = v_i^T (\lambda_i v_i) = \lambda_i\]길이의 제곱은 음수가 될 수 없으므로 \(\lambda_i \ge 0\)이다. 이 성질 때문에 \(A^TA\)를 양의 준정부호(positive semidefinite) 행렬이라 한다. 고유값을 크기순으로 정렬한다.
\[\lambda_1 \ge \lambda_2 \ge \cdots \ge \lambda_n \ge 0\]특이값의 정의
정의. \(A\)의 특이값(singular value) 은 \(A^TA\)의 고유값의 제곱근이다.
\[\sigma_i = \sqrt{\lambda_i}, \qquad \sigma_1 \ge \sigma_2 \ge \cdots \ge \sigma_n \ge 0\]고유값이 음수가 아니므로 제곱근은 항상 실수다. 위의 계산은 특이값의 기하학적 의미도 알려 준다.
\[\sigma_i = \lVert Av_i \rVert\]즉 \(\sigma_i\)는 \(A^TA\)의 단위 고유벡터 \(v_i\)를 \(A\)로 변환한 벡터의 길이다.
핵심 정리
\(A\)가 0이 아닌 특이값을 \(r\)개 가진다고 하자. 예를 들어 \(A\)가 \(5 \times 3\)이면 \(A^TA\)는 \(3 \times 3\)이고 고유값은 3개다. 그 고유값이 \(8, 5, 0\)이라면 0이 아닌 것은 2개이므로 \(r = 2\)다. 일반적으로 \(r \le \min(m, n)\)이다.
정리. \(\{v_1, \dots, v_n\}\)이 \(A^TA\)의 정규직교 고유벡터이고 \(\lambda_1 \ge \cdots \ge \lambda_n\)이며, \(A\)가 0이 아닌 특이값을 \(r\)개 가진다고 하자. 그러면 \(\{Av_1, \dots, Av_r\}\)는 \(\operatorname{Col} A\)의 직교기저이고, \(\operatorname{rank} A = r\)이다.
\(v_i\)는 \(\mathbb{R}^n\)의 벡터이고, \(Av_i\)는 \(\mathbb{R}^m\)의 벡터다. 정리의 내용은, \(\mathbb{R}^n\)에서 서로 직교하던 고유벡터들을 \(A\)로 옮겨도 \(\mathbb{R}^m\)에서 여전히 서로 직교한다는 것이다. 길이는 1에서 \(\sigma_i\)로 바뀐다.
아래 예제 2의 \(A = \begin{bmatrix} 3 & 0 \\ 4 & 5 \end{bmatrix}\)가 단위원을 타원으로 보내는 모습. 표준기저 \(e_1, e_2\)의 상은 \(36.9^\circ\)로 좁혀지지만, \(A^TA\)의 고유벡터 \(v_1, v_2\)의 상은 여전히 직교한다.
왼쪽의 두 쌍 \(e_1, e_2\)(회색)와 \(v_1, v_2\)(파랑, 빨강)는 모두 직교한다. \(A\)를 곱하면 회색 쌍은 \((3, 4)\)와 \((0, 5)\)가 되어 내적이 \(20\)이고 더 이상 수직이 아니다. 반면 \(Av_1\)과 \(Av_2\)는 수직을 유지하며 타원의 긴 축과 짧은 축이 된다. 그 길이 \(\lVert Av_1 \rVert = 3\sqrt{5}\), \(\lVert Av_2 \rVert = \sqrt{5}\)가 특이값이다. 직교성을 잃지 않고 옮겨지는 직교 쌍은 \(A^TA\)의 고유벡터라는 것이 정리의 그림이다.
증명. (1) 직교성. \(i \neq j\)이면 다음과 같다.
\[(Av_i)^T(Av_j) = v_i^T A^TA v_j = v_i^T (\lambda_j v_j) = \lambda_j (v_i^T v_j) = 0\]가운데의 \(A^TA\)는 그대로는 밖으로 꺼낼 수 없지만, \(v_j\)가 고유벡터이므로 스칼라 \(\lambda_j\)로 바뀌어 밖으로 나온다. 남은 \(v_i^T v_j\)는 \(v_i\), \(v_j\)가 정규직교이므로 0이다.
(2) 길이. 앞에서 본 대로 \(\lVert Av_i \rVert = \sigma_i\)다. 따라서 \(i \le r\)이면 \(Av_i \neq 0\)이고, \(i > r\)이면 \(\lambda_i = 0\)이므로 \(Av_i = 0\)이다.
(3) 열공간을 생성함. \(Av_1, \dots, Av_r\)는 모두 \(A\)의 열들의 선형결합이므로 \(\operatorname{Col} A\)에 속한다. 거꾸로 \(\operatorname{Col} A\)의 임의의 벡터 \(y = Ax\)를 보자. \(\{v_1, \dots, v_n\}\)은 \(\mathbb{R}^n\)의 정규직교기저이므로 \(x = c_1 v_1 + \cdots + c_n v_n\)으로 쓸 수 있다. 그러면 다음이 성립한다.
\[y = Ax = c_1 Av_1 + \cdots + c_r Av_r + c_{r+1} Av_{r+1} + \cdots + c_n Av_n = c_1 Av_1 + \cdots + c_r Av_r\]\(i > r\)인 항은 \(Av_i = 0\)이므로 모두 사라진다. 따라서 \(\operatorname{Col} A\)의 모든 벡터는 \(Av_1, \dots, Av_r\)의 선형결합이다.
(4) 결론. \(Av_1, \dots, Av_r\)는 영이 아닌 직교 벡터들이므로 선형독립이다(직교는 가장 강한 형태의 선형독립이다). 따라서 이들은 \(\operatorname{Col} A\)의 직교기저이고, \(\operatorname{rank} A = \dim \operatorname{Col} A = r\)이다. \(\blacksquare\)
결과적으로 직사각행렬 \(A\)의 랭크는 \(A^TA\)의 0이 아닌 고유값의 개수와 같다.
예제
\[A = \begin{bmatrix} 1 & -1 \\ -2 & 2 \\ 2 & -2 \end{bmatrix}, \qquad A^TA = \begin{bmatrix} 9 & -9 \\ -9 & 9 \end{bmatrix}\]\(A^TA\)의 고유값은 \(18\)과 \(0\)이고, 정규직교 고유벡터는 다음과 같다.
\[v_1 = \frac{1}{\sqrt{2}}\begin{bmatrix} 1 \\ -1 \end{bmatrix}, \qquad v_2 = \frac{1}{\sqrt{2}}\begin{bmatrix} 1 \\ 1 \end{bmatrix}\]특이값은 \(\sigma_1 = \sqrt{18} = 3\sqrt{2}\), \(\sigma_2 = 0\)이므로 \(r = 1\)이다. 실제로 다음과 같다.
\[Av_1 = \frac{1}{\sqrt{2}}\begin{bmatrix} 2 \\ -4 \\ 4 \end{bmatrix}, \quad \lVert Av_1 \rVert = \sqrt{\tfrac{36}{2}} = 3\sqrt{2}, \qquad Av_2 = 0\]\(A\)의 두 열은 서로 \(-1\)배 관계이므로 \(\operatorname{rank} A = 1\)이고, \(\operatorname{Col} A\)는 \(Av_1\), 즉 \((1, -2, 2)\) 방향의 직선이다. 정리와 일치한다.
랭크 1인 \(A\)의 작용. 왼쪽 \(\mathbb{R}^2\)의 단위원이 오른쪽 \(\mathbb{R}^3\)에서 \(\operatorname{Col} A\) 직선 위의 선분(보라)으로 납작해진다. \(v_2\) 방향(빨간 점선, \(\operatorname{Nul} A\))은 원점으로 간다.
왼쪽에서 \(v_1\)과 \(v_2\)는 단위원 위의 직교하는 두 방향이다. \(v_2 = \frac{1}{\sqrt{2}}(1, 1)\)이 생성하는 직선이 영공간이므로, 그 성분은 \(A\)를 거치며 사라진다. 그래서 단위원 위의 점 \(c_1 v_1 + c_2 v_2\)는 \(c_1 Av_1\)로만 보내지고, 원 전체가 \(-Av_1\)에서 \(Av_1\)까지의 선분이 된다. 선분의 반쪽 길이가 \(\sigma_1 = 3\sqrt{2}\)이고, 두 번째 축 방향으로는 전혀 늘어나지 않으므로 \(\sigma_2 = 0\)이다.
SVD의 구성
이 강의는 자막을 받을 수 없어, 앞 강의들의 흐름에 맞춰 강의 제목의 주제를 표준 내용으로 정리했다.
\(U\)의 열 만들기
44강의 정리로 \(\{Av_1, \dots, Av_r\}\)가 \(\operatorname{Col} A\)의 직교기저임을 알았다. 각각을 길이 \(\sigma_i\)로 나누어 정규화한다.
\[u_i = \frac{1}{\sigma_i} Av_i \quad (i = 1, \dots, r), \qquad \text{즉} \quad Av_i = \sigma_i u_i\]\(\{u_1, \dots, u_r\}\)는 \(\operatorname{Col} A\)의 정규직교기저다. \(r < m\)이면 여기에 벡터를 더하여 \(\mathbb{R}^m\)의 정규직교기저 \(\{u_1, \dots, u_m\}\)로 확장한다(예: 그람-슈미트). 추가한 벡터들은 \(\operatorname{Col} A\)에 직교한다.
\(A = U\Sigma V^T\)의 증명
\(U = [u_1 \ \cdots \ u_m]\), \(V = [v_1 \ \cdots \ v_n]\)으로 두고, \(\Sigma\)는 대각에 \(\sigma_1, \dots, \sigma_r\)를 두고 나머지는 0인 \(m \times n\) 행렬로 둔다. 열별로 비교하면 다음과 같다.
\[AV = [Av_1 \ \cdots \ Av_r \ \ 0 \ \cdots \ 0] = [\sigma_1 u_1 \ \cdots \ \sigma_r u_r \ \ 0 \ \cdots \ 0] = U\Sigma\]\(U\Sigma\)의 \(i\)번째 열은 \(U\)의 열들을 \(\Sigma\)의 \(i\)번째 열로 결합한 것이고, 그 열에서 영이 아닌 성분은 \(\sigma_i\)뿐이기 때문이다. \(V\)는 직교행렬이므로 \(V^{-1} = V^T\)이고, 오른쪽에 \(V^T\)를 곱하면 다음을 얻는다.
\[A = U \Sigma V^T\]이 구성은 어떤 \(m \times n\) 행렬에도 적용된다. 필요한 것은 대칭행렬 \(A^TA\)의 직교대각화뿐이고, 이는 스펙트럼 정리로 항상 보장된다. 그래서 SVD는 항상 존재한다.
용어로는 \(v_i\)를 오른쪽 특이벡터(right singular vector), \(u_i\)를 왼쪽 특이벡터(left singular vector) 라 한다.
예제 1: 랭크 1인 \(3 \times 2\) 행렬
44강의 \(A = \begin{bmatrix} 1 & -1 \\ -2 & 2 \\ 2 & -2 \end{bmatrix}\)를 이어서 분해한다. \(\sigma_1 = 3\sqrt{2}\)이므로 다음과 같다.
\[u_1 = \frac{1}{3\sqrt{2}} \cdot \frac{1}{\sqrt{2}}\begin{bmatrix} 2 \\ -4 \\ 4 \end{bmatrix} = \frac{1}{3}\begin{bmatrix} 1 \\ -2 \\ 2 \end{bmatrix}\]\(r = 1 < m = 3\)이므로 \(u_1\)에 직교하는 단위벡터 두 개를 더해야 한다. \(u_1 \cdot x = 0\), 즉 \(x_1 - 2x_2 + 2x_3 = 0\)의 해 중에서 서로 직교하는 것을 고른다.
\[u_2 = \frac{1}{\sqrt{5}}\begin{bmatrix} 2 \\ 1 \\ 0 \end{bmatrix}, \qquad u_3 = \frac{1}{\sqrt{45}}\begin{bmatrix} -2 \\ 4 \\ 5 \end{bmatrix}\](\(u_1 \cdot u_3 \propto -2 - 8 + 10 = 0\), \(u_2 \cdot u_3 \propto -4 + 4 = 0\)이다.) 따라서 다음과 같다.
\[A = \begin{bmatrix} 1/3 & 2/\sqrt{5} & -2/\sqrt{45} \\ -2/3 & 1/\sqrt{5} & 4/\sqrt{45} \\ 2/3 & 0 & 5/\sqrt{45} \end{bmatrix} \begin{bmatrix} 3\sqrt{2} & 0 \\ 0 & 0 \\ 0 & 0 \end{bmatrix} \begin{bmatrix} 1/\sqrt{2} & -1/\sqrt{2} \\ 1/\sqrt{2} & 1/\sqrt{2} \end{bmatrix}\]외적 형태로는 항이 하나뿐이다.
\[A = \sigma_1 u_1 v_1^T = 3\sqrt{2} \cdot \frac{1}{3}\begin{bmatrix} 1 \\ -2 \\ 2 \end{bmatrix} \cdot \frac{1}{\sqrt{2}}\begin{bmatrix} 1 & -1 \end{bmatrix} = \begin{bmatrix} 1 & -1 \\ -2 & 2 \\ 2 & -2 \end{bmatrix}\]예제 2: 기하학적 그림
\[A = \begin{bmatrix} 3 & 0 \\ 4 & 5 \end{bmatrix}, \qquad A^TA = \begin{bmatrix} 25 & 20 \\ 20 & 25 \end{bmatrix}\]\(A^TA\)의 고유값은 \(45\)와 \(5\)이고 고유벡터는 \(v_1 = \frac{1}{\sqrt{2}}(1, 1)\), \(v_2 = \frac{1}{\sqrt{2}}(1, -1)\)이다. 특이값은 \(\sigma_1 = 3\sqrt{5}\), \(\sigma_2 = \sqrt{5}\)다.
\[u_1 = \frac{Av_1}{\sigma_1} = \frac{1}{\sqrt{10}}\begin{bmatrix} 1 \\ 3 \end{bmatrix}, \qquad u_2 = \frac{Av_2}{\sigma_2} = \frac{1}{\sqrt{10}}\begin{bmatrix} 3 \\ -1 \end{bmatrix}\]\(u_1 \cdot u_2 = 0\)임을 확인할 수 있다. 외적의 합으로 쓰면 다음과 같다.
\[A = \frac{3}{2}\begin{bmatrix} 1 & 1 \\ 3 & 3 \end{bmatrix} + \frac{1}{2}\begin{bmatrix} 3 & -3 \\ -1 & 1 \end{bmatrix} = \begin{bmatrix} 3 & 0 \\ 4 & 5 \end{bmatrix}\]\(Ax = U\Sigma V^Tx\)는 고유값 분해 때처럼 세 단계로 읽을 수 있다. 차이는 첫 단계와 마지막 단계가 모두 회전(또는 반사)이라는 점이다.
- \(V^T\): 직교행렬이므로 길이와 각도를 보존한다. 직교하는 방향 \(v_1, v_2\)를 좌표축으로 돌린다.
- \(\Sigma\): 각 축 방향으로 \(\sigma_1, \sigma_2\)만큼 늘이거나 줄인다.
- \(U\): 다시 회전하여 좌표축을 \(u_1, u_2\) 방향으로 보낸다.
따라서 \(A\)는 단위원을, 장축과 단축 방향이 \(u_1\), \(u_2\)이고 반지름이 \(\sigma_1 = 3\sqrt{5}\), \(\sigma_2 = \sqrt{5}\)인 타원으로 보낸다. 가장 크게 늘어나는 입력 방향이 \(v_1\)이고, 그 늘어나는 비율이 \(\sigma_1\)이다.
\(A = U\Sigma V^T\)가 단위원에 작용하는 세 단계. \(V^T\)가 \(v_1, v_2\)를 좌표축으로 보내고, \(\Sigma\)가 축 방향으로 \(3\sqrt{5}\), \(\sqrt{5}\)배 늘이고, \(U\)가 축을 \(u_1, u_2\) 방향으로 보낸다. 검은 점은 \(e_1 = (1, 0)\)의 위치를 추적한 것이다.
첫 패널에서 파란 \(v_1\)과 빨간 \(v_2\)는 대각선 방향이다. \(V^T\)를 곱하면 원 자체는 그대로이고 \(v_1\)이 \(e_1\), \(v_2\)가 \(e_2\)로 옮겨진다. 이 예의 \(V\)는 행렬식이 \(-1\)이어서 회전이 아니라 반사이지만, 길이와 각도를 보존하는 점은 같다. 세 번째 패널에서 \(\Sigma\)는 가로로 \(3\sqrt{5} \approx 6.7\)배, 세로로 \(\sqrt{5} \approx 2.2\)배 늘여 축에 정렬된 타원을 만든다(셋째, 넷째 패널은 축척이 다르다). 마지막으로 \(U\)가 이 타원을 돌려 긴 축을 \(u_1\), 짧은 축을 \(u_2\) 방향에 놓는다. 검은 점은 \(e_1\)에서 출발해 \(A e_1 = (3, 4)\), 곧 \(A\)의 첫째 열에 도착한다.
\(U\)와 \(AA^T\), 그리고 네 가지 기본 부분공간
\(A = U\Sigma V^T\)이면 다음이 성립한다.
\[AA^T = U\Sigma V^T V \Sigma^T U^T = U (\Sigma\Sigma^T) U^T\]\(\Sigma\Sigma^T\)는 대각에 \(\sigma_i^2\)를 가진 \(m \times m\) 대각행렬이다. 따라서 \(U\)의 열은 \(AA^T\)의 고유벡터이고, 0이 아닌 고유값은 \(A^TA\)와 같은 \(\sigma_i^2\)다. 즉 33강에서 본 두 행렬 \(A^TA\)(항목 간 내적)와 \(AA^T\)(특징 간 내적)의 고유벡터가 각각 \(V\)와 \(U\)가 된다.
SVD는 네 가지 기본 부분공간의 정규직교기저를 한 번에 준다.
- \(\{u_1, \dots, u_r\}\): \(\operatorname{Col} A\)의 기저
- \(\{u_{r+1}, \dots, u_m\}\): \((\operatorname{Col} A)^\perp = \operatorname{Nul} A^T\)의 기저
- \(\{v_{r+1}, \dots, v_n\}\): \(\operatorname{Nul} A\)의 기저 (\(Av_i = 0\)이므로)
- \(\{v_1, \dots, v_r\}\): \((\operatorname{Nul} A)^\perp = \operatorname{Row} A\)의 기저
예제 1에서 \(v_2 = \frac{1}{\sqrt{2}}(1, 1)\)은 \(\operatorname{Nul} A\)를, \(u_2, u_3\)은 \(\operatorname{Nul} A^T\)를 생성한다.
축약된 SVD와 저랭크 근사
0인 특이값에 해당하는 부분을 모두 버리면 축약된 SVD(reduced SVD) 를 얻는다.
\[A = U_r D V_r^T = \sum_{i=1}^{r} \sigma_i u_i v_i^T, \qquad D = \operatorname{diag}(\sigma_1, \dots, \sigma_r)\]\(U_r\)은 \(m \times r\), \(V_r\)은 \(n \times r\)다. 특이값이 큰 순서로 정렬되어 있으므로, 앞의 \(k\)개 항만 남긴 다음 행렬은 \(A\)의 가장 중요한 성분만 담은 랭크 \(k\) 행렬이다.
\[A_k = \sum_{i=1}^{k} \sigma_i u_i v_i^T\]\(A_k\)는 랭크가 \(k\) 이하인 행렬 중 \(A\)에 가장 가까운 행렬이다(에카르트-영 정리, Eckart–Young theorem). 이 성질은 데이터 압축, 잡음 제거, 주성분 분석 같은 응용의 기반이 된다.
설명용으로 만든 \(48 \times 64\) 흑백 이미지 행렬 \(A\)(랭크 48)의 특이값과 저랭크 근사 \(A_1, A_2, A_5, A_{15}\). 괄호 안은 프로베니우스 노름으로 잰 상대 오차 \(\lVert A - A_k \rVert / \lVert A \rVert\)다.
왼쪽 막대그래프에서 \(\sigma_1 \approx 31.1\)이 압도적으로 크고, \(\sigma_2 \approx 7.0\)부터 빠르게 작아진다. \(A_1 = \sigma_1 u_1 v_1^T\)는 한 열 벡터와 한 행 벡터의 곱이므로 모든 행이 같은 모양의 상수배다. 그래서 원과 직사각형의 위치만 흐릿한 띠로 나타난다. 항을 더할수록 모양이 살아나서 \(A_5\)에서 원과 직사각형이 뚜렷해지고, \(A_{15}\)에서는 대각선 띠까지 대부분 복원된다. 저장해야 하는 수는 \(A\)의 \(48 \times 64 = 3072\)개에 비해 \(A_{15}\)는 \(15 \times (48 + 64 + 1) = 1695\)개다. 특이값이 빨리 줄어드는 행렬일수록 적은 항으로 잘 근사된다.
정리
- SVD \(A = U\Sigma V^T\)는 임의의 \(m \times n\) 행렬에 대해 존재한다. \(U\)(\(m \times m\))와 \(V\)(\(n \times n\))는 직교행렬이고, \(\Sigma\)는 \(A\)와 같은 크기의 대각 형태 행렬이다.
- 고유값 분해는 하나의 \(V\)와 그 역행렬로 양쪽을 맞춰야 하지만, SVD는 \(U\)와 \(V\)를 따로 고를 수 있어 자유도가 크고 항상 존재한다.
- \(A^TA\)는 대칭이고 고유값이 모두 0 이상(양의 준정부호)이다. 특이값은 그 고유값의 제곱근 \(\sigma_i = \sqrt{\lambda_i} = \lVert Av_i \rVert\)다.
- \(A^TA\)의 정규직교 고유벡터를 \(A\)로 옮긴 \(Av_1, \dots, Av_r\)는 서로 직교하며 \(\operatorname{Col} A\)의 기저가 된다. 따라서 \(\operatorname{rank} A\)는 0이 아닌 특이값의 개수다.
- \(u_i = Av_i / \sigma_i\)로 \(U\)의 열을 만들고 \(\mathbb{R}^m\)의 정규직교기저로 확장하면 \(AV = U\Sigma\), 즉 \(A = U\Sigma V^T\)를 얻는다. \(U\)의 열은 \(AA^T\)의 고유벡터다.
- \(A = \sum_i \sigma_i u_i v_i^T\)는 랭크 1 조각들의 가중합이며, 기하학적으로는 회전, 축별 크기 조정, 회전의 합성이다. 앞의 \(k\)개 항은 \(A\)의 최적 랭크 \(k\) 근사다.