[AI basis] Low-rank approximation

Factorization은 무슨 결과를 낼 수 있을까?

Matrix decomposition은 하나의 큰 matrix를 factorization한다고 할 수 있다.

예를 들어 3 X 3 행렬을 3 X 1, 1 X 1 행렬의 곱으로 표현할 수 있다면 우리는 효율적으로 matrix를 저장할 수 있다.

이를 위한 대표적인 2가지 decomposition 방법에 대해 알아보고자 한다.

 

1. Eigenvalue Decomposition(고유값 분해)

 임의의 정사각행렬 A에 대해

$$ Ax = \lambda x$$ 

 를 만족하는 $\lambda$를 고유값(eigen value)이라고 하고 $x$를 고유 벡터(eigen vector)라고 한다.

 

이때 eigen value와 eigen vector의 쌍은 유일하지 않기 때문에 다음과 같은 행렬을 구성할 수 있다.

$$ X = [x_1, x_2 \cdots x_n] $$ 

$$ \Lambda = [\lambda _1, \lambda _2 \ddots \lambda _3] $$ 

$x$가 역행렬이 존재할 때 다음과 같이 decomposition할 수 있다. 

 

$$ A = X \Lambda X^{-1}$$

 Eigenvalue를 활용한 decomposition은 위에서 설명한바와 같이 많은 한계점이 존재한다.

 (1) $A$가 정사각행렬이여야한다.

 (2) $X$ 가 역행렬이 존재해야한다.

 

2. SVD(Singular value decomposition) ( 특이값 분해 )

 임의의 행렬 A에 대해

$$ Av = \sigma u$$

 를 만족하는 $\sigma$를 특이값(singular value) 하고 $v$ 를 오른쪽 특이 벡터 (right singular vector), $u$ 를 왼쪽 특이 벡터 (left singular vector)라고 한다.

 

 이때 $m X n $ 행렬 A에 대해 특이값, 오른쪽 특이 벡터, 왼쪽 특이 벡터로

$$ \sum = [ \sigma _1, \sigma _2, \ddots , \sigma _n ] $$

$$ U  = [ u_1, u_2, \cdots , u_n] $$

$$ V = [ v_1, v_2 , \cdots , v_n] $$

 를 구성할 수 있고 다음의 식이 항상 성립한다.

$$ A = U \sum V^T ( UU^T = U^T U = VV^T = V^T V = I) $$ 

 

 SVD를 활용한 decomposition은 위의 eigen value를 활용한 경우보다 더 많은 자유도를 준다.

 (1) 임의의 행렬 A에 대해 특이값 분해가 항상 존재한다.

 (2) rank(A) = r 에 대해 0이 아닌 특이값은 총 r개 존재한다. 0인 특이점을 생략하는 경우를 reduced SVD라고 한다.

 (3) A의 특이값은 $AA^T$ 나 $A^T A$의 고유값의 양의 제곱근이다.

 

 최종적으로 SVD를 활용한 Low-rank approximation의 방법을 간략하게 알아보고자 한다.

 (Best) Low-rank approximation은 행렬에 제한을 두면서 원래 행렬에 가장 비슷한 행렬을 찾는 것이다. 

 이를 찾는 과정은

$$ \sum = [ \sigma _1, \sigma _2, \ddots , \sigma _n ] $$

$$ {\sum} _i = [ \sigma _1, \sigma _2, \ddots , \sigma _i, 0 \ddots , 0 ] $$

$$ U  = [ u_1, u_2, \cdots , u_n] $$

$$ V = [ v_1, v_2 , \cdots , v_n] $$

에 대해서

$$ A - A_i = [ u_{i+1}, u_{i+2} \cdots , u_{n}] [ \sigma _{i+1}, \sigma _{i+2} \ddots ,\sigma _n] [ v_{i+1}, v_{i+2} \cdots , v_n]$$

으로 구할 수 있다.

 

우리는 SVD를 활용한 low-rank approximation에 대해 간략하게 알아보았다. 이런 Low-rank approximation은 행렬을 효율적으로 다룰 수 있는 중요한 도구이다. 더 다양한 방법이 있고 발전되고 있는 분야이니 계속해서 주의를 기울여야겠다.

 

 

참고:

https://www.secmem.org/blog/2019/06/15/matrix-decomposition/