고차원에서의 PCA

PCA를 수행하기 위해서는 데이터 공분산 행렬을 계산해야 한다. $D$ 차원에서의 데이터 공분산 행렬은 $D \times D$ 행렬이다. 이 행렬의 고윳값과 고유벡터를 계산하는 것은 $D$ 에 대해 세제곱( $O(D^3)$ )으로 스케일링되므로 연산 비용이 매우 높다. 따라서 앞서 논의한 바와 같이, 차원이 매우 높은 경우 PCA는 실현 불가능할 수 있다. 예를 들어, 만약 우리의 $\boldsymbol{x}_n$ 이 10,000 픽셀을 가진 이미지(예: $100 \times 100$ 픽셀 이미지)라면, $10,000 \times 10,000$ 공분산 행렬의 고윳값 분해를 수행해야 할 것이다. 다음에서는 데이터 포인트의 수가 차원보다 실질적으로 적은 경우, 즉 $N \ll D$ 인 상황에 대해 이 문제의 해결책을 제공한다.

$\quad$ 중심화된 데이터셋 $\boldsymbol{x}_1, \dots, \boldsymbol{x}_N, \boldsymbol{x}_n \in \mathbb{R}^D$ 가 있다고 가정하자. 그러면 데이터 공분산 행렬은 다음과 같이 주어진다.

여기서 $\boldsymbol{X} = [\boldsymbol{x}_1, \dots, \boldsymbol{x}_N]$ 은 열들이 데이터 포인트인 $D \times N$ 행렬이다.

$\quad$ 이제 $N \ll D$ , 즉 데이터 포인트의 수가 데이터의 차원보다 작다고 가정하자. 중복되는 데이터 포인트가 없다면 공분산 행렬 $\boldsymbol{S}$ 의 랭크는 $N$ 이므로, 0인 고윳값을 $D - N + 1$ 개 가지게 된다. 직관적으로 이는 약간의 중복성(redundancies)이 존재함을 의미한다. 다음에서는 이를 활용하여 $D \times D$ 공분산 행렬을 모든 고윳값이 양수인 $N \times N$ 공분산 행렬로 변환할 것이다.

$\quad$ PCA에서 우리는 다음의 고유벡터 방정식으로 귀결되었다.

여기서 $\boldsymbol{b}_m$ 은 주 부분공간의 기저 벡터이다. 이 식을 조금 다시 써보자. (10.53)에서 정의된 $\boldsymbol{S}$ 를 대입하면 다음을 얻는다.

이제 좌측에서 $\boldsymbol{X}^\top \in \mathbb{R}^{N \times D}$ 를 곱하면 다음이 산출된다.

그리고 우리는 새로운 고유벡터/고윳값 방정식을 얻는다. $\lambda_m$ 은 여전히 고윳값으로 유지되며, 이는 $\boldsymbol{X}\boldsymbol{X}^\top$ 의 0이 아닌 고윳값이 $\boldsymbol{X}^\top\boldsymbol{X}$ 의 0이 아닌 고윳값과 같다는 4.5.3절의 결과를 확인해 준다. 우리는 $\lambda_m$ 과 연관된 행렬 $\frac{1}{N}\boldsymbol{X}^\top\boldsymbol{X} \in \mathbb{R}^{N \times N}$ 의 고유벡터를 $\boldsymbol{c}_m := \boldsymbol{X}^\top\boldsymbol{b}_m$ 으로 얻는다. 중복되는 데이터 포인트가 없다고 가정하면 이 행렬은 랭크 $N$ 을 가지며 가역적(invertible)이다. 이는 또한 $\frac{1}{N}\boldsymbol{X}^\top\boldsymbol{X}$ 가 데이터 공분산 행렬 $\boldsymbol{S}$ 와 동일한 (0이 아닌) 고윳값을 가짐을 의미한다. 하지만 이것은 이제 $N \times N$ 행렬이므로, 원래의 $D \times D$ 데이터 공분산 행렬에 비해 훨씬 더 효율적으로 고윳값과 고유벡터를 계산할 수 있다.

$\quad$ 이제 $\frac{1}{N}\boldsymbol{X}^\top\boldsymbol{X}$ 의 고유벡터를 구했으므로, PCA에 여전히 필요한 원본 고유벡터를 복원할 것이다. 현재 우리는 $\frac{1}{N}\boldsymbol{X}^\top\boldsymbol{X}$ 의 고유벡터를 알고 있다. 우리의 고윳값/고유벡터 방정식의 좌측에 $\boldsymbol{X}$ 를 곱하면 다음을 얻는다.

이를 통해 데이터 공분산 행렬을 다시 복원한다. 이는 이제 우리가 $\boldsymbol{X}\boldsymbol{c}_m$ 을 $\boldsymbol{S}$ 의 고유벡터로 복원해 냈음을 의미한다.
Remark. 10.6절에서 논의할 PCA 알고리즘을 적용하려면, $\boldsymbol{S}$ 의 고유벡터 $\boldsymbol{X}\boldsymbol{c}_m$ 이 노름(norm) 1을 갖도록 정규화해야 한다.