SVD (특이값 분해)

수학

by Simple Runner 2018. 11. 18. 18:38

특이값 분해(SVD, Singular Value Decomposition)를 선형대수학(Linear Algebra)의 꽃(Highlight)이라고 부른다고 한다. 왜 그런지 알아보자. 아래 설명을 이해하기 위해서는 먼저 다음 사항을 먼저 알고 있어야 한다.

[1] 직교행렬(Orthogonal Matrix)

벡터가 서로 직교(Orthogonal)한다고 하면 내적이 영이 된다. u와 v가 nx1인 벡터라고 할 때, 다음 수식을 만족하면 직교한다고 한다.

$\mathbf{u^Tv}=0$

n차원 공간에는 최대 n개의 nx1인 서로 직교인 단위벡터(Unit Vector)가 존재하는데, 이 벡터을 이용하여 행렬을 만들면 직교행렬(Q)이 된다.

$\mathbf{Q = (u_1, u_2, \cdots, u_n)}$

직교행렬은 역행렬(Inverse Matrix)과 전치행렬(Transposed Matrix)이 같다. 전치행렬은 행과 열을 바꾸는 것이어서 쉽게 계산이 가능하다.

$\mathbf{Q^TQ}=\mathbf{QQ^T}=\mathbf{I}$

[2] 영공간(Null Space)

행렬 A 영공간(Null Space)은 다음을 만족하는 모든 해의 집합니다. 커널(Kernel)이라고도 불림.

$\mathbf{Ax}=\mathbf{0}$

예를 들어 A가 2차원 행렬이고 a11만 1이고 다른 원소는 0이며 x=(x,y)라고 하면, Ax = 0을 만족하는 해는 x=0, y는 임의의 값이다. 따라서 null(A)는 2차원 평면 내에서 x=0인 공간, 즉 y축이 된다.

[3] 고유값 분해 (Eigen Decomposition)

nxn 행렬 A는 아래와 같이 고유값 분해할 수 있다.

$\mathbf{A_{nn}}=\mathbf{S \Lambda S^{-1}}$

여기서 $\mathbf{\Lambda}$ 는 고유값(Eigen Value) $\mathbf{\delta_i}$ 를 대각 원소로 갖는 대각행렬이며, $\mathbf{S}$ 는 고유벡터(Eigen Vector)로 구성된 행렬이다.

#Why? (선형 연립방정식)

선형대수학의 기본이라 할 수 있는 선형 연립방정식을 푸는 것이 수학의 오래된 과제이다. 이것을 행렬과 벡터로 단순화 하여 나타내면 다음과 같다.

$\mathbf{Ax}=\mathbf{b}$

인덱스를 활용해 나타내면 $a_{mn} x_n = b_m$

A, x, b를 상세히 나타내 보면 아래와 같다.

$\mathbf{A} = \begin{pmatrix} a_{11} & a_{12} & a_{13} & \cdots & a_{1n}\\ a_{21} & a_{22} & a_{23} & \cdots & a_{2n}\\ \vdots & \vdots & \vdots& \ddots & \vdots \\ a_{m1} & a_{m2} & a_{m3} & \cdots & a_{mn} \end{pmatrix}$

$\mathbf{x}=\begin{pmatrix} x_1\\ x_2\\ \vdots \\ x_n \end{pmatrix}$

$\mathbf{b}=\begin{pmatrix} b_1\\ b_2\\ \vdots \\ b_m \end{pmatrix}$

위의 연립 방정식을 풀 때, 다음 3가지 경우가 존재한다.

해가 1개 존재하는 경우: 독립적인 방정식의 개수와 미지수가 같음 (A가 정방행렬(m = n)이고 역행렬이 존재)

따라서 역행렬을 구하면 쉽게 해를 구할 수 있지만, 시스템의 사이즈(n)가 커지면 역행렬을 구하는 것도 쉽지 않다. 가우스 소거법(Gauss Elimination), LU분해(LU Decomposition) 등의 방법이 있지만, 경우에 따라서 불안정해서 해가 구해지지 않는 경우가 있다.
해가 여러 개 존재하는 경우: 독립적인(Independent) 방정식의 개수가 미지수보다 적음 (A is underconstrained)
해가 존재하지 않는 경우: 독립적인 방정식의 개수가 미지수보다 많음 (A is overconstrained)
해가 존재하지 않지만 아래 수식을 만족하는 x를 찾고 싶을 때가 있다.

$\min {\left \|\mathbf{ Ax-b} \right \|}$

위 세가지 경우 별로 적용할 수 있는 이론이 있겠지만, 일반적으로 사용할 수 있는 방법론이 없을까?

#What? (Singular Value Decomposition)

특이값(Singular Value)을 수학적으로 정의해 놓은 사이트가 많이 있는데, 용어가 어려워 이해하기가 쉽지 않다. 일반 행렬에서 특이값은 고유값(Eigen Value)의 절대값이고, 특이벡터는 고유벡터이다. (선형변환 및 고유값, 고유벡터에 대한 설명은 다음을 참고바람)

A라는 행렬을 다음과 같이 만들고자 하는 것이 SVD (Singular Value Decomposition)이다. 왜 그렇게 하는지는 나중에 이해하게 된다.

$\mathbf{A}_{mn}=\mathbf{U}_{mm}\times \mathbf{\Sigma }_{mn}\times\mathbf{V^T}_{nn}$

여기서 U와 V는 직교행렬(Orthogonal Matrix)이고, $\mathbf{\Sigma }_{mn}$ 는 대각행렬(Rectangular Diagonal Matrix)이다. 이 행렬의 주대각선의 원소 중 영이 아닌 것의 개수를 r이라고 하면 r <= min(m,n) 이다. 그리고 이 원소의 절대값이 큰 것들부터 순서대로 앞쪽으로 배열했다고 하자.

위와 같이 나타내면 다음의 성질을 가진다.

$rank(\mathbf{A})= rank(\mathbf{\Sigma }) = r$
행렬 U의 r+1번째부터 m번째 행은 행렬 A의 영공간(Null Space)이다 (어떤 값이어도 수식에 영향을 미치지 않음, 즉 없어도 됨)
행렬 V의 r+1번째부터 n번째 행은 행렬 A의 영공간(Null Space)이다

그리고 행렬 U, V를 다음과 같이 행렬 벡터들(u는 m차원, v는 n차원)의 결합으로 생각하면,

$\mathbf{U}=(\mathbf{u_1}, \mathbf{u_2}, \cdots, \mathbf{u_m})$

$\mathbf{V}=(\mathbf{v_1}, \mathbf{v_2}, \cdots, \mathbf{v_n})$

행렬 A를 다음과 같이 단순화하여 나타낼 수 있다는 것이다.

$\mathbf{A}=\sigma_1 \mathbf{u_1 v_1^T} + \sigma_2 \mathbf{u_2 v_2^T} + \cdots + \sigma_r \mathbf{u_r v_r^T}$

여기서 $\sigma_i$ 는 대각행렬 $\mathbf{\Sigma}$ 의 i번째 대각 원소이다.

여기서 SVD의 의미를 다시 한번 생각해 보자.

$\mathbf{A}_{mn} \mathbf{x}_{n} = \mathbf{b }_{m}$

위의 수식은 n차원의 데이터(점) x를 선형 변환(A)하면 m차원의 데이터(점) b가 된다는 것이다. 즉 n차원 데이터를 m차원으로 변환하는 것이 핵심이다. 이러한 변환하는 방법을 3가지의 단순(?) 변환으로 나눈 것이 SVD이다.

n차원 내에서의 직교 변환 (길이를 바꾸지지 않고, 방향 등만 변환하는 것):
$\mathbf{V^T}_{nn}$
n차원에서 m차원으로의 변환 (각 차원의 길이는 바꿀 수 있음, 실제 의미있는 차원은 r임):
$\mathbf{\Sigma}_{mn}$
m차원 내에서의 직교 변환:
$\mathbf{U}_{mm}$

$\mathbf{U}_{mm}\times (\mathbf{\Sigma }_{mn} \times (\mathbf{V^T}_{nn} \times \mathbf{x}_{n})) = \mathbf{b }_{m}$

#How? (분해 방법)

그렇다면 문제는 행렬 A를 위와 같이 3가지 행렬의 곱으로 어떻게 나타낼 수 있느냐이다.

행렬의 고유값 분해를 활용해 보자. 고유값 분해는 정방행렬(Square Matrix, nxn)에서만 정의되기 때문에 직사각행렬(mxn)인 A에 바로 적용할 수는 없다. 행렬 A를 정방행렬로 만드는 방법은 두가지가 있다.

$\mathbf{A}_{mn}\times\mathbf{A^T}_{nm}=(\mathbf{AA^T})_{mm}$

$\mathbf{A^T}_{nm}\times \mathbf{A}_{mn}=(\mathbf{A^TA})_{nn}$

이제 위 두 개의 정방행렬을 각각 고유값 분해하여 다음과 같이 된다고 가정하자.

$\mathbf{AA^T} = \mathbf{U D U^{T}}$

$\mathbf{A^TA} = \mathbf{V D' V^{T}}$

위의 두 식에서 D와 D' 행렬은 순서는 다를 수 있지만 대각의 영이 아닌 원소는 서로 같다고 한다. 확인해 보자. 첫번째 식에 A를 SVD했던 수식을 입력해 보자. (아래 계산에서는 직교행렬의 전치행렬은 역행렬과 같고, 대각행렬의 전치행렬은 자신과 같음을 이용함)

$\mathbf{AA^T} = \mathbf{(U\Sigma V^T) \times (V \Sigma^T U^T)}$ $= \mathbf{U\Sigma^2 U^T} = \mathbf{U D U^{T}}$

두번째 식에도 동일하게 해보면,

$\mathbf{A^TA} = \mathbf{(V\Sigma^T U^T) \times (U \Sigma V^T)}$ $= \mathbf{V\Sigma^2 V^T} = \mathbf{V D' V^{T}}$

따라서 $\mathbf{D} = \mathbf{D'} = \mathbf{\Sigma^2}$ 이다.

이제 행렬 A가 주어지면 SVD를 구성하는 3개의 행렬을 구할 수 있다. 정리해 보자.

$(\mathbf{A^TA})_{nn}$ 의 고유값( $\delta_i$ )과 고유벡터( $\mathbf{v_i}$ )를 구한다.
대각행렬 $(\mathbf{\Sigma})_{mn}$ 를 구성한다. 대각원소는 $\sigma_i = \sqrt{\delta_i}$ 이고, 순서는 절대값이 큰것부터 순서대로 정렬한다.
다음 수식을 활용하여 $\mathbf{u_i}$ 를 구한다.

$\mathbf{u_i} = \frac{\mathbf{Av_i}}{\sigma_i}$

참고로 위 수식은 다음과 같이 유도된 것이다. (직교 벡터의 성질 활용)

$\mathbf{A}=\sigma_1 \mathbf{u_1 v_1^T} + \cdots + \sigma_r \mathbf{u_r v_r^T}$

$\mathbf{Av_i}=\sigma_i \mathbf{u_i v_i^T} \times \mathbf{v_i} = \sigma_i \mathbf{u_i}$
대각원소의 순서에 맞게 직교행렬 U, V를 구성한다.

마지막으로 왜 SVD를 하는지를 살펴보자. SVD를 하면 mxn 행렬 A를 다음과 같이 나타낼 수 있다.

$\mathbf{A}_{mn}=\mathbf{U}_{mm}\times \mathbf{\Sigma }_{mn}\times\mathbf{V^T}_{nn}$

영이 아닌 고유값의 개수가 r이면 위 수식은 다음과 같이 줄여 쓸 수 있다. (영공간 만큼의 값은 없어도 됨)

$\mathbf{A}_{mn}=\mathbf{U}_{mr}\times \mathbf{\Sigma }_{rr}\times\mathbf{V^T}_{rn}$

즉 mxn개의 데이터값을 저장해야 하는데, 줄여서 (m*r + r + r*n)개의 데이터만 저장하면 된다. m과 n이 크고 r작으면 그 효과가 매우 크다. 추가로 고유값이 상대적으로 작거나 0에 가까운 것이면 0에 근사하여 r의 개수를 더 줄일 수도 있다. 원래의 행렬 A로 100% 동일하게 복원은 못하겠지만, 고유값이 작으면 복원계산시 그 영향도가 적기 때문에 유사하게 복원이 가능하다. 이런 성질을 활용하면 이미지 데이터의 사이즈를 줄일 수 있다.

우리가 처음에 고민했던 연립방정식 문제를 다시 생각해 보자.

x를 고유벡터 v(n차원)의 조합으로 나타내면,

$\mathbf{x}=x_1 \mathbf{v_1} + x_2 \mathbf{v_2} + \cdots + x_n \mathbf{v_n}$

행렬 A와 곱하여 전개를 해보면,

$\mathbf{Ax}=\sigma_1 x_1 \mathbf{u_1 v_1^T v_1}+ \sigma_2 x_2\mathbf{u_2 v_2^T v_2}$ $+ \cdots + \sigma_r x_r \mathbf{u_r v_r^T v_r}$

연립 방정식은 다음과 같게 된다.

$\mathbf{Ax}=\sigma_1 x_1 \mathbf{u_1}+ \sigma_2 x_2\mathbf{u_2} + \cdots + \sigma_r x_r \mathbf{u_r} = \mathbf{b}$

b를 고유벡터 u(m차원)의 조합으로 나타내면

$\mathbf{b}=b_1 \mathbf{u_1} + b_2 \mathbf{u_2} + \cdots + b_m \mathbf{u_m}$

따라서 위아래 수식을 비교하면, $x_i = b_i/ \sigma_i, 1 \le i \le r$

r = n = m 일 때, 1개의 해(n차원)가 존재
r < min(m, n) 이고, b가 r개의 고유벡터의 조합으로 나타낼 수 있으면, 위에서 구한 값들에 r+1부터 n까지 값을 임의로 대입해서 n차원 해를 만들어도 되기 때문에 다양한 해의 집합이 존재
r < min(m, n) 이고, b가 r개의 고유벡터의 조합으로 나타낼 수 없으면, 해를 구할 수 없음. 하지만 위의 계산값은 n차원을 r차원으로 정사영시킨 최소자승해(Least Square Solution)이 됨.(증명은 나중에)

대각행렬의 역행렬을 쉽게 구할 수 있기 때문에, 아래와 같이 쉽게 전개할 수 있다.

$\mathbf{x}_{n}=\mathbf{A^{-1}}_{nm}\times \mathbf{b }_{m}$

여기서

$\mathbf{A^{-1}}_{nm}=\mathbf{V}_{nr}\times \mathbf{\Sigma^{-1} }_{rr}\times\mathbf{U^T}_{rm}$

$\mathbf{A^{-1}}=\frac{\mathbf{v_1 u_1^T}}{\sigma_1} + \frac{\mathbf{v_2 u_2^T}}{\sigma_2} + \cdots + \frac{\mathbf{v_r u_r^T}}{\sigma_r}$

'수학' 카테고리의 다른 글

정보 엔트로피 (Information Entropy) (8)	2018.12.04
행렬의 고유값 구하기 (0)	2018.11.25
지수의 확장 (1)	2018.11.11
제타 함수란? (0)	2018.11.05
해석적 확장이란? (0)	2018.11.04

하고 싶은 일을 하자

고정 헤더 영역

메뉴 레이어

메뉴 리스트

검색 레이어

검색 영역

상세 컨텐츠

본문 제목

본문