2. 선형대수(주성분 분석)

R^n 에 있는 m 개의 점들의 집합에 유손실 압축 lossy compression 을 적용한다고 하자.

필요한 저장 공간을 줄이는 한 가지 방법은 이 점들을 더 낮은 차원으로 부호화하는 것이다. 

각 점에 대해 그에 대응되는 부호 벡터를 구한다. l 이 n 보다 작다면, 더 적은 메모리로 그러한 부호점을 저장할 수 있다. 

이를 위해서는 주어진 점에 대한 부호를 산출하는 어떤 부화화 함수 f(x) = c 와 주어진 부호로부터 원래의 점을 재구축하는 복호화 함수 x = g(f(x)) 가 필요하다. 

 

PCA 를 바로 그러한 복호화 함수로 사용할 수 있다. 구체적으로는 복호기를 아주 단순하게 만들기 위해 행렬 곱셈을 이용해서 부호를 다시 R^n 의 점으로 복원한다. g(c) = Dc 라고 하자. D R^n*l 은 복호화 과정을 정의하는 행렬이다.

 

이 복호기를 위한 최적의 부호를 계산하는 것이 어려운 문제일 수 있다. 부호화 문제를 단수하게 유지하기 위해, PCA 는 D 의 열ㄷ르이 반드시 서로 직교라는 제약을 둔다. 

 

지금까지 서술한 문제에는 해가 여러 개 존재할 수 있다. 모든 점에 비례해서 c_i 를 감소함으로써 D_:,i 의 비례 정도를 증가할 수 있기 때문이다. 이 문제의 해가 고유함을 보장하기 위해 D 의 열들이 모두 단위 노름이어야 한다는 제약을 도입한다.

 

이러한 기본 착안을 구현 가능한 알고리즘으로 만드려면 우선 각 입력점 x 에 대한 최적의 부호점 c* 를 생성하는 방법을 고안해야 한다. 

한가지 방법은 입력점 x 와 그것의 재구축 결과인 g(c*) 사이의 거리를 최소화하는 것이다. 이 거리는 노름으로 측정할 수 있다. 주성분 분석 알고리즘에서는 L^2 노름을 사용한다.

e* = argmin||x - g(e)||_2^2

최소화 대상 함수를 따로 전개, 정리

최소화 대상 함수에서 첫 항은 e 에 의존하지 않으므로 생략,

 

g(e) 의 정의를 대입해서 정리

D 에 대한 직교성 제약과 단위 노름 제약에 따라

벡터 미적분을 이용해서 이 최적화 문제를 풀 수 있다.

x 를 그냥 행렬 벡터 곱셈 연산 한 번만 사용해서 최적으로 부호화할 ㅜㅅ 있다.

부호화할 때는 다음과 같은 부호화 함수를 적용한다.

행렬 곱셈을 하나만 더 사용하면 PCA 재구축 연산을 정의할 수 있다.

다음으로, 부호화 행렬 D 를 선택해야 한다. 이를 위해, 입려고가 재구축 사이의 L^2 거리를 최소화한다는 착안을 다시 고찰, 모든 점을 동일한 행렬 D 로 복호화할 것이므로 점들을 따로 고려할 필요가 없다. 

대신, 모든 차원과 모든 점에 관해 계산한 오차들로 이뤄진 행렬의 프로베니우스 노름을 최소화해야 한다.