[개발자를 위한 실전 선형대수학] 직교 행렬과 QR 분해

 

개발자를 위한 실전 선형대수학(Practical Linear Algebra for Data Science)

8장 직교 행렬과 QR 분해: 선형대수학의 핵심 분해법 1

 

 

 

 

---

 

직교 행렬(orthogonal matrix)

 직교 행렬은 두 가지 속성을 가진다.

• 직교 열: 행렬의 모든 열은 서로 직교합니다.
• 단위 노름 열: 각 열의 노름(기하학적 길이)은 정확히 1이다. 

$$q_i\cdot q_j = \left\{\begin{matrix}0, \textrm{if} \ i\neq j\\ 1, \textrm{if} \ i= j\end{matrix}\right.$$

(직교 행렬 Q의 열q에 대해, 모든 열은 자기자신과의 내적은 1이고, 다른열과의 내적은 0이다)

 

위  식은 직교행렬의 원소들에 대하여, 수많은 내적의 결과가 0, 1뿐임을 의미함.

행렬의 왼쪽으로 그 행렬의 전치를 곱하면, 열들 사이의 모든 내적을 구할 수 있음

그 중 행렬 곱셈의 결과 중 대각행렬은 자기자신에 대한 내적이므로 1, 그외 원소는 0을 가짐

$$Q^TQ=I$$

 

이는 역행렬의 정의과 같으므로, 직교행렬은 자신의 전치행렬이 곧 역행렬

 

 

그람-슈미트 과정(Gram-Schmidt process, GS)

- 비직교 행렬을 직교행렬로 변환시키는 과정/ 임의의 벡터 집합에서 직교 집합을 구하는 과정

 

https://subprofessor.tistory.com/70

[선형대수학] 그람-슈미트 과정 (Gram-Schmidt Process) 예제

 

벡터 집합의 직교성 유무와 관계없이 한 벡터를 다른 벡터에 사영시킨 것을 이용하여 직교집합을 구한다.

열 $\mathbf{v_1}$부터 $\mathbf{v_n}$까지로 구성된 행렬$\mathbf{V}$는 다음 알고리즘에 따라 열 $q_k$를 갖는 직교 행렬Q로 변환된다.

$\mathbf{V}$의 모든 열벡터는 첫 번째(가장 왼쪽)부터 시작하여 마지막(가장 오른쪽)까지 차례로 이동한다.
1. 직교벡터 분해를 사용하여 $\mathbf{v_k}$를 행렬Q의 모든 이전 열과 직교화함, 이렇게 직교화된 벡터를 $\mathbf{v_k^*}$라고 함.
2. $\mathbf{v_k^*}$를 단위길이로 정규화한다. 그리고 이를 Q 행렬의 k번째 열인 $q_k$가 된다.

 

$$\mathbf{v_1}=x_1$$

$$\mathbf{v_2}=x_2- \frac{x_2\cdot \mathbf{v_1}}{\mathbf{v_1}\cdot \mathbf{v_1}}\mathbf{v_1}$$

$$\mathbf{v_3}=x_3- \frac{x_3\cdot \mathbf{v_1}}{\mathbf{v_1}\cdot \mathbf{v_1}}\mathbf{v_1}- \frac{x_3\cdot \mathbf{v_2}}{\mathbf{v_2}\cdot \mathbf{v_2}}\mathbf{v_2}$$

$$\mathbf{v_p}=x_p- \frac{x_p\cdot \mathbf{v_1}}{\mathbf{v_1}\cdot \mathbf{v_1}}\mathbf{v_1}- \frac{x_p\cdot \mathbf{v_2}}{\mathbf{v_2}\cdot \mathbf{v_2}}\mathbf{v_2}-\cdots -\frac{x_p\cdot \mathbf{v_{p-1}}}{\mathbf{v_{p-1}}\cdot \mathbf{v_{p-1}}}\mathbf{v_{p-1}}$$

 

QR 분해

GS는 행렬을 직교 행렬 Q로 변환한다. 이 과정에서  발생하는 정보 손실(원래 행렬에서 직교 행렬로의 변화)을 행렬 R에 저장하면 다음과 같이 표현할 수 있다.

$$A = QR \ \ (GS)$$

$$Q^{T}A = Q^{T}QR$$

$$Q^{T}A = R$$

 

import numpy as np
import matplotlib.pyplot as plt
import matplotlib.gridspec as gridspec

# create a random matrix
A = np.random.randn(6,6)

# QR decomposition
Q,R = np.linalg.qr(A)



# show the matrices
fig = plt.figure(figsize=(10,6))
axs = [0]*5
c = 1.5 # color limits

gs1 = gridspec.GridSpec(2,6)
axs[0] = plt.subplot(gs1[0,:2])
axs[0].imshow(A,vmin=-c,vmax=c,cmap='magma')
axs[0].set_title('A',fontweight='bold')

axs[1] = plt.subplot(gs1[0,2:4])
axs[1].imshow(Q,vmin=-c,vmax=c,cmap='magma')
axs[1].set_title('Q',fontweight='bold')

axs[2] = plt.subplot(gs1[0,4:6])
axs[2].imshow(R,vmin=-c,vmax=c,cmap='magma')
axs[2].set_title('R',fontweight='bold')

axs[3] = plt.subplot(gs1[1,1:3])
axs[3].imshow(A - Q@R,vmin=-c,vmax=c,cmap='magma')
axs[3].set_title('A - QR',fontweight='bold')

axs[4] = plt.subplot(gs1[1,3:5])
axs[4].imshow(Q.T@Q,cmap='magma')
axs[4].set_title(r'QQ',fontweight='bold')

# remove ticks from all axes
for a in axs:
  a.set_xticks([])
  a.set_yticks([])

plt.tight_layout()
plt.savefig('Figure_08_01.png',dpi=300)
plt.show()

 

손실된 정보 R을 직교행렬 Q에 곱하면, 본래 정보 A로 복원할 수 있다.(직교행렬의 전치는 그 역행렬이다)

 

Q와 R의 크기는 분해될 행렬 A의 크기와 QR분해가 경제형(축소)인지 완전형(전체)인지에 따라 달라짐

 

Q와 R의 크기

- 분해된 행렬 A의 크기는 QR 분해의 형태에 따라 달라진다.

 

높은 행렬의 QR분해 문제는 경제형, 완전형을 채택할 수 있음

2