3 Inseok Kong Schedule

Linear Algebra 9: Singular Value Decomposition

특이값 분해(SVD)의 형태와 고유값 분해와의 비교, AᵀA로부터 정의되는 특이값과 열공간의 직교기저, 그리고 A = UΣVᵀ를 실제로 구성하는 방법을 다룬다.

SVD의 형태와 고유값 분해와의 비교

▶ 43강

정의와 크기

고유값 분해(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\)가 된다.

특이값과 열공간의 직교기저

▶ 44강

\(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\)로 바뀐다.

Orthogonal e1, e2 lose orthogonality under A, while v1, v2 stay orthogonal 아래 예제 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)\) 방향의 직선이다. 정리와 일치한다.

A rank-1 3x2 matrix maps the unit circle of R^2 onto a segment of a line in R^3 랭크 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의 구성

▶ 45강

이 강의는 자막을 받을 수 없어, 앞 강의들의 흐름에 맞춰 강의 제목의 주제를 표준 내용으로 정리했다.

\(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\)는 고유값 분해 때처럼 세 단계로 읽을 수 있다. 차이는 첫 단계와 마지막 단계가 모두 회전(또는 반사)이라는 점이다.

  1. \(V^T\): 직교행렬이므로 길이와 각도를 보존한다. 직교하는 방향 \(v_1, v_2\)를 좌표축으로 돌린다.
  2. \(\Sigma\): 각 축 방향으로 \(\sigma_1, \sigma_2\)만큼 늘이거나 줄인다.
  3. \(U\): 다시 회전하여 좌표축을 \(u_1, u_2\) 방향으로 보낸다.

따라서 \(A\)는 단위원을, 장축과 단축 방향이 \(u_1\), \(u_2\)이고 반지름이 \(\sigma_1 = 3\sqrt{5}\), \(\sigma_2 = \sqrt{5}\)인 타원으로 보낸다. 가장 크게 늘어나는 입력 방향이 \(v_1\)이고, 그 늘어나는 비율이 \(\sigma_1\)이다.

The unit circle under V transpose, then Sigma, then U, ending as the ellipse of A \(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). 이 성질은 데이터 압축, 잡음 제거, 주성분 분석 같은 응용의 기반이 된다.

Singular values of a 48 by 64 image matrix and its rank-1, 2, 5 and 15 approximations 설명용으로 만든 \(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\) 근사다.