Summary

본 내용은 MIT 18.065 강의 33 번의 일부 내용 정리입니다. 자세한 내용은 해당 강의를 참고하세요.

강의 33번에서 거리행렬 D 가 주어졌을 경우, 위치 행렬 X 를 찾는 문제가 나온다. 이때 D 는 \(X^TX\) 와 같은 구성으로 결정할 수 있는데, 2 가지 방식이 있다. 하나는 고유값 분해를 이용한 대칭행렬의 \(D = QΛQ^T\) 분해이고, 다른 하나는 소거를 이용한 Cholesky 분해 유도 방식이다. 즉, \(D = LDU = LDL^T\) 와 같은 형태로 유도해서 \(X = \sqrt(D) L^T\) 의 상삼각행렬 형태로 만드는 방식이다.

행렬 A가 symmetric, positive definite 일경우, Choleksy decomposition 을 검토한다.

먼저, A 를 LDU 분해를 해서, A 가 LDL^T 형식으로 유도됨을 확인한다. 그리고 최종적으로 R 의 Cholesky 분해 함수를 이용해서 값을 서로 검증한다.

작업 순서는 아래와 같다.

  1. \(A = LU\), LU 분해를 한다.
  2. \(A = LDU\), 1단계에서의 U 에서 대각성분을 따로 빼서 대각행렬 D 로 구성한다. 여기서 U 는 대각성분이 1이 된다.
  3. \(A = LDL^T\), 형태로 보는데, 여기서 위의 U 는 L^T 와 같음을 확인한다.
  4. \(A = L \sqrt(D) * \sqrt(D)L^T\), 와 같은데, \(R = \sqrt(D) * L^T\) 라고 한다면
  5. \(A = R^T R\) 이 된다. 이것이 Cholesky decomposition 이 된다.
#install.packages("Matrix")
library(matrixcalc)

# Symmetric, postitive definite matrix 구성
A <- matrix( c ( 2, 1, 1, 2 ), nrow=2, byrow=TRUE)
A
##      [,1] [,2]
## [1,]    2    1
## [2,]    1    2
# LU 분해 작업 
luA <- lu.decomposition(A)
L <- luA$L # 하삼각행렬
U <- luA$U # 상삼각행렬

L # 하삼각행렬
##      [,1] [,2]
## [1,]  1.0    0
## [2,]  0.5    1
U # 상삼각행렬
##      [,1] [,2]
## [1,]    2  1.0
## [2,]    0  1.5
# u = d * u1, => u1 = d-1 * u
# 대각행렬 구성
D <- diag(U) # U 에서 대각성분을 구하고
D <- diag(D) # 대각성분을 이용해서 대각행렬을 구한다.
D # 대각행렬
##      [,1] [,2]
## [1,]    2  0.0
## [2,]    0  1.5
# 상삼각행렬(u) 에서 대각성분을 1로 만들었을 경우의 상삼각행렬
U1 <- solve(D) %*% U
U1 # 대각성분이 1 인 상삼각행렬
##      [,1] [,2]
## [1,]    1  0.5
## [2,]    0  1.0
# U1 은  L 의 전치행렬과 동일함을 확인한다. U1 = L^T
t(L) # L의 전치행렬은 U1 와 동일하다.
##      [,1] [,2]
## [1,]    1  0.5
## [2,]    0  1.0
# R = D^(1/2) * LT
R1 <- sqrt(D) %*% t(L) # A = LDU 소거를 이용한 Cholesky 분해에서의 상삼각행렬 팩터
R1 # Cholesky 분해 행렬
##          [,1]      [,2]
## [1,] 1.414214 0.7071068
## [2,] 0.000000 1.2247449
R2 <- chol(A) # R 내장함수의 Cholesky 분해 함수를 이용한 상삼각행렬 팩터 
R2 # Cholesky 분해 행려
##          [,1]      [,2]
## [1,] 1.414214 0.7071068
## [2,] 0.000000 1.2247449
# R1, R2 가 서로 같음을 확인한다.