특이값분해
행렬의 특이값 분해(SVD)는 선형대수학에서 핵심적인 행렬 분해 방법이다. 이것은 정사각 행렬뿐만 아니라 모든 행렬에 적용될 수 있고, 항상 존재하기 때문에 “선형대수학의 기본 정리”(Strang, 1993)라고 불려왔다. 게다가, 뒤에서 살펴보겠지만 선형 사상 $\Phi: V \to W$ 를 표현하는 행렬 $A$ 의 SVD는 이 두 벡터 공간 사이의 기하학적 구조의 변화를 정량화해 준다. SVD의 수학적 배경에 대한 더 깊은 개요를 위해서는 Kalman(1996)과 Roy and Banerjee(2014)의 연구를 추천한다.
$\to$ “두 벡터 공간 사이의 기하학적 구조의 변화를 정량화해 준다.”의 의미가 뭔지 생각해보자. “기하학적 구조의 변화”란 가령, 벡터 공간 $V$ 에 단위 구(반지름이 1)가 행렬 $A$ 라는 변환을 통해 $W$ 로 보내졌을 때 대부분의 선형 변환은 이 구를 찌그리뜨리거나 늘려서 타원체로 만든다. 이것이 기하학적 구조의 변화이다. 그럼 “정량화”는 무엇일까. SVD( $A = U \Sigma V^\top$ )의 각 행렬은 이 변화를 정확한 수치로 보여준다. 4.4절에 $A=P^{-1}DP$ 를 그림 4.7로 묘사한 것과 유사하다. $V$ (Right Singular Vectors, 우특이벡터)는 입력 공간에서 어느 방향으로 힘을 가할 것인지, $\Sigma$ (Singular Values, 특이값)는 그 방향으로 얼마나 늘리거나 줄일 것인지, $U$ (Left Singular Vectors, 좌특이벡터)는 그렇게 변형된 구가 출력 공간( $W$ )에서 어느 방향을 향해 놓여있는지를 보여준다. 이는 그림 4.8에도 적절히 묘사되었다.
정리 4.22 (SVD 정리). $A \in \mathbb{R}^{m \times n}$ 을 랭크가 $r \in [0, \min(m, n)]$ 인 직사각형 행렬이라고 하자. $A$ 의 SVD는 다음과 같은 형태의 분해이다.
여기서 $U \in \mathbb{R}^{m \times m}$ 는 열벡터 $u_i (i=1, \dots, m)$ 를 가진 직교 행렬이고, $V \in \mathbb{R}^{n \times n}$ 는 열벡터 $v_j (j=1, \dots, n)$ 를 가진 직교 행렬이다. 또한, $\Sigma$ 는 $m \times n$ 행렬로, $\Sigma_{ii} = \sigma_i \ge 0$ 이고 $i \neq j$ 일 때 $\Sigma_{ij} = 0$ 이다.
$\quad$ $\Sigma$ 의 대각 성분들 $\sigma_i (i = 1, \dots, r)$ 은 특이값(singular values)이라고 불리고, $u_i$ 는 좌-특이벡터(left-singular vectors), $v_j$ 는 우-특이벡터(right-singular vectors)라고 불린다. 관례에 따라 특이값들은 순서대로 정렬된다. 즉, $\sigma_1 \ge \sigma_2 \ge \dots \ge \sigma_r \ge 0$ .
$\quad$ 특이값 행렬 $\Sigma$ 는 유일하지만(unique), 약간의 주의가 필요하다. $\Sigma \in \mathbb{R}^{m \times n}$ 이 직사각형이라는 점을 관찰하라. 특히, $\Sigma$ 는 $A$ 와 같은 크기이다. 이것은 $\Sigma$ 가 특이값들을 포함하는 대각 부분행렬(diagonal submatrix)을 가지며 추가적인 0 패딩(zero padding)이 필요함을 의미한다. 구체적으로, 만약 $m > n$ 이면(행이 더 많으면), 행렬 $\Sigma$ 는 $n$ 행까지는 대각 구조를 가지고 그 아래 $n+1$ 부터 $m$ 까지는 0으로 된 행 벡터들로 구성된다.
만약 $m < n$ 이면(열이 더 많으면), 행렬 $\Sigma$ 는 $m$ 열까지는 대각 구조를 가지고 $m+1$ 부터 $n$ 까지는 0으로 된 열들로 구성된다.
참고. SVD는 임의의 행렬 $A \in \mathbb{R}^{m \times n}$ 에 대해서 존재한다.
4.5.1 특이값 분해의 기하학적 직관
SVD는 변환 행렬 $A$ 를 서술하는 기하학적 직관을 제공한다. 다음 내용에서, 우리는 SVD를 기저(bases)에 대해 수행되는 순차적인 선형 변환으로 논의할 것이다. 예제 4.12에서 우리는 SVD의 변환 행렬들을 $\mathbb{R}^2$ 의 벡터 집합에 적용할 것이며, 이는 각 변환의 효과를 더 명확하게 시각화할 수 있게 해준다.
$\quad$ 행렬의 SVD는 대응하는 선형 사상(2.7.1절 상기) $\Phi: \mathbb{R}^n \to \mathbb{R}^m$ 을 세 가지 연산으로 분해한 것으로 해석될 수 있다(그림 4.8 참조).
그림 4.8 (행렬 $A \in \mathbb{R}^{3 \times 2}$ 에 대한 SVD의 직관). 순차적인 변환으로서의 SVD.
- 좌측 상단에서 좌측 하단으로 ( $V^\top$ ): $\mathbb{R}^2$ 내에서 기저 변경을 수행한다.
- 좌측 하단에서 우측 하단으로 ( $\Sigma$ ): 스케일링을 하고 $\mathbb{R}^2$ 에서 $\mathbb{R}^3$ 로 매핑한다. 우측 하단의 타원(ellipse)은 $\mathbb{R}^3$ 공간 안에 살고 있다. 세 번째 차원은 타원형 디스크의 표면에 수직이다(즉, 평면 밖으로 튀어나온 축은 값이 0임).
- 우측 하단에서 우측 상단으로 ( $U$ ): $\mathbb{R}^3$ 내에서 기저 변경을 수행한다.
SVD의 직관은 피상적으로는 우리의 고유값 분해의 직관(그림 4.7 참조)과 유사한 구조를 따른다. 대략적으로 말해서, SVD는 $V^\top$ 를 통해 기저 변경(basis change)을 수행하고, 뒤이어 특이값 행렬 $\Sigma$ 를 통해 스케일링(scaling) 및 차원 확장(augmentation) 또는 축소(reduction)를 수행한다. 마지막으로, $U$ 를 통해 두 번째 기저 변경을 수행한다. SVD는 많은 중요한 세부 사항과 주의점을 수반하므로, 우리는 우리의 직관을 더 자세히 검토할 것이다.
$\quad$ 선형 사상 $\Phi: \mathbb{R}^n \to \mathbb{R}^m$ 의 변환 행렬이 표준 기저 $B$ ( $\mathbb{R}^n$ 의 기저)와 $C$ ( $\mathbb{R}^m$ 의 기저)에 대해 주어졌다고 가정하자. 또한 $\mathbb{R}^n$ 의 두 번째 기저 $\tilde{B}$ 와 $\mathbb{R}^m$ 의 두 번째 기저 $\tilde{C}$ 를 가정하자. 그러면 다음과 같다.
- 행렬 $V$ 는 정의역 $\mathbb{R}^n$ 에서 $\tilde{B}$ 로부터 표준 기저 $B$ 로의 기저 변경을 수행한다. $V^\top = V^{-1}$ 는 $B$ 에서 $\tilde{B}$ 로의 기저 변경을 수행한다. (그림 4.8의 좌측 상단에 있는 빨간색과 주황색 벡터 $v_1, v_2$ 가 $\tilde{B}$ 를 나타냄). 이제 빨간색과 주황색 벡터는 그림 4.8의 좌측 하단에서 표준 기저(canonical basis)와 정렬된다.
- 좌표계가 $\tilde{B}$ 로 변경된 상태에서, $\Sigma$ 는 새로운 좌표들을 특이값 $\sigma_i$ 만큼 스케일링한다(그리고 차원을 추가하거나 삭제한다). 즉, $\Sigma$ 는 $\tilde{B}$ 와 $\tilde{C}$ 에 대한 $\Phi$ 의 변환 행렬이다. 이것은 그림 4.8의 우측 하단에서 빨간색과 주황색 벡터가 $e_1-e_2$ 평면에 놓여 있으면서 늘어났고, 제3의 차원에 임베딩된 것으로 표현된다.
- $U$ 는 공역(codomain) $\mathbb{R}^m$ 에서 $\tilde{C}$ 로부터 $\mathbb{R}^m$ 의 표준 기저로의 기저 변경을 수행한다. 이것은 그림 4.8의 우측 상단에서 $e_1-e_2$ 평면 밖으로 빨간색과 주황색 벡터가 회전하는 것으로 표현된다.
SVD는 정의역과 공역 모두에서의 기저 변경을 표현한다. 이것은 동일한 벡터 공간 내에서 작동하여 동일한 기저 변경이 적용되었다가 다시 되돌려지는 고유값 분해와 대조적이다. SVD를 특별하게 만드는 것은 이 서로 다른 두 기저가 특이값 행렬 $\Sigma$ 에 의해 동시에 연결된다는 점이다.
예제 4.12 (벡터와 SVD)
원점을 중심으로 하는 $2 \times 2$ 크기의 상자 안에 들어맞는 벡터들의 정사각형 격자 $\mathcal{X} \in \mathbb{R}^2$ 의 매핑을 고려하자. 표준 기저를 사용하여, 우리는 이 벡터들을 다음 행렬을 이용해 매핑한다.
우리는 격자로 배열된 벡터 집합 $\mathcal{X}$ (색칠된 점들; 그림 4.9의 좌측 상단 패널 참조)에서 시작한다.
그림 4.9 (SVD와 벡터의 매핑). 벡터들의 매핑(원반으로 표현됨). 패널들은 그림 4.8과 동일한 반시계 방향 구조를 따른다.
그런 다음 우리는 $V^\top \in \mathbb{R}^{2 \times 2}$ 를 적용하여 $\mathcal{X}$ 를 회전시킨다. 회전된 벡터들은 그림 4.9의 좌측 하단 패널에 나타나 있다. 이제 우리는 특이값 행렬 $\Sigma$ 를 사용하여 이 벡터들을 공역 $\mathbb{R}^3$ 로 매핑한다(그림 4.9의 우측 하단 패널 참조). 모든 벡터가 $x_1-x_2$ 평면에 놓여 있음에 주목하라. 세 번째 좌표는 항상 0이다. $x_1-x_2$ 평면의 벡터들은 특이값들에 의해 늘어났다.( $\to$ $x_1-x_2$ 에서 ‘ $-$ ‘는 연산자의 역할이 아닌 $x_1$ 과 $x_2$ 를 연결하는 기호로써 사용된다.)
$\quad$ $A$ 에 의한 벡터 $\mathcal{X}$ 의 공역 $\mathbb{R}^3$ 로의 직접적인 매핑은 $U \Sigma V^\top$ 에 의한 변환과 동일하다. 여기서 $U$ 는 매핑된 벡터들이 더 이상 $x_1-x_2$ 평면에 제한되지 않도록 공역 $\mathbb{R}^3$ 내에서 회전을 수행한다; 그들은 그림 4.9의 우측 상단 패널과 같이 여전히 하나의 평면 위에 존재한다.
4.5.2 특이값 분해의 구성
우리는 다음으로 왜 SVD가 존재하는지 논의하고 그것을 계산하는 방법을 상세히 보일 것이다. 일반적인 행렬의 SVD는 정사각 행렬의 고유값 분해와 몇 가지 유사점을 공유한다.
참고. 대칭 양의 정부호(SPD) 행렬의 고유값 분해를 비교해보자.
그리고 이에 대응하는 SVD는 다음과 같다.
만약 우리가 다음과 같이 설정한다면,
우리는 SPD 행렬의 SVD가 그들의 고유값 분해와 같다는 것을 알 수 있다.
$\quad$ 다음 내용에서, 우리는 왜 정리 4.22(SVD 정리)가 성립하는지, 그리고 SVD가 어떻게 구성되는지 탐구할 것이다. $A \in \mathbb{R}^{m \times n}$ 의 SVD를 계산하는 것은 공역 $\mathbb{R}^m$ 과 정의역 $\mathbb{R}^n$ 의 두 정규 직교 기저 집합 $U = (u_1, \dots, u_m)$ 과 $V = (v_1, \dots, v_n)$ 을 각각 찾는 것과 동등하다. 이 순서화된 기저들로부터, 우리는 행렬 $U$ 와 $V$ 를 구성할 것이다.
$\quad$ 우리의 계획은 우-특이벡터들의 정규 직교 집합 $v_1, \dots, v_n \in \mathbb{R}^n$ 을 구성하는 것으로 시작하는 것이다. 그 후 우리는 좌-특이벡터들의 정규 직교 집합 $u_1, \dots, u_m \in \mathbb{R}^m$ 을 구성할 것이다. 그 후, 우리는 이 둘을 연결할 것이며, $v_i$ 의 직교성(orthogonality)이 $A$ 의 변환 하에서도 보존될 것을 요구할 것이다. 이것은 중요한데, 왜냐하면 우리는 이미지들 $Av_i$ 가 직교 벡터들의 집합을 형성한다는 것을 알기 때문이다. 우리는 이 이미지들을 스칼라 인자로 정규화(크기를 1로 만듦)할 것이며, 이 스칼라 인자들이 결국 특이값들이 될 것이다.
$\quad$ 우-특이벡터들을 구성하는 것부터 시작하자. 스펙트럴 정리(정리 4.15)는 대칭 행렬의 고유벡터들이 정규 직교 기저(ONB)를 형성하며, 따라서 대각화 가능하다는 것을 말해준다. 게다가, 정리 4.14로부터 우리는 임의의 직사각형 행렬 $A \in \mathbb{R}^{m \times n}$ 으로부터 대칭이고 양의 준정부호(positive semidefinite)인 행렬 $A^\top A \in \mathbb{R}^{n \times n}$ 을 항상 구성할 수 있다. 따라서 우리는 $A^\top A$ 를 항상 대각화할 수 있고 다음을 얻는다.
여기서 $P$ 는 정규 직교 고유 기저로 구성된 직교 행렬이다. $\lambda_i \ge 0$ 은 $A^\top A$ 의 고유값들이다. $A$ 의 SVD가 존재한다고 가정하고 식 (4.64)를 (4.71)에 대입해보자. 이것은 다음을 산출한다.
여기서 $U, V$ 는 직교 행렬이다. 따라서 $U^\top U = I$ 이므로 우리는 다음을 얻는다.
이제 (4.71)과 (4.73)을 비교해보면, 우리는 다음을 식별할 수 있다.
따라서, $P$ 를 구성하는 $A^\top A$ 의 고유벡터들이 바로 $A$ 의 우-특이벡터 $V$ 이다(식 4.74 참조). 또한 $A^\top A$ 의 고유값들은 $\Sigma$ 의 특이값들의 제곱이다(식 4.75 참조).
$\quad$ 좌-특이벡터 $U$ 를 얻기 위해, 우리는 유사한 절차를 따른다. 우리는 (이전의 $A^\top A \in \mathbb{R}^{n \times n}$ 대신) 대칭 행렬 $AA^\top \in \mathbb{R}^{m \times m}$ 의 SVD를 계산하는 것으로 시작한다. $A$ 의 SVD는 다음을 산출한다.
스펙트럴 정리는 $AA^\top = SDS^\top$ 가 대각화 가능하며 우리가 $S$ 에 모인 $AA^\top$ 의 고유벡터들로 이루어진 ONB를 찾을 수 있음을 말해준다. $AA^\top$ 의 정규 직교 고유벡터들은 좌-특이벡터 $U$ 이며 SVD의 공역(codomain)에서 정규 직교 기저를 형성한다.
$\quad$ 여기서 행렬 $\Sigma$ 의 구조에 대한 질문이 있을 수 있다. $AA^\top$ 와 $A^\top A$ 는 동일한 0이 아닌 고유값들을 가지므로(106페이지 참조), 두 경우 모두 SVD에서 $\Sigma$ 행렬의 0이 아닌 성분들은 동일해야 한다.
$\to$ 왜 $AA^\top$ 와 $A^\top A$ 는 항상 동일한 고유값을 가지는가? $A^\top A$ 의 0이 아닌 고유값을 $\lambda$ , 고유벡터를 $v$ 라고 가정해보자.
양변의 왼쪽에 $A$ 를 곱하면:
결합 법칙을 적용하여 괄호를 다시 묶으면:
식 (1)과 (3)을 보면 $A^\top A$ 의 고유값이 $\lambda$ 이면, $AA^\top$ 의 고유값도 똑같이 $\lambda$ 가 된다(단, 이때 (입력)고유벡터는 $v$ 가 아니라 $Av$ 가 된다).
$\quad$ 마지막 단계는 지금까지 다룬 모든 부분들을 연결하는 것이다. 우리는 $V$ 에 우-특이벡터들의 정규 직교 집합을 가지고 있다. SVD 구성을 완료하기 위해, 우리는 그들을 정규 직교 벡터 $U$ 와 연결한다. 이 목표에 도달하기 위해, 우리는 $A$ 에 의한 $v_i$ 의 상(image, $Av_i$ ) 또한 직교해야 한다는 사실을 이용한다. 우리는 3.4절의 결과를 사용하여 이를 보일 수 있다. 우리는 $i \neq j$ 일 때 $Av_i$ 와 $Av_j$ 사이의 내적이 반드시 0이어야 함을 요구한다. 임의의 두 직교 고유벡터 $v_i, v_j (i \neq j)$ 에 대해 다음이 성립한다.( $\to$ $v_j$ 는 행렬 $(A^\top A)$ 의 고유벡터이기 때문에 $(A^\top A) v_j = \lambda_j v_j$ 가 성립한다.)
$m \ge r$ 인 경우에 대해, $\set{Av_1, \dots, Av_r}$ 은 $\mathbb{R}^m$ 의 $r$ 차원 부분공간의 기저가 된다.
$\quad$ SVD 구성을 완료하기 위해, 우리는 정규 직교인 좌-특이벡터들이 필요하다. 우리는 우-특이벡터들의 상 $Av_i$ 를 정규화하여 다음을 얻는다.
여기서 마지막 등호는 (4.75)와 (4.76b)로부터 얻어졌으며, 이는 $AA^\top$ 의 고유값들이 $\sigma_i^2 = \lambda_i$ 와 같음을 보여준다.
$\to$ SVD의 정의상 $A = U \Sigma V^\top$ 이므로, $AV = U\Sigma$ 가 성립해야 한다. 즉, 입력 벡터 $v_i$ 를 $A$ 에 통과시킨 결과( $Av_i$ )는 출력 벡터 $u_i$ 와 방향이 같아야 한다( $Av_i = \sigma_i u_i$ ). 이때 $Av_i$ 는 길이가 1이 아니므로 자기 자신의 길이( $\Vert Av_i\Vert = \sigma_i$ )로 나누는 정규화가 필요하다.
$\to$ 좌-특이벡터와 우-특이벡터는 항상 단위 벡터이다. 이는 행렬 분해( $A = U \Sigma V^\top$ )에서 각 행렬의 기능을 생각해보면 된다. $\Sigma$ 는 크기를 조절하는 scaler이며 $V^\top$ 와 $U$ 는 각각 입력 공간과 출력 공간에서의 ‘회전’ 변환이다. 만약 좌/우-특이벡터가 단위 벡터가 아닐 경우 이 변환(A)를 해석하기 어렵다.
$\quad$ 따라서, 우리가 우-특이벡터 $v_i$ 로 알고 있는 $A^\top A$ 의 고유벡터들과, $A$ 에 의한 그것들의 정규화된 이미지인 좌-특이벡터 $u_i$ 는, 특이값 행렬 $\Sigma$ 를 통해 연결되는 두 개의 자기 일관적인(self-consistent) 정규 직교 기저(ONB)를 형성한다.
$\to$ “self-consistent한 ONB”의 의미를 생각해보자. 일반적으로 정의역 $\mathbb{R}^n$ 의 기저와 공역 $\mathbb{R}^m$ 의 기저는 서로 아무런 상관없이 정의할 수 있다. 하지만 SVD에서의 $V$ (입력 기저)와 $U$ (출력 기저)는 $\Sigma$ (특이값)를 매개로 하여 연결되어 있다. 가령 $v_i$ 를 정하면 $u_i$ 는 $Av_i$ 방향으로 고정되며, $u_i$ 를 정하면 $v_i$ 는 $A^{\top}u_i$ 방향으로 고정된다. 즉, 어떤 벡터( $v_i$ )가 변환( $A$ )이 적용된 상( $Av_i$ )이 다른 벡터( $u_i$ )의 위치이며, 그 크기 비율은 $\sigma_i$ 로 일정하다는 관계가 모든 $i$ 에 대해 성립하므로, 두 기저 집합은 서로 맞물려 돌아간다는 의미에서 self-consistent라고 표현한다.
$\quad$ 식 (4.78)을 재배열하여 우리는 특이값 방정식(singular value equation)을 얻는다.
이 방정식은 고유값 방정식 (4.25)와 매우 닮았지만, 좌변과 우변의 벡터가 서로 다르다( $v_i$ vs $u_i$ ).
$\quad$ $n < m$ 인 경우, (4.79)는 오직 $i \le n$ 에 대해서만 성립하며, (4.79)는 $i > n$ 인 $u_i$ 에 대해서는 아무것도 말해주지 않는다. 그러나 우리는 구성에 의해 그것들이 정규 직교임을 안다. 반대로 $m < n$ 인 경우, (4.79)는 오직 $i \le m$ 에 대해서만 성립한다. $i > m$ 에 대해서 우리는 $Av_i = 0$ 을 얻으며, 우리는 여전히 $v_i$ 들이 정규 직교 집합을 형성함을 안다. 이것은 SVD가 $A$ 의 커널(영공간), 즉 $Ax = 0$ 인 벡터 $x$ 들의 집합에 대한 정규 직교 기저 또한 제공함을 의미한다(2.7.3절 참조).
$\to$ 입력 공간의 차원이 출력 공간의 차원보다 작은 경우( $n < m$ ) 입력 기저 n개로 출력 공간 $\mathbb{R}^m$ 전체를 span하지 못한다. 따라서 치역(Image, $Av$ 가 도달하는 곳)은 $\mathbb{R}^m$ 의 일부분인 $n$ 차원 부분공간에 불과하며, 이는 $u_1, \dots, u_n$ 에 의해 생성된다. 반면, 남은 $u_{n+1}, \dots, u_m$ 은 치역에 수직인 공간(치역의 직교 여공간)을 형성하며, 이 공간은 입력 벡터 $v_i$ 로는 도달할 수 없다(이를 ‘좌영공간’이 부른다.). 이 좌영공간에 대응되는 특이값은 0이다.
$\quad$ $v_i$ 들을 열로 하여 $V$ 를 만들고 $u_i$ 들을 열로 하여 $U$ 를 만들어 연결하면 다음을 얻는다.
여기서 $\Sigma$ 는 $A$ 와 동일한 차원을 가지며 행 $1, \dots, r$ 에 대해 대각 구조를 가진다. 따라서 양변의 오른쪽에 $V^\top$ 를 곱하면 $A = U \Sigma V^\top$ 가 되며, 이것이 $A$ 의 SVD이다.
예제 4.13 (SVD 계산하기)
다음 행렬의 특이값 분해를 구해보자.
SVD는 우리가 우-특이벡터 $v_j$ , 특이값 $\sigma_k$ , 그리고 좌-특이벡터 $u_i$ 를 계산할 것을 요구한다.
$\quad$ 1단계: $A^\top A$ 의 고유 기저(eigenbasis)로서의 우-특이벡터
$\quad$ 우리는 다음을 계산하는 것으로 시작한다.
$\quad$ 우리는 $A^\top A$ 의 고유값 분해를 통해 특이값들과 우-특이벡터들 $v_j$ 를 계산한다. 그 결과는 다음과 같다.
그리고 우리는 $P$ 의 열들을 가져와 우-특이벡터를 얻는다.
$\quad$ 2단계: 특이값 행렬
$\quad$ 특이값 $\sigma_i$ 는 $A^\top A$ 의 고유값들의 제곱근이므로, 우리는 $D$ 로부터 바로 그것들을 얻는다. $\text{rank}(A) = 2$ 이므로, 0이 아닌 특이값은 두 개뿐이다: $\sigma_1 = \sqrt{6}$ 그리고 $\sigma_2 = 1$ . 특이값 행렬은 반드시 $A$ 와 같은 크기여야 하므로, 우리는 다음을 얻는다.
$\quad$ 3단계: 우-특이벡터들의 정규화된 이미지로서의 좌-특이벡터
$\quad$ 우리는 우-특이벡터들의 $A$ 에 의한 이미지( $Av_i$ )를 계산하고 그것들을 대응하는 특이값으로 나누어 정규화함으로써 좌-특이벡터들을 찾는다. 우리는 다음을 얻는다.
참고. 컴퓨터상에서 여기에 묘사된 접근법( $A^\top A$ 를 이용하는 방법)은 나쁜 수치적 거동(poor numerical behavior)을 가지며, $A$ 의 SVD는 일반적으로 $A^\top A$ 의 고유값 분해에 의존하지 않고 계산된다.
4.5.3 고유값 분해 vs. 특이값 분해
고유값 분해 $A = PDP^{-1}$ 와 SVD $A = U\Sigma V^\top$ 를 고려하고 지난 절들의 핵심 요소들을 검토해보자.
- SVD는 어떤 행렬 $\mathbb{R}^{m \times n}$ 에 대해서도 항상 존재한다. 고유값 분해는 오직 정사각 행렬 $\mathbb{R}^{n \times n}$ 에 대해서만 정의되며, 우리가 $\mathbb{R}^n$ 의 고유벡터 기저를 찾을 수 있을 때만 존재한다.( $\to$ 전단 변환과 같은 결함 행렬은 고유 벡터의 수가 모자라 분해할 수 없다. SVD는 이 변환을 제곱하여 대칭행렬로 만들어 분해하므로 무조건 분해 가능하다.)
- 고유값 분해 행렬 $P$ 의 벡터들은 반드시 직교하지는 않는다. 즉, 기저 변경이 단순한 회전과 스케일링이 아니다. 반면, SVD의 행렬 $U$ 와 $V$ 에 있는 벡터들은 정규 직교하므로, 그들은 회전을 나타낸다.
- 고유값 분해와 SVD는 모두 세 가지 선형 사상의 합성이다.
- 정의역(domain)에서의 기저 변경
- 각 새로운 기저 벡터의 독립적인 스케일링 및 정의역에서 공역(codomain)으로의 매핑
- 공역에서의 기저 변경
- 고유값 분해와 SVD의 주요한 차이점은 SVD에서는 정의역과 공역이 서로 다른 차원의 벡터 공간일 수 있다는 점이다.
- SVD에서, 좌-특이벡터 행렬 $U$ 와 우-특이벡터 행렬 $V$ 는 일반적으로 서로의 역행렬이 아니다(그들은 서로 다른 벡터 공간에서 기저 변경을 수행한다). 고유값 분해에서, 기저 변경 행렬 $P$ 와 $P^{-1}$ 는 서로의 역행렬이다.
- SVD에서, 대각 행렬 $\Sigma$ 의 성분들은 모두 실수이며 음수가 아니다. 이것은 고유값 분해의 대각 행렬에 대해서는 일반적으로 성립하지 않는다.
- SVD와 고유값 분해는 그들의 사영(projections)을 통해 밀접하게 연관되어 있다.
- $A$ 의 좌-특이벡터들은 $AA^\top$ 의 고유벡터들이다.
- $A$ 의 우-특이벡터들은 $A^\top A$ 의 고유벡터들이다.
- $A$ 의 0이 아닌 특이값들은 $AA^\top$ 와 $A^\top A$ 의 0이 아닌 고유값들의 제곱근이다.
- 대칭 행렬 $A \in \mathbb{R}^{n \times n}$ 에 대해서, 고유값 분해와 SVD는 동일하다. 이는 스펙트럴 정리 4.15로부터 따른다.
$\to$ 반사 변환과 같이 공간을 뒤집는 변환은 고유값 분해하면 음수인 고유값이 존재한다. SVD에서는 이러한 ‘방향(부호) 정보’가 특이값 $\Sigma$ 가 아닌 직교 행렬 $U$ 또는 $V$ 의 벡터 방향으로 흡수된다. 또한, 수학적으로 특이값은 $\sigma_i = \Vert A v_i \Vert$ 로 정의된다. 여기서 $\Vert \cdot \Vert$ 는 벡터의 길이(Norm)를 의미하므로, 정의상 특이값은 음수가 될 수 없다. 즉, $\Sigma$ 의 대각 성분은 모두 0 이상의 실수이다.
$\to$ 이를 벡터 공간의 관점에서 보면 차이는 더 명확하다. 고유값 분해( $Ax = \lambda x$ )는 입력과 출력이 같은 공간에 존재하며 두 벡터가 평행하기 때문에 방향(부호) 비교가 가능하다. 하지만 SVD( $Av = \sigma u$ )는 입력 $v$ 와 출력 $u$ 가 서로 다른 차원의 공간에 존재할 수 있다. 서로 다른 공간에 있는 두 벡터의 방향이 같은지 다른지 논하는 것은 수학적으로 정의되지 않으므로, $\Sigma$ 에는 방향 정보를 담을 수 없다. 설령 같은 차원이라 해도 입력 기저( $V$ )와 출력 기저( $U$ )를 서로 다르게 설정하여 방향 정보를 처리하므로, $\Sigma$ 는 오직 ‘크기 변화량’만을 나타낸다.
예제 4.14 (영화 평점과 소비자에서의 구조 찾기)
SVD에 대한 실용적인 해석을 더하기 위해 사람들과 그들이 선호하는 영화에 대한 데이터를 분석해보자. 세 명의 관람객(Ali, Beatrix, Chandra)이 네 편의 서로 다른 영화(Star Wars, Blade Runner, Amelie, Delicatessen)를 평가하는 상황을 고려하자. 그들의 평점은 0(최악)에서 5(최고) 사이의 값이며, 그림 4.10과 같이 데이터 행렬 $A \in \mathbb{R}^{4 \times 3}$ 으로 인코딩된다. 각 행은 영화를 나타내고 각 열은 사용자를 나타낸다. 따라서 영화 평점의 열벡터들은 각각의 관람객 $x_{\text{Ali}}, x_{\text{Beatrix}}, x_{\text{Chandra}}$ 이다.
$\quad$ SVD를 사용하여 $A$ 를 분해하는 것은 사람들이 영화를 평가하는 방식의 관계를 포착할 방법을 제공하며, 특히 어떤 사람이 어떤 영화를 좋아하는지를 연결하는 구조가 있을 때 더욱 그렇다. 데이터 행렬 $A$ 에 SVD를 적용하는 것은 다음과 같은 몇 가지 가정을 만든다.
1. 모든 관람객은 동일한 선형 사상을 사용하여 일관되게 영화를 평가한다.
2. 평점에 오류나 노이즈가 없다.
3. 우리는 좌-특이벡터 $u_i$ 를 “전형적인(stereotypical) 영화”로, 우-특이벡터 $v_j$ 를 “전형적인 관람객”으로 해석한다.
그러면 우리는 어떤 관람객의 특정 영화 선호도도 $v_j$ 들의 선형 결합으로 표현될 수 있다는 가정을 하게 된다. 유사하게, 어떤 영화의 호감도(like-ability)도 $u_i$ 들의 선형 결합으로 표현될 수 있다. 따라서, SVD의 정의역(domain)에 있는 벡터는 “전형적인 관람객들의 공간”에 있는 관람객으로 해석될 수 있고, 공역(codomain)에 있는 벡터는 이에 상응하여 “전형적인 영화들의 공간”에 있는 영화로 해석될 수 있다.
우리 영화-사용자 행렬의 SVD를 살펴보자. 첫 번째 좌-특이벡터 $u_1$ 은 두 공상과학(SF) 영화에 대해 큰 절댓값을 가지며 큰 첫 번째 특이값을 가진다(그림 4.10의 빨간색 음영). 따라서, 이것은 특정 영화 세트(SF 테마)를 가진 사용자 유형을 그룹화한다. 유사하게, 첫 번째 우-특이벡터 $v_1$ 은 SF 영화에 높은 점수를 준 Ali와 Beatrix에 대해 큰 절댓값을 보여준다(그림 4.10의 녹색 음영). 이것은 $v_1$ 이 “SF 애호가”라는 개념을 반영함을 시사한다.
$\quad$ 유사하게, $u_2$ 는 “프랑스 예술 영화” 테마를 포착하는 것으로 보이며, $v_2$ 는 Chandra가 그러한 영화들의 이상적인 애호가에 가깝다는 것을 나타낸다. 이상적인 SF 애호가는 순수주의자여서 오직 SF 영화만 좋아하므로, SF 애호가 $v_1$ 은 SF 테마가 아닌 모든 것에 0점을 준다. 이 논리는 특이값 행렬 $\Sigma$ 의 대각 하부구조(substructure)에 의해 암시된다. 그러므로 특정 영화는 그것이 전형적인 영화들로 어떻게 분해(선형적으로)되는지에 의해 표현된다. 마찬가지로, 사람은 그들이 영화 테마들로 어떻게 분해(선형 결합을 통해)되는지에 의해 표현된다.
$\quad$ 문헌마다 사용되는 버전이 다르므로 SVD 용어와 관례를 간단히 논의하는 것은 가치가 있다. 이러한 차이점이 혼란스러울 수 있지만, 수학적 본질은 변하지 않는다.
- Full SVD: 표기법과 추상화의 편의를 위해, 우리는 좌-특이벡터와 우-특이벡터 행렬이 모두 정사각 행렬이고 특이값 행렬은 정사가 아닌(직사각형) SVD 표기법을 사용한다. (4.64)에서의 우리의 정의는 때때로 Full SVD라고 불린다.
- Reduced SVD: 어떤 저자들은 SVD를 조금 다르게 정의하며 정사각 특이값 행렬에 초점을 맞춘다. $A \in \mathbb{R}^{m \times n}$ 이고 $m \ge n$ 인 경우에 대해 다음과 같이 쓴다.
때때로 이 공식은 Reduced SVD (예: Datta (2010)) 또는 그냥 the SVD (예: Press et al. (2007))라고 불린다. 이 대안적인 포맷은 단순히 행렬이 구성되는 방식만 바꿀 뿐 SVD의 수학적 구조는 그대로 둔다. 이 대안적 표기법의 편의성은 고유값 분해에서처럼 $\Sigma$ 가 대각 행렬(정사각)이라는 점이다. - Truncated SVD: 4.6절에서 우리는 SVD를 이용한 행렬 근사 기법을 배울 것인데, 이는 Truncated SVD라고도 불린다. - Rank- $r$ SVD: 랭크가 $r$ 인 행렬 $A$ 의 SVD를 정의할 때, $U$ 는 $m \times r$ , $\Sigma$ 는 $r \times r$ 대각 행렬, $V$ 는 $r \times n$ 행렬이 되도록 할 수 있다. 이 구성은 우리의 정의와 매우 유사하며, 대각 행렬 $\Sigma$ 가 대각선상에 오직 0이 아닌 성분들만 갖도록 보장한다. SVD가 $m \ge n$ 인 행렬에만 적용된다는 제약은 실제로는 불필요하다. $m < n$ 일 때, SVD 분해는 행보다 열이 더 많은 $\Sigma$ 를 산출할 것이며, 결과적으로 특이값 $\sigma\_{m+1}, \dots, \sigma\_n$ 은 0이 된다. $\quad$ SVD는 최소 자승 문제(least-squares problems)부터 연립 일차 방정식 풀이까지 머신러닝의 다양한 응용 분야에서 사용된다. 이러한 응용들은 행렬의 랭크와의 관계, 그리고 주어진 행렬을 더 낮은 랭크의 행렬로 근사하는 능력 등 SVD의 다양한 중요 성질들을 활용한다. 행렬을 그 SVD로 대체하는 것은 종종 수치적 반올림 오차(rounding errors)에 대해 계산을 더 견고(robust)하게 만드는 이점을 가진다. 다음 절에서 살펴볼 것처럼, SVD가 행렬을 더 간단한 행렬들로 원칙에 입각해 근사하는 능력은 차원 축소(dimensionality reduction)와 토픽 모델링(topic modeling)에서부터 데이터 압축 및 클러스터링에 이르기까지 다양한 머신러닝 응용을 가능하게 한다.