고차원에서의 PCA
Chapter 5 : PCA in High Dimensions
Edited by / 박상은 (CheezEun) 
장성준 (junnei) 
PCA in High Dimensions
PCA를 수행하기 위해서는 데이터 행렬 $X \in \mathbb{R}^{D \times N}$ ($N$: data의 개수)의 공분산 행렬 $S \in \mathbb{R}^{D \times D}$를 계산해야 한다.
그러나 $X$가 고차원 데이터, 예를 들어 100 x 100 이미지인 경우 $x$는 10,000 차원 데이터이고, $S$는 10,000 x 10,000 차원의 행렬이 되며 이에 대한 eigendecomposition을 수행해야 하는데, 이런 연산을 실제로 수행하기 어렵기 때문에, 다음과 같은 방법을 사용한다.
우리가 구하고자 하는 목표는
\[\boldsymbol{S} \boldsymbol{b}_m = \lambda_m \boldsymbol{b}_m, \quad m=1,\ldots,M, \tag{10.32}\]를 만족하는 $\lambda_m$과 $b_m$를 찾는 것이다.
이때 공분산 행렬 $S$는
\[\boldsymbol{S} = {1 \over N} \boldsymbol{X} \boldsymbol{X}^\textsf{T} \in \mathbb{R}^{D \times D}, \tag{10.32}\]이므로
\[{1 \over N} \boldsymbol{X} \boldsymbol{X}^\textsf{T} \boldsymbol{b}_m = \lambda_m \boldsymbol{b}_m. \tag{10.32}\]이며, 여기서 양변에 $X^\textsf{T}$를 곱해주면
\[{1 \over N} \underbrace{\boldsymbol{X}^\textsf{T}\boldsymbol{X}}_{N \times N} \underbrace{\boldsymbol{X}^\textsf{T}\boldsymbol{b}_m}_{=:\boldsymbol{c}_m} = \lambda_m \boldsymbol{X} ^\textsf{T} \boldsymbol{b}_m \Longleftrightarrow {1 \over N} \boldsymbol{X}^\textsf{T}\boldsymbol{X} \boldsymbol{c}_m = \lambda_m \boldsymbol{c}_m \tag{10.32}\]즉, $S \in \mathbb{R}^{D \times D}$ 의 eigenvalues와 $X^\textsf{T} X \in \mathbb{R}^{N \times N}$의 eigenvalue는 같다.
또한, 위 식의 양변에 다시 $X$를 곱해주면
\[\underbrace{ {1 \over N} \boldsymbol{X}\boldsymbol{X}^\textsf{T}}_{\boldsymbol{S}} \boldsymbol{X} \boldsymbol{c}_m = \lambda_m \boldsymbol{X} \boldsymbol{c}_m \tag{10.32}\]가 되므로 즉 $b_m = X c_m$ 이다. 따라서 $X^\textsf{T} X$의 eigenvector를 구하여 $X$를 곱해주는 것으로 $S$의 eigenvector도 구할 수 있다.
따라서 적절하게 작은 $N$ 값을 선정함으로써 high dimension data에 대한 공분산 행렬 $S$의 eigenvalue와 eigenvector를 쉽게 구할 수 있다.