[선형대수] 특이값 분해 (SVD)
특이값 분해 (SVD - Singular Value Decomposition)
SVD는 EVD와 달리 정사각 행렬이 아니어도 적용할 수 있으며, 임의의 행렬 $A \in \mathbb{R}^{m \times n}$를 다음 세 행렬의 곱으로 분해할 수 있다.
\[A=U\Sigma V^\top \tag{1}\]$U$: 각 열이 $A$의 Left Singular Vector들로 구성된 직교 행렬
\[U=\begin{bmatrix}|&|&&|\\\mathbf{u}_1&\mathbf{u}_2&\cdots&\mathbf{u}_m\\|&|&&|\end{bmatrix} \in\mathbb{R}^{m\times m}\]$V\in\mathbb{R}^{n\times n}$: 각 열이 $A$의 Right Singular Vector들로 구성된 직교 행렬
\[V=\begin{bmatrix}|&|&&|\\\mathbf{v}_1&\mathbf{v}_2&\cdots&\mathbf{v}_n\\|&|&&|\end{bmatrix} \in\mathbb{R}^{n\times n}\]$\Sigma$: 주대각선에 $A$의 특이값들이 크기순으로 나열된 직사각 대각 행렬
\[\Sigma=\begin{bmatrix}\sigma_1&0&\cdots&0\\0&\sigma_2&\cdots&0\\\vdots&\vdots&\ddots&\vdots\\0&0&\cdots&\sigma_n\\0&0&\cdots&0\end{bmatrix} \in\mathbb{R}^{m\times n} \;,\quad\text{where }m>n\] \[\Sigma=\begin{bmatrix}\sigma_1&0&\cdots&0&\cdots&0\\0&\sigma_2&\cdots&0&\cdots&0\\\vdots&\vdots&\ddots&\vdots&\vdots&\vdots\\0&0&\cdots&\sigma_m&\cdots&0\end{bmatrix} \in\mathbb{R}^{m\times n} \;,\quad\text{where }m<n\]이때 특이값 $\sigma_i$는 서로 중복될 수 있으며, $\text{rank}(A)=r$이면 $r$개의 특이값만 양수이고 나머지 특이값은 $0$이다.
\[\sigma_1\geq \cdots \geq \sigma_r>0, \quad,\quad \sigma_{r+1}=\cdots=\sigma_{\min(m,n)}=0\]
SVD의 기하학적 의미
SVD는 복잡해 보이는 선형 변환 $A$를 입력 공간의 회전, 축별 스케일링, 출력 공간의 회전으로 나누어 해석하게 해준다.
왜 이런 해석이 가능한지 살펴보자.
행렬 $A\in\mathbb{R}^{m\times n}$의 SVD가 $A=U\Sigma V^\top$로 주어질 때, 벡터 $\mathbf{x} \in \mathbb{R}^n$에 대한 변환은 다음과 같이 표현할 수 있다.
\[A\mathbf{x}=U\Sigma V^\top \mathbf{x}\]이때 $\mathbf{x}$가 원래 표현되어 있는 좌표계의 기저를 $\lbrace\mathbf{e}_1,\dots,\mathbf{e}_n\rbrace$이라고 하자.
위 식은 오른쪽부터 차례대로 다음의 세 단계를 거치는 과정으로 이해할 수 있다.
$V^\top\mathbf{x}$: 원래 좌표계에서 표현된 벡터 $\mathbf{x}$를 Right Singular Vector들을 기저로 하는 좌표계에서의 좌표로 변환한다.
\[\mathbf{x}=c_1\mathbf{v}_1+c_2\mathbf{v}_1+\cdots+c_n\mathbf{v}_n\]$\Sigma(V^\top\mathbf{x})$: Right Singular Vector 좌표계에서 표현된 각 성분을, 대응되는 특이값 $\sigma_i$만큼 독립적으로 Scaling한다.
\[\sigma_1(c_1\mathbf{v}_1)+\sigma_2(c_2\mathbf{v}_2)+\cdots+\sigma_n(c_n\mathbf{v}_n)\]$U(\Sigma V^\top\mathbf{x})$: Scaling된 Left Singular Vector 좌표를 Right Singular Vector를 기저로 하는 좌표계로 표현한다.
\[\mathbf{y}=y_1\mathbf{u}_1+y_2\mathbf{u}_2+\cdots+y_n\mathbf{u}_n\]
즉, SVD는 행렬의 선형 변환 과정을 회전 → 스케일링 → 회전 3단계로 분해하여여 나타낸 것이다.
예시
예를 들어, 행렬 $A$가 다음과 같이 SVD가 된다고 가정해 보자.
\[A=U\Sigma V^\top= \begin{bmatrix}0&-1\\1&0\end{bmatrix} \begin{bmatrix}2&0\\0&0.5\end{bmatrix} \begin{bmatrix}1&0\\0&-1\end{bmatrix}^\top\]그리고 유클리드 좌표계에 존재하는 벡터 $\mathbf{x}=2\mathbf{i}+2\mathbf{j}$에 선형 변환 $A$를 적용한다고 해보자.
$\mathbf{y}=A\mathbf{x}$를 다음과 같이 세 단계로 표현할 수 있다.
벡터 $\mathbf{x}$를 Right Singular Vector 좌표계로 표현
\[V^\top\mathbf{x} =\begin{bmatrix}1&0\\0&-1\end{bmatrix} \begin{bmatrix}2\\2\end{bmatrix} =\begin{bmatrix}2\\-2\end{bmatrix}\]따라서 Right Singular Vector 좌표계에서 $\mathbf{x}=2\mathbf{v}_1-2\mathbf{v}_2$로 표현된다.
각 성분을 특이값 $\sigma_1=2,\sigma_2=0.5$만큼 Scaling
\[\Sigma(V^\top\mathbf{x}) =\begin{bmatrix}2&0\\0&0.5\end{bmatrix} \begin{bmatrix}2\\-2\end{bmatrix} =\begin{bmatrix}4\\-1\end{bmatrix}\]Scaling 후의 벡터는 $4\mathbf{v}_1-\mathbf{v}_2$가 된다.
Left Singular Vector 좌표계로 표현
\[U(\Sigma V^\top\mathbf{x}) =\begin{bmatrix}0&-1\\1&0\end{bmatrix} \begin{bmatrix}4\\-1\end{bmatrix} =\begin{bmatrix}1\\4\end{bmatrix}\]따라서 Left Singular Vector 좌표계에서 $\mathbf{y}=\mathbf{u}_1+4\mathbf{u}_2$로 표현된다.
즉, $A$에 의한 선형 변환의 결과는 다음과 같다.
\[\mathbf{y}=\mathbf{u}_1+4\mathbf{u}_2=\begin{bmatrix}4\\-1\end{bmatrix}\]EVD를 통해 SVD를 계산하는 방법
행렬의 고유값과 고유벡터는 특성 방정식 또는 수치적 알고리즘을 통해 구할 수 있다.
따라서 대각화 가능한 행렬에 대해서는 EVD를 계산할 수 있다.
그렇다면 SVD는 어떻게 계산할 수 있을까?
SVD는 임의의 행렬 $A$에 대해, $A^\top A$ 또는 $AA^\top$의 EVD를 이용해 구할 수 있다.
구체적으로 행렬 $A$의 특이값과 특이벡터는, 행렬 $A^\top A$와 $AA^\top$의 고유값과 고유벡터와 다음의 관계를 갖는다.
행렬 $A^\top A$와 $AA^\top$의 고유값은 행렬 $A$의 특이값의 제곱과 같다.
\[\lambda_i=\sigma_i^2 \tag{2}\]- 행렬 $A^\top A$의 고유벡터들은 $A$의 Right Singular Vector 행렬 $V$를 구성한다.
- 행렬 $AA^\top$의 고유벡터들은 $A$의 Left Singular Vector 행렬 $U$를 구성한다.
증명
행렬 $A\in\mathbb{R}^{m\times n}$가 $A=U\Sigma V^\top$로 SVD된다고 해보자.
또한 $S_1=A^\top A$ , $S_2=AA^\top$라고 하자.행렬 $S_1=A^\top A$ 전개
$U^\top U=I$이므로, 다음과 같이 전개할 수 있다.
\[S_1=A^\top A=(U\Sigma V^\top)^\top(U\Sigma V^\top)=V\Sigma^\top (U^\top U)\Sigma V^\top=V(\Sigma^\top\Sigma) V^\top\] \[S_1=V(\Sigma^\top\Sigma) V^\top=V\begin{bmatrix}\sigma_1^2&\cdots&0\\\vdots&\ddots&\vdots\\0&\cdots&\sigma_n^2\end{bmatrix}V^\top\]이때 $S_1$은 대칭 행렬이므로, $S_1=P_1\Lambda_1 P_1^\top$ 형태로 EVD가 가능하다.
즉, 아래의 두 관계가 성립하게 된다.
행렬 $A^\top A$의 고유값은 행렬 $A$의 특이값의 제곱과 같다.
\[\Lambda_1=\Sigma^\top\Sigma\quad\to\quad\begin{bmatrix}\lambda_1&\cdots&0\\\vdots&\ddots&\vdots\\0&\cdots&\lambda_n\end{bmatrix}=\begin{bmatrix}\sigma_1^2&\cdots&0\\\vdots&\ddots&\vdots\\0&\cdots&\sigma_n^2\end{bmatrix}\]행렬 $A^\top A$의 고유벡터들은 $A$의 Right Singular Vector 행렬 $V$를 구성한다.
\[P_1=V\quad\to\quad\begin{bmatrix}\mathbf{p}_1&\cdots&\mathbf{p}_n\end{bmatrix}=\begin{bmatrix}\mathbf{v}_1&\cdots&\mathbf{v}_n\end{bmatrix}\]행렬 $S_2=AA^\top$ 전개
$U^\top U=I$이므로, 다음과 같이 전개할 수 있다.
\[S_2=AA^\top=(U\Sigma V^\top)(U\Sigma V^\top)^\top=U\Sigma (V^\top V)\Sigma^\top U^\top=U(\Sigma\Sigma^\top)^\top\] \[S_2=U(\Sigma\Sigma^\top) U^\top=U\begin{bmatrix}\sigma_1^2&\cdots&0\\\vdots&\ddots&\vdots\\0&\cdots&\sigma_m^2\end{bmatrix}U^\top\]이때 $S_2$는 대칭 행렬이므로, $S_2=V_2\Lambda_2 V_2^\top$ 형태로 EVD가 가능하다.
즉, 아래의 두 관계가 성립하게 된다.
행렬 $AA^\top$의 고유값은 행렬 $A$의 특이값의 제곱과 같다.
\[\Lambda_2=\Sigma\Sigma^\top\quad\to\quad\begin{bmatrix}\lambda_1&\cdots&0\\\vdots&\ddots&\vdots\\0&\cdots&\lambda_n\end{bmatrix}=\begin{bmatrix}\sigma_1^2&\cdots&0\\\vdots&\ddots&\vdots\\0&\cdots&\sigma_n^2\end{bmatrix}\]행렬 $AA^\top$의 고유벡터들은 $A$의 Left Singular Vector 행렬 $U$를 구성한다.
\[P_2=V\quad\to\quad\begin{bmatrix}\mathbf{p}_1&\cdots&\mathbf{p}_n\end{bmatrix}=\begin{bmatrix}\mathbf{u}_1&\cdots&\mathbf{u}_n\end{bmatrix}\]
위의 성질에 따르면, SVD를 계산하기 위해 행렬 $A^\top A$와 $AA^\top$ 각각에 대해 두 번의 EVD를 수행해야 한다.
하지만 아래의 공식을 사용하면, 하나의 행렬에 대해서만 EVD를 계산해도 SVD를 계산할 수 있다.
여기서 $\mathbf{v}_i$는 $V$의 $i$번째 열벡터, $\mathbf{u}_i$는 $U$의 $i$번째 열벡터를 의미한다.
$A^\top A$에 대해 EVD를 먼저 수행한 경우 $\to$ $V$를 구한 상태
\[\mathbf{u}_i=\frac{1}{\sigma_i}A\mathbf{v}_i \;,\quad\text{where }\sigma_i\not=0\]
식 (3)을 변형한 아래의 공식을 이용해 $U$를 구함$AA^\top$에 대해 EVD를 먼저 수행한 경우 $\to$ $U$를 구한 상태
\[\mathbf{v}_i^\top=\frac{1}{\sigma_i}\mathbf{u}_i^\top A \;,\quad\text{where }\sigma_i\not=0\]
식 (3)을 변형한 아래의 공식을 이용해 $V$를 구함
$\sigma_i=0$인 경우에는 $A\mathbf{v}_i=\mathbf{0}$을 풀면 된다.
식 (3) 유도
\[A=U\Sigma V^\top~\to~AV=U\Sigma\]$AV$ 행렬은 다음과 같이 표현할 수 있다.
\[AV=\begin{bmatrix}|&&|\\A\mathbf{v}_1&\cdots&A\mathbf{v}_n\\|&&|\end{bmatrix}\in\mathbb{R}^{m\times n}\]$U\Sigma$ 행렬은 다음과 같이 표현할 수 있다.
\[U\Sigma=\begin{bmatrix}|&&|\\\sigma_1\mathbf{u}_1&\cdots&\sigma_n\mathbf{u}_n\\|&&|\end{bmatrix}\in\mathbb{R}^{m\times n}\]따라서, $A\mathbf{v}_i=\mathbf{u}_i\sigma_i$이다.
다시 말하자면, 행렬 $A$의 SVD는 행렬 $A^\top A$와 $AA^\top$에 대해 EVD를 수행해서 계산할 수 있다.
Example: EVD를 통해 SVD 계산
\[A=\begin{bmatrix}1&5&0\\5&1&0\end{bmatrix}\]$AA^\top$에 대한 EVD를 수행하여, $A$에 대한 SVD를 계산하는 과정은 다음과 같다.
\[AA^\top=\begin{bmatrix}26&10\\10&26\end{bmatrix}\]
- 대칭 행렬 $AA^\top$를 만든다.
\[\mathbf{v}_1^\top=\frac{1}{6}\begin{bmatrix}\frac{1}{\sqrt2}&\frac{1}{\sqrt2}\end{bmatrix}\begin{bmatrix}1&5&0\\5&1&0\end{bmatrix}=\begin{bmatrix}\frac{1}{\sqrt2}&\frac{1}{\sqrt2}&0\end{bmatrix}\] \[\mathbf{v}_2^\top=\frac{1}{4}\begin{bmatrix}-\frac{1}{\sqrt2}&\frac{1}{\sqrt2}\end{bmatrix}\begin{bmatrix}1&5&0\\5&1&0\end{bmatrix}=\begin{bmatrix}\frac{1}{\sqrt2}&-\frac{1}{\sqrt2}&0\end{bmatrix}\]
특성 방정식을 풀어, 고유값과 고유벡터를 구한다.
\[\lambda_1=36~,~\lambda_2=16\quad,\quad\mathbf{x}_1=\begin{bmatrix}\frac{1}{\sqrt2}\\\frac{1}{\sqrt2}\end{bmatrix}~,~\mathbf{x}_2=\begin{bmatrix}-\frac{1}{\sqrt2}\\\frac{1}{\sqrt2}\end{bmatrix}\]고유값을 이용해 특이값을 계산하고, 크기가 큰 순서대로 정렬하여 주대각선에 배치해서 행렬 $\Sigma$를 만든다.
\[\sigma_1=\sqrt{\lambda_1}=6~,~\sigma_2=\sqrt{\lambda_2}=4\] \[\Sigma=\begin{bmatrix}6&0&0\\0&4&0\end{bmatrix}\]Left Singular Vector 행렬 $U$를 만든다.
\[U=\begin{bmatrix}\frac{1}{\sqrt2}&-\frac{1}{\sqrt2}\\\frac{1}{\sqrt2}&\frac{1}{\sqrt2}\end{bmatrix}\]$\mathbf{v}_i^\top=\frac{1}{\sigma_i}\mathbf{u}_i^\top A$ 공식을 이용해 $\mathbf{v}_i$를 계산한다.
\[A\begin{bmatrix}x\\y\\z\end{bmatrix}=\begin{bmatrix}x+5y\\5x+y\end{bmatrix}=\begin{bmatrix}0\\0\end{bmatrix}\quad\to\quad\mathbf{v}_3=\begin{bmatrix}0\\0\\1\end{bmatrix}\]
- $\mathbf{v}_3$는 $A\mathbf{v}_3=\mathbf{0}$을 풀어서 구한다.
\[V=\begin{bmatrix}\frac{1}{\sqrt2}&\frac{1}{\sqrt2}&0\\\frac{1}{\sqrt2}&-\frac{1}{\sqrt2}&0\\0&0&1\end{bmatrix}\]
- Right Singular Vector 행렬 $V$를 만든다.
최종적인 SVD 결과는 다음과 같다.
\[\begin{bmatrix}1&5&0\\5&1&0\end{bmatrix}=\begin{bmatrix}\frac{1}{\sqrt2}&-\frac{1}{\sqrt2}\\\frac{1}{\sqrt2}&\frac{1}{\sqrt2}\end{bmatrix}\begin{bmatrix}6&0&0\\0&4&0\end{bmatrix}\begin{bmatrix}\frac{1}{\sqrt2}&\frac{1}{\sqrt2}&0\\\frac{1}{\sqrt2}&-\frac{1}{\sqrt2}&0\\0&0&1\end{bmatrix}\]
EVD와 SVD의 수치적 안정성 (Numerical Stability)
우리가 실제 다루는 데이터는 대부분 직사각행렬이다.
임의의 행렬 $A\in\mathbb{R}^{m\times n}$에 대해 PCA를 수행할 때, 일반적으로 공분산 행렬 $A^\top A$에 대한 EVD를 사용한다.
수학적으로 $A$에 대한 SVD와 동치이지만, 수치적으로는 SVD가 훨씬 더 안정적이다.
EVD의 불안정성
EVD에서 $A^\top A$를 형성하는 순간, 조건수가 제곱으로 증폭된다.
\[\vphantom{\Big(} \kappa_2(A^\top A) = \kappa_2(A)^2\]만약 원본 행렬 $A$의 조건수가 크다면, $A^\top A$는 훨씬 더 불안정해진다는 뜻이다.
결국 불안정한 행렬 $A^\top A$에 대해 EVD를 수행하면, Round-off 오차가 증폭되어 고유값과 고유벡터가 부정확하게 계산될 위험이 크다.
Round-off 오차는 실수를 유한한 비트 수로 근사하여 표현할 때 생기는 오차이다.
이는 컴퓨터의 부동소수점 (floating-point) 연산은 유한한 자릿수만 저장할 수 있고, 계산 결과가 그 범위를 넘어가면 가장 가까운 수로 반올림을 하기 때문에 발생한다.
예를 들어 아래 연산에서 실제 결과는 $0.3$이지만, 부동소수점 표현에서는 이를 정확히 표현할 수 없어 근사값으로 저장된다.
\[0.1+0.2=0.30000000000000004\]따라서 반복적인 연산을 거치면 round-off 오차가 매우 커질 수 있다.
SVD의 안정성
반면, SVD는 원본 행렬 $A$에 대해 바로 SVD를 수행하기 때문에, 조건수 제곱 효과가 발생하지 않아 수치적으로 더 안정적이다.
\[\vphantom{\Big(}A=U\Sigma V^\top\]위에서는 $AA^\top$와 $A^\top A$를 이용해 SVD를 수행했지만, 실제로는 이러한 행렬을 직접 구성하지 않고 SVD를 수행하는 알고리즘이 존재한다.
조건수 (Condition Number)
조건수는 입력에 생긴 작은 오차가 출력에 얼마나 크게 증폭되는지를 수치적으로 나타내는 민감도 지표이다.
값이 클수록 불안정 (ill-conditioned)하고, 값이 작을수록 안정 (well-conditioned)하다고 한다.
\[\kappa_2(A)=\lVert A\rVert_2\lVert A^{-1}\rVert_2 =\frac{\sigma_{\max}(A)}{\sigma_{\min}(A)} \tag{4}\]행렬의 조건수가 크다는 것은 해당 행렬의 변환이 한 쪽의 방향은 크게 늘리고 다른 쪽의 방향은 크게 눌렀다는 뜻이다.
이런 경우, 작은 축 방향 (분산이 약한 방향)의 신호들은 값이 작아져 노이즈와 구분이 어려워지고 수치적 안정성이 떨어지게 된다.
