[DIP] Karhunen–Loève Transform (KLT)

Karhunen–Loève 변환(Karhunen–Loève Transform, KLT)은
데이터를 주요 성분으로 표현하여 효율적으로 압축하는 차원 축소 기법임.

• KLT는 데이터의 고유벡터(eigenvector)들의 선형 결합(linear combination)으로 데이터를 표현하는 방식으로 최적의 압축 성능을 제공함.
• Hotelling 변환(Hotelling Transform)이라고도 불리며, KLT의 기저(basis)는 변환 대상인 데이터에 따라 달라지는 특성을 가짐.

KLT는

1. 데이터의 공분산 행렬(covariance matrix)에 대한 고유값 분해(eigenvalue decomposition, EVD)를 통해 수행되며,
2. 주요 정보는 고유값(eigenvalue)이 큰 방향의 성분에 압축됨.

이 때문에 KLT는

1. 데이터 압축(compression),
2. 잡음 제거(denoising),
3. 특징 추출(feature extraction)

등의 작업에서 널리 사용됨.

PCA (Principal Component Analysis, 1901 Pearson)

KLT는 주로 신호 처리, 통신, 영상 압축 등에서 연속 확률 과정을 분석할 때 사용되는 용어.

이는 데이터의 확률적 특성에 따라 최적의 변환을 찾기 위한 기법으로 Karhunen(1946)과 Loève(1948)는 확률 과정에 대한 연구에서 이 변환을 정의했음.

PCA와 동일한 수학적 원리에 기반하나, discrete data에 초점을 맞춘 PCA와 용도적인 측면에서 차이를 보임.

KLT는 데이터의 확률적 특성에 따라 최적의 변환을 찾기 위한 기법이나, PCA와 실제 구현의 측면에서는 큰 차이가 보이지 않음(discrete data를 다룬다면)

---

KLT의 일반적인 과정

https://gist.github.com/dsaint31x/85d0f80524ffef96e45c00362da8565c

dip_KLT_EVD.ipynb

 

1. 데이터 중심화(Centering):

• 각 feature(column)의 평균을 빼서 데이터를 중심화하는 단계임.
• 이를 통해 각 데이터 포인트(sample, row))가 평균으로부터 얼마나 변동하는지를 중심으로 분석할 수 있음.

2. 공분산 행렬 계산(Covariance Matrix Calculation):

• 중심화된 데이터를 사용해 공분산 행렬을 계산함.
• 공분산 행렬은 데이터의 각 변수 간의 상관관계를 나타내며, 데이터가 어느 방향으로 더 많이 퍼져 있는지를 나타냄.

3. 공분산 행렬의 고유값 분해(Eigenvalue Decomposition):

• 공분산 행렬을 eigenvalue decomposition(고유값분해)하여 eigenvalue과 eigenvector를 구하는 단계임.
• eigenvector는 데이터가 가장 많이 변동(넓은 범위에 분포하는)하는 방향을 나타내며,
• eigenvalue(고유값)은 그 변동성의 크기를 의미함.

4. 주요 성분 선택(Principal Component Selection):

• eigenvalue(고유값)이 큰 순서대로 상위 $k$개의 고유벡터를 선택하여 새로운 basis로 사용하는 과정임.
• 고유값이 큰 고유벡터일수록 데이터의 중요한 정보가 더 많이 포함됨.

5. 데이터 투영(Data Projection):

• 원본 데이터를 선택된 고유벡터 기저에 투영하여 새로운 좌표계로 변환하는 단계임.
• 이 과정에서 데이터는 차원이 축소되며, 주요 성분으로 구성된 compressed representation(압축 표현)을 얻음.

---

예제: $5 \times 10$ 그레이스케일 이미지에 KLT 적용

1. 데이터 준비와 중심화

• 주어진 (5 \times 10) 크기의 그레이스케일 이미지를 각 행을 하나의 데이터 포인트로 보고, 10개의 픽셀 값을 가지는 벡터 5개로 구성된 데이터 행렬 ( A )로 표현함.
• 각 열(픽셀 위치)의 평균을 구해 모든 값에서 평균을 빼 줌. 이로써 중심화된 데이터 행렬 ( \tilde{A} )를 얻음.

$$\tilde{A}{i,j} = A{i,j} - \text{mean of column}_j$$

---

2. 공분산 행렬 계산

• 중심화된 데이터 ( \tilde{A} )에 대해 공분산 행렬 ( C )를 계산함.

$$C = \frac{1}{5 - 1} \tilde{A}^\top \tilde{A}$$

• 이 공분산 행렬은 $10 \times 10$ 크기를 가지며, 이전 이미지에서 각 column들의 상관관계를 나타내는 symmetric matrix.

대칭 행렬의 경우, 실수 고유값을 가지며 항상 고유값 분해가 가능!

---

3. 공분산 행렬의 고유값 분해

• 공분산 행렬 $C$에 대해 고유값 분해(EVD)를 수행하여 고유값과 고유벡터를 구함.

$$C = U \Lambda U^\top$$

• 여기서 $U$는 고유벡터들이 열 벡터로 구성된 $10 \times 10$ 행렬이며: covariance matrix에서 얻어진 $U$는 항상 orthogonal matrix
• $\Lambda$는 고유값을 대각선에 가진 $10 \times 10$ 대각 행렬임.
• 고유값이 큰 고유벡터일수록 데이터의 중요한 변동을 포함하는 방향임.

---

4. 주요 성분 선택

• 고유값이 큰 순서대로 상위 $k$개의 고유벡터를 선택함.
• 예를 들어, $k = 3$으로 설정하면 상위 3개의 고유벡터로 구성된 $10 \times 3$ 행렬 $U_3$를 형성함.

$$U_3 = \begin{bmatrix} \mathbf{u}_1 & \mathbf{u}_2 & \mathbf{u}_3 \end{bmatrix}$$

---

5. 데이터 투영(projection)

• 원래의 중심화된 이미지 데이터 $\tilde{A}$를 $U_3$에 투영하여 주요 성분을 이용한 압축 표현 $Y$를 얻음.

$$Y = \tilde{A} U_3$$

• 여기서 $Y$는 $5 \times 3$ 행렬로, 이미지 데이터를 3개의 주요 성분으로 압축한 결과임.

---

6. 주요 성분을 이용한 복원(reconstruction)

• 압축된 표현 $Y$를 $U_3$에 다시 곱하여 원래 공간으로 복원된 중심화 데이터 $\tilde{A}_{\text{reconstructed}}$를 얻음.

$$\tilde{A}_{\text{reconstructed}} = Y U_3^\top$$

---

7. 평균값 추가

• 복원된 중심화 데이터에 원래 열 평균을 더하여 원본의 스케일로 복원된 이미지를 얻음.

$$A_{\text{reconstructed}} = \tilde{A}_{\text{reconstructed}} + \text{column means}$$

---

KLT의 특징

• 최적의 ideal compression 압축:
  • KLT는 데이터의 주요 변동 방향으로 차원을 축소하여
  • 정보 손실을 최소화하면서 압축을 수행하는 특징을 가짐.
• 잡음 제거와 정보 보존:
  • 고유값이 작은 성분을 제거하여
  • 데이터의 주요 구조만 남길 수 있음.
• 데이터 종속적 basis:
  • 변환 대상 데이터에 따라 기저가 달라짐.
  • 이는 주파수 기반 변환(DCT, FFT)과의 차이점임.

---

요약

Karhunen–Loève 변환(KLT)은 데이터를 고유벡터들의 선형 결합으로 표현하여 주요 성분을 추출하는 변환임.
데이터의 변동을 분석하고, 주요 정보를 보존하여 차원을 축소하는 효과적인 기법임.

---

같이보면 좋은 자료들

https://dsaint31.me/mkdocs_site/ML/ch06/ml_pca/

BME228

2024.07.20 - [.../Linear Algebra] - [LA] Spectral Theorem for Symmetric Matrix

[LA] Spectral Theorem for Symmetric Matrix

2022.11.17 - [.../Math] - [LA] Orthogonal matrix (직교행렬)

[LA] Orthogonal matrix (직교행렬)

---