코딩 더 매트릭스 - 12장 특이값 분해

필립 클라인의 저서 코딩 더 매트릭스 12장 특이값 분해

1. 행렬을 로우 랭크 행렬로 근사시 얻는 이점을 알아봅니다.
2. 프로베니우스 norm을 알아봅니다.
3. 트롤리 노선 위치 문제를 통해 벡터들에 가장 가까운 벡터의 의미를 이해합니다.
4. 가장 가까운 1차원 공간의 의미를 이해합니다.
5. 가장 가까운 k-차원 공간의 의미를 이해합니다.
6. 특이값 분해를 알고 성질을 이해합니다.
7. 오른쪽 특이벡터들을 이용해 가장 가까운 k-차원 공간을 찾는 법을 이해합니다.

로우 랭크 행렬에 의한 행렬 근사

랭크가 1인 행렬의 모든 행들은 1차원 공간에 놓여 있습니다. $v$가 이 공간의 기저라 하면 행렬의 모든 행은 $v$의 스칼라배입니다. $u$를 스칼라배들을 엔트리로 가지는 벡터라 하면 랭크가 1인 행렬을 다음과 같이 표현할 수 있습니다.

위와 같이 행렬을 표현하면 m x n 행렬을 단순히 m + n 개의 숫자들로 표현할 수 있습니다. 그리고 행렬-벡터 곱셈에 대해 다음처럼 바꾸어 표현함으로써 연산수를 줄일 수 있습니다.

행렬의 norm

다음과 같이 행렬의 norm을 구하는 것을 프로베니우스 norm이라 합니다.

프로베니우스 norm의 제곱은 행렬 $A$의 행들의 제곱의 합과 동일합니다.

트롤리 노선 위치

벡터 $a_1, ..., a_m$으로 명시된 $m$개의 주택의 위치에 대해 $m$개의 주택에 가장 가깝게 배치하는 트램 레일을 찾으려고 합니다. 이 때 norm이 1인 벡터 $v$에 대해 트램 레일을 $Span\text{ }\{v\}$라 하면 어떤 벡터 $v$가 가장 이상적인 배치를 이끌어 낼 수 있을까요?

각 벡터 $a_1, ..., a_m$은 각자로부터 레일까지의 거리 $d_i$를 가집니다. 최소제곱처럼 벡터 $[d_1, ..., d_m]$의 norm을 최소화한다면 가장 가까운 위치라 할 수 있습니다. 즉 $d_1^2 + ... + d_m^2$을 최소화하는 경우입니다. 각각의 주택에서 레일까지의 거리는 $\parallel a_i^{\perp v} \parallel ^2$이라 할 수 있습니다. 피타고라스의 정리에 의해 $\parallel a_i^{\perp v} \parallel ^2$를 다음과 같이 쓸 수 있습니다.

각각의 주택에 대해 합하면 다음과 같습니다.

$a_i^{\parallel v} = \langle a_i, v \rangle v$인 사실과 $v$의 norm이 1인 사실을 이용해 위 식을 아래와 같이 바꿔 쓸 수 있습니다.

$v$는 $\parallel Av \parallel ^2$을 최대화하는 벡터라 할 수 있습니다. 이 때 $\sigma_1 = \parallel Av \parallel$을 만족하는 $\sigma_1$을 $A$의 첫번째 특이값이라 하고 $v$를 첫번째 오른쪽 특이 벡터라고 합니다. 따라서 제곱 거리합의 최솟값을 $\parallel A \parallel ^2 - \sigma_1^2$처럼 쓸 수 있습니다.

행렬에 대한 랭크-1 근사

벡터에 대한 최상의 k-스파스 근사를 찾는데 있어서 "최상"은 "원래의 벡터에 가장 가까운"을 말합니다. 이번에는 원래의 행렬에 가장 가까운 행렬, 즉 최상의 랭크-k 근사 행렬을 찾아보겠습니다. 여기서 가장 가까운 랭크-1 행렬을 $\bar{A}$라 쓰겠습니다. $\bar{A}$은 $\parallel A - \bar{A} \parallel$를 최소화하는 랭크-1 행렬입니다.

$\parallel A - \bar{A} \parallel$를 $A - \bar{A}$의 행벡터의 관점에서 보면 다음과 같이 쓸 수 있습니다.

$\bar{A}$는 랭크-1 행렬이므로 어떤 벡터 $v_1$에 대해 $\bar{A}$의 각 행은 $Span\text{ }\{v_1\}$내에 있어야 합니다. 따라서 $A$까지의 거리를 최소화하기 위해 $v_1$가 선택되면 $\bar{A}$를 아래와 같이 선택해야 합니다.

$a_i$에 가장 가까운 $Span\text{ }\{v_1\}$내의 벡터는 트롤리 노선 위치 문제와 마찬가지로 $a_i$에 대한 투영이라 할 수 있습니다. 따라서 각각의 행을 다음처럼 쓸 수 있습니다.

위 행렬은 다시 다음과 같이 변환됩니다.

이전에 $\sigma_1 = \parallel Av_1 \parallel$를 정의했었습니다. $\sigma_1 u_1 = Av_1$을 만족하는 norm이 1인 벡터를 $u_1$이 있다고 하면 다음과 같이 바꿔 쓸 수 있습니다.

이 때 $u_1$을 $A$의 왼쪽 특이벡터라 합니다. $\bar{A} = \sigma_1 u_1 v^T$입니다.

가장 가까운 1차원 아핀공간

트롤리 노선 위치문제의 가장 가까운 벡터 $Span\text{ }\{v\}$는 원점을 지나는 직선이었습니다. 하지만 임의의 직선은 항상 원점을 지나지는 않습니다. 임의의 직선은 아핀 공간입니다. 주택의 위치 $a_1, ..., a_m$에 대해 점 $\bar{a}$를 선택하고 다음에 $\bar{a}$를 각각의 주택의 위치에서 빼 평행이동하면 다음과 같습니다.

위처럼 평행이동한 위치에 대해 가장 가까운 1차원 벡터공간을 찾고 나중에 $\bar{a}$를 더해 벡터공간을 평행이동 시키면 가장 가까운 벡터를 찾을 수 있습니다. 이 때 $\bar{a}$는 직관적으로 입력된 점들의 센트로이드(centroid)이고 다음과 같이 기술합니다.

가장 가까운 차원-k 벡터 공간

트롤리 노선 위치 문제를 더 높은 차원으로 일반화 해보겠습니다. 이 알고리즘의 입력과 출력은 다음과 같습니다.

• input: 벡터 $a_1, ..., a_m$과 양의 정수 $k$
• output: 다음을 최소화하는 k-차원 벡터공간 $V_k$의 기저

이 알고리즘의 자연스러운 일반화는 정규직교 기저를 찾는 것입니다. 매 이터레이션에서 $V_k$의 기저를 찾는 다고 할 때 다음과 같은 프로세스가 진행됩니다.

• $v_1$은 $\parallel Av \parallel$을 최대가 되게 하는 norm이 1인 벡터
• $v_2$는 $v_1$에 직교하며 $\parallel Av \parallel$을 최대가 되게 하는 norm이 1인 벡터
• $v_3$는 $v_1$, $v_2$에 직교하며 $\parallel Av \parallel$을 최대가 되게 하는 norm이 1인 벡터 ...

다음은 이 알고리즘에 대한 의사코드입니다.

def find_right_singular_vectors(A):
	for i = 1, 2, ...
		vi = arg_max{||Av|| : ||v|| = 1, v is orthogonal to v1, v2, ..., v(i-1)}
		sigma = ||Avi||
	until Av = 0 (v is orthogonal to v1, v2, ..., vi)
	return [v1, v2, ..., vi]

위와 같은 알고리즘을 Gedaken 알고리즘이라고 합니다.

이터레이션에서 매번 얻게 되는 $\sigma_i = \parallel Av_i \parallel$는 음수가 아니며 내림차순입니다. 그도 그럴것이 $\sigma_i$는 norm이므로 당연히 음수가 아닙니다. 매 이터레이션에서 얻게 되는 $\sigma_i$는 $\parallel Av_i \parallel$값을 최대화 시키는 후보집합 중 이전 이터레이션의 결과를 제외한 집합에서 선택되므로 자명하게 내림차순임을 알 수 있습니다. 이터레이션은 $Av = 0$일 때 까지 반복됩니다. 거리는 $\parallel A \parallel ^2 - \parallel Av \parallel ^2$이므로 $Av = 0$은 더이상 가까운 벡터가 없음을 의미합니다. 따라서 이터레이션의 종료 조건이 됩니다.

한편 $A$의 모든 행들은 오른쪽 특이벡터의 생성에 속합니다. 이터레이션의 종료 조건인 $Av = 0$을 만족할 때 이전까지의 오른쪽 특이벡터 $v_1, ..., v_i$는 $v$와 직교합니다. 그리고 $v$는 $A$의 소멸자 입니다. $v$를 $V^0$의 임의의 벡터라 하겠습니다. $(V^0)^0$는 $V^0$에 직교하는 모든 벡터들로 구성되므로 $v_1, ..., v_i$는 $(V^0)^0$에 속한다고 할 수 있습니다. 그리고 $A$는 $v$의 소멸자이므로 $(V^0)^0$에 속한다고 할 수 있습니다. 따라서 $A$의 행들은 $Span\text{ }\{[v_1, ..., v_i]\}$, 즉 $(V^0)^0 = V$의 생성에 속합니다.

특이값 분해

$A$의 각 행 $a_i$가 오른쪽 특이벡터들의 생성에 속한다는 것을 보았습니다. $v_i$는 norm이 1인 벡터이므로 $a_i$를 다음과 같이 표현 할 수 있습니다.

위 식을 벡터-행렬 곱셈으로 아래와 같이 표현 할 수 있습니다.

$A$의 모든 행들에 대해 표현하면 다음과 같습니다.

이 때 우변의 첫번째 행렬의 한 열을 따로 떼어놓고 다시 정리하면 다음과 같습니다.

$\sigma_i u_i = Av_i$라 하고 다시 고쳐 쓰면 다음과 같습니다.

위 식을 간단하게 $A = U\Sigma V^T$라 쓸 수 있습니다. 이를 특이값 분해라 하고 다음 세가지 성질을 갖습니다.

• $\Sigma$는 대각 행렬이고 그 엔트리 $\sigma_1, ..., \sigma_r$은 양수이고 내림차순입니다.
• $V$는 열-직교 행렬입니다.
• $U$는 열-직교 행렬입니다.

특이값 분해는 전치에 대해 대칭성을 가집니다. $A = U\Sigma V^T$일 때 $A^T$에 대해 다음이 성립합니다.

여기서 $\Sigma$는 대각행렬이므로 $\Sigma = \Sigma^T$입니다.

가장 가까운 k-차원 공간을 찾는데 오른쪽 특이벡터 사용하기

벡터 공간 $V$의 정규 직교 기저, $v_1, ..., v_k$에 대해 다음이 성립합니다.

$a_i$에서 $V$까지의 거리는 피타고라스의 정리에 의해 $\parallel a_i^{\perp V} \parallel ^2 = \parallel a_i \parallel ^2 - \parallel a_i^{\parallel V} \parallel ^2$ 입니다. 이를 위 식에 대입하면 다음을 얻습니다.

$A$의 오른쪽 특이벡터 $v_1, ..., v_k$와 특이값 $\sigma_1, ..., \sigma_r$에 대해 제곱 거리의 합의 최소값은 $\parallel A \parallel ^2 - \sigma_1 ^2 - ... - \sigma_k ^2$입니다. 이를 증명하기 위해 임의의 다른 k-차원 벡터공간 $W$의 최소 제곱합이 $\parallel A \parallel ^2 - \sigma_1 ^2 - ... - \sigma_k ^2$보다 큼을 보여줄 필요가 있습니다. 임의의 벡터공간 $W$는 정규직교 기저를 가지고 이를 $w_1, ..., w_k$라 하겠습니다. 그러면 $A$의 각 행 $a_1, ..., a_m$에 대해 다음 제곱 거리의 합을 얻습니다.

$\parallel Aw_1 \parallel ^2 + ... + \parallel Aw_k \parallel ^2 \le \sigma_1 ^2 + ... + \sigma_k ^2$ 이면 증명이 완료됩니다.

$\parallel Aw_1 \parallel ^2 + ... + \parallel Aw_k \parallel ^2$는 $\parallel AW \parallel ^2$이라 할 수 있습니다. $A = U \Sigma V^T$로 분해할 수 있고 이를 $\parallel AW \parallel ^2$에 대입하면 $\parallel U \Sigma V^T W \parallel ^2$을 얻습니다. 이 때 $U$는 열-직교 행렬이므로 $\parallel U \Sigma V^T W \parallel ^2 = \parallel \Sigma V^T W \parallel ^2$입니다. ($\because$ norm이 1인 열-직교 행렬과의 곱은 norm을 유지함 %})

한편 $\parallel v_i \parallel ^2 = \parallel v_i^{\parallel W} \parallel ^2 + \parallel v_i^{\perp W} \parallel ^2$입니다. 식을 통해 $\parallel v_i^{\parallel W} \parallel ^2 \le \parallel v_i \parallel ^2 = 1$을 알 수 있습니다. $\Sigma V^TW$에서 $V^T W$은 $v_i^{\parallel W}$의 좌표표현의 행렬입니다. 예를 들면 $V^T W$의 첫번째 행은 $[\langle v_1, w_1 \rangle, ..., \langle v_1, w_k \rangle]$입니다. 따라서 $V^T W$의 한 행의 제곱의 합은 $\parallel v_i^{\parallel W} \parallel ^2$입니다. $\Sigma V^T W$에 이를 적용하면 최소 제곱 거리의 합은 $\sigma_1 ^2 \parallel v_1^{\parallel W} \parallel ^2 + ... + \sigma_k ^2 \parallel v_k^{\parallel W} \parallel ^2$ 입니다.

증명하고자 했던 부등식은 아래와 같았습니다.

$\parallel Aw_1 \parallel ^2 + ... + \parallel Aw_k \parallel ^2 = \sigma_1 ^2 \parallel v_1^{\parallel W} \parallel ^2 + ... + \sigma_k ^2 \parallel v_k^{\parallel W} \parallel ^2$이고 $\parallel v_i^{\parallel W} \parallel ^2 \le \parallel v_i \parallel ^2 = 1$이므로 다음이 성립합니다.

행렬 A의 최상의 랭크-k 근사

행렬 $A$의 최상의 랭크-k 근사는 다음과 같습니다.

여기서 $\sigma_i$는 $A$의 특이값, $u_i$는 왼쪽 특이벡터, $v_i$는 오른쪽 특이벡터입니다. 이 때 $\parallel A - \bar{A} \parallel ^2 = \parallel A \parallel ^2 - \sigma_1^2 - ... - \sigma_k^2$ 입니다.

$\bar{A}$는 다음과 같습니다.

$\bar{A}$를 다음과 같이 다시 쓸 수 있습니다.

$Av_i = \sigma_i u_i$라 하면 다음과 같이 쓸 수 있습니다.

$\bar{A} = \sigma_1 u_1 v_1^T + ... + \sigma_k u_k v_k^T$ 의 증명이 완료되었습니다.

특이값들의 개수는 rank A

벡터-행렬 곱의 관점에서 $A = (U \Sigma)V^T$ 의 $A$의 각 행은 $V^T$의 행의 선형결합입니다. 따라서 $Row\text{ }A = Row\text{ }V^T$ 입니다. 행렬-벡터 곱의 관점에서 $A = U(\Sigma V^T)$ 의 $A$의 각 열은 $U$의 열의 선형결합입니다. 따라서 $Col\text{ }A = Col\text{ }U$ 입니다.

가장 가까운 k-차원 아핀공간

1차원 아핀공간과 마찬가지로 센트로이드 $\bar{a}$를 찾습니다. $a_1 - \bar{a}, ..., a_m - \bar{a}$에 대해 가장 가까운 k-차원 벡터공간을 찾고 나중에 벡터공간의 기저에 $\bar{a}$를 더해줍니다.