Eigenvalue Decomposition (EVD)의 수식 기초

오늘은 Eigenvalue Decomposition(EVD)에 대해 빠삭하게 정리해보고자 한다. Singular Value Decomposition(SVD)를 설명하기 전 사전지식을 한 글로 떼어내서 다뤄볼 것이다. 본 내용은 '머피의 머신러닝 1'의 7.4장에 근거한다. 

 

 

---

0. 사전지식 

Orthogonal Matrix(직교 행렬)

두 선이 있을 때 수직이라면 이 두 선은 '직교'한다고 말한다. 벡터에서도 마찬가지다. x, y벡터가 있을 때 xT y = 0이라면 이 두 벡터는 orthogonal(직교)하다. 여기서 만약 x의 크기가 1이라면 (||x||2 == 1) 이땐 orthonomal 하다고 표현한다.

 

이를 행렬로도 확장해 보자. 정방행렬 내 모든 column이 orthonomal(orthogonal 하고 normalize 된 컬럼벡터들)하면 이 행렬은 orthognal matrix(직교행렬)이다. 직교행렬의 특징을 정리하면 다음과 같다. (참고로 로보틱스 수업에서 배우는 rotation matrix도 여기에 포함된다.)

• 직교행렬의 역행렬은 전치행렬과 같다. 

• 직교행렬 U의 크기는 1이기 때문에 Ux의 크기는 x의 크기와 같다.

• A, B라는 벡터에 직교행렬 U을 곱한다 해서 A, B사이 각도가 달라지진 않는다. 
  • 아래 식은 ||U|| = 1, UTU = 1이란 개념을 통해 풀 수 있다.

 

 

 

 

1. eigenvalue, eigenvector

행렬 A가 주어졌을 때 아래와 같은 식을 만족하는 값 λ을 고유값 eigenvalue, u를 고유벡터 eigenvector라고 부른다. 아래 식을 해석하자면  λ만큼 크기를 가진 u 방향의 벡터가 Au와 동일하다는 의미다. 일반적으로 고유벡터 u는 크기가 1이라 가정하며, 그렇기 때문에 λ는 최댓값을 갖게 된다. 참고로 A는 본인의 rank 수와 동일한 (u,λ) 쌍을 갖게 된다. 만약 rank수가 n이라고 한다면 U = [u1, u2, ... un]의 고유벡터 행렬을 갖고 있는 것이다. 그리고 보통 이 순서는 λ의 크기가 큰 순서로 나열한다. ( λ1 >=  λ2 ... >=  λn)

 

Au = λu , u != 0

 

eigenvector가 가지는 특성들은 다음과 같다. 

• A의 trace(대각합)은 eigenvalue 합과 같다.

• A의 determinant는 eigenvalue 곱과 같다. 

• A의 rank는 A의 eigenvalue 수와 같다. 

 

• A가 non-singular(역행렬을 가질 수 있는 행렬)이라면 A-1(Inverse)의 eigenvalue는 1/λ와 같다. 그러므로 아래 식이 성립한다.

 

 

 

2. Symmetric matrices

위에서 배운 Au = uλ를 AU = UΛ로도 쓸 수 있다. A의 rank가 n이라고 가정해 보자. 이때 U = [u1, u2, .. un], Λ=diag(λ1, λ2,...λn)로 표현할 수 있다. U는 eigenvector의 행렬, Λ는 eigenvalue들의 대각행렬이다. U에는 독립 벡터만 있다고 가정한다면 A와 U에 대한 관계는 아래와 같이 표현될 수 있다. 

 

A = UΛU-1

 

만약 A가 symmetric metrics(대칭행렬)이라면 eigenvector는 orthogonal matrix(직교행렬)이 된다.

직교행렬이라면 해당하는 벡터들은 서로 직교하며 크기가 1일 것이기 때문에 아래 조건을 만족한다. 

 

즉 U의 역행렬은 U의 전치행렬과 같기 때문에 아래와 같이 A의 역행렬에 대해서도 간단히 표기가 가능하다. 

 

A의 역행렬

A가 U만큼 rotate하고 Λ만큼 크기를 키운다음 다시 U만큼 unrotate 한 결과라면, A의 역행렬은 U만큼 rotate 하고 Λ만큼 크기를 줄인 다음 다시 U만큼 unrotate한 결과인 것이다.

 

 

 

3. Quadratic forms

이번엔 행렬 A가 quadratic form에 사용될 때의 특성에 대해 알아보자. 벡터 x가 있을 때 symmetric A와 함께 다음과 같이 이차형태로 표현할 수 있다. 여기선 A의 조건에 positive definite(행렬 내 모든 원소가 양수)도 추가하도록 한다. 

 

이 식을 한 번 eigenvalue, eigenvector를 사용해서 정리해 보자.  

 

만약에 A의 rank가 2고, f(x)의 값을 r이라고 했을 때 식을 전개해보자. 그러면 식이 아래와 같이 되는데, 생김새가 참 익숙하다. 마치 타원 같다! 

 

eigenvalue만큼 비례하는 길이를 가지고, eigenvector의 방향을 가진 타원이 되는 것이다. 

 

svd quadratic form

 

 

4. EVD 사용 로직 예시 

whitening

글쓰기 큐에 들어있는 PCA에서도 eigenvector를 이용한다.  간략히 PCA는 데이터의 주성분을 분석하여 차원을 축소하는 것이 목적인데, 이때 차원 축소 하기 전 데이터의 correlation은 보존하면서 normalize해야 한다(== whitening). 이때 SVD 개념이 쓰인다. 

 

 

power method

검색 알고리즘으로 유명한 page rank에서도 사용하는 power method에 대해서 간략히 알아보자. 이 문제에 들어가기 전 행렬 A의 eigenvector는 orthogonal 하다고 정의하겠다. 그리고 | λ1| > | λ2| >= ... >= | λm| >= 0을 만족한다고 하자.

 

우리에게 A 내에 있는 임의의 벡터 v(0)가 있어서, 어떤 x에 대해 v(0) = Ax로 표현될 수 있다고 가정해 보자. 이를 page rank에 대입해 생각해 보면 v(0)는 0번째 연산의 page rank vector를 의미하는 듯하다. (page rank에선 페이지간 relevant 등을 계산할 때 벡터연산을 해야하는데, 이 연산량을 줄이기 위해 power method로 대체하는 느낌.)

 

v(t) ~= Av(t-1)로 정의하면 다음 v(1) = Av(0)일 것이고, v(3) = Av(2) = AA(v1) = AAA(v0)=A**t(v0)일 것이다. 따라서 v(t)는 아래와 같이 풀어진다. λ2/λ1 <1이고, 이것을 t번 제곱하면 0에 가까워질 것이기 때문에, λ**t u1로 값이 수렴하게 되는 것이다.

 

 

 

 

---

오늘은 행렬의 eigenvalue(Λ)와 eigenvector(U)에 대해 정리했다. A가 대칭행렬일땐 U가 직교행렬인 것에 기인하여 여러 경우에 SVD 개념이 쓰일 수 있음을 알았다.

 

글을 쓸 때마다 단순히 지식을 나열하는 것이 아닌 전달을 위해선 꽤나 많은 고민과 노력이 들어간다는 걸 느낀다. 다음 포스트에선 드디어 SVD에 대해 완벽 정리할 시간이다. EVD의 특성들이 SVD에서 어떻게 쓰일 수 있는지 살펴보자.