행렬 분해 (Matrix factorization)

matrix factorization은 우리가 방정식을 인수분해 하는것처럼, 한 행렬을 두가지 이상 행렬의 곱으로 다시 분해하여 표현하는 것이다.

 

우리가 방정식을 인수분해 하면, 보이지 않았던 인수도 보이고, x값도 찾을 수 있는것처럼,

행렬도 분해를 하면 그 안에 숨겨진 데이터나 특징을 이용할 수 있다.

 

 

 

 

LU factorization

LU 분해는 비즈니스나 산업에 많이 쓰이는 방법중 하나다.

행렬을 하삼각행렬과 상삼각행렬 두 개의 곱으로 나타내는것이다.

상삼각, 하삼각 행렬은 그림에서 보다싶이 대각성분 기준으로 아래쪽 삼각형이 채워지면 하상각 반대면 상삼각이다.

 

 

 

 

 

왜 중요한가?

삼각형 형태로 만들면 앞서 배웠던 기본행렬 연산만 적용하면 되므로 계산하기가 쉽다.

그리고 우리가 합성함수 계산을 할때를 생각해보면

f(g(x)) = y 일때

f(a) = y 를 만족하는 a를 구하고,

g(x) = a를 만족하는 x를 구하면 x를 구할 수 있는것처럼

 

행렬A도 LU factorization을 통해 계산하기 쉬운 두 삼각행렬(LU)의 곱으로 나타냈으면 A = LU그 이후 해를 구할때

 

Ax = b

LUx = b

L(Ux) = b

↓

Ly = b

Ux = y

 

다음과 같이 합성함수처럼 차례대로 해를 구하면 되기 때문이다.

 

 

 

 

LU factorization 구하기(알고리즘)

어떤 행렬 A를 기본행연산을 통해 행사다리꼴 행렬 U를 만든다 할때 다음과 같이 쓸 수 있다.

 

행사다리꼴 행렬 U가 상삼각행렬 모양이기 때문에, 이것의 역행렬 연산을 하는 L은 자연스럽게 하삼각행렬 모양이 되고,  unit lower triangular matrices을 만들 수 있다.

 

 

예제

다음과 같은 A행렬이 있다면 

 

일단 L은 대충 4x4의 이러한 형태일것이다.

 

 

 

A를 기본행연산을 통해 행사다리꼴 행렬U를 만들면

기본행연산의 역행렬들은 그 기본행 연산을 반대로만 하면 되므로, 그것을 다 모은 역행렬 L은 다음과 같아진다.

 

 

결국 매번 생성되는 column들을 top pivot entry들로 나눠주면 그게 L인것이다. (highlited 한 부분 참조)