LU, Cholesky, QR, SVD, Eigenvalue decomposition의 차이가 무엇인가요?

이 게시물은 장형기님의 기술면접 100선에 대한 답을 제 나름대로 적어본 것입니다.

---

LU, Cholesky, QR, SVD, Eigenvalue decomposition은 모두 행렬을 분해하는 기술입니다.
각 분해 방법은 행렬을 다른 형태로 분해하여 문제를 풀거나 효율적으로 계산을 수행할 수 있도록 돕습니다.

1. LU분해

• 정의: 행렬 A를 Lower Triangular Matrix L과 Upper Triangular matrix U로 분해하는 방법입니다.
  $A = LU$

• 조건: A는 일반적으로 Inversible해야하며, LU 분해는 모든 inversible matrix에 대해 가능하지만 피버팅을 필요로 하는 경우가 있어서 PLU 분해를 사용하기도 합니다.

• 장점: 비교적 간단하고 계산이 빠르며, 선형 시스템을 푸는 데 주로 사용됩니다.

2. Cholesky 분해

• 정의: Symmetric matrix이면서 Positive Definite인 matrix를 분해하는 방법입니다.

  $A = LL^T$

  여기서 L은 Lower Triangular matrix입니다.

• 조건: 행렬이 symmetric이고 Positive definite일 때만 가능합니다.

• 장점: LU 분해보다 더 효율적입니다. A가 symmetric이고 positive definite인 경우에 Cholesky 분해는 계산이 더 빠르고 안정적입니다.

3. QR Decomposition

• 정의: 주어진 행렬 A를 직교행렬 Q와 Upper triangular R로 분해하는 방법입니다.
  $A = QR$

• 조건: 모든 직사각형 행렬에 대해 가능하지만, 행렬이 full rank일 때 정확한 QR 분해를 수행할 수 있습니다.

• 장점: 수치적 안정성이 뛰어나고 mean square error를 푸는데 매우 유용합니다.

4. SVD

• 정의: 임의의 행렬 A를 다음 세 행렬의 곱으로 분해
  $A = U\Sigma V^T$
  $U: 왼쪽 직교행렬 \\ \Sigma:대각행렬 \\ V^T:오른쪽 직교 행렬$

• 조건: 임의의 $m \times n$ 행렬에 적용 가능

• 장점: 모든 행렬에 대해 항상 적용 가능하고 차원 축소, 데이터 압축, 노이즈 제거에 강력합니다.

5. 고유값 분해

• 정의: 정사각행렬 A를 고유값과 고유벡터를 사용하여 다음과 같이 분해.

  $A = VΛV^{-1}$

• 조건: A는 정사각행렬이어야 합니다.

• 장점: 행렬의 대각화를 통해 계산 단순화를 할 수 있습니다.

---

SLAM에서는 어떤 방식을 자주 사용하고, 어떤 상황에서 이를 사용하나요?

Cholesky, QR decomposition을 주로 사용하는 것 같습니다.
optimization 과정에서 수식을 풀기 위해 사용하거나 Eigen value, vector를 계산할 때 사용하는 것을 볼 수 있었습니다.

---