[선형대수] Gram-Schmidt process와 QR 분해

컴퓨터 비전에서 DLT를 수행하기 위해서는 QR 분해가 뭔지 알아야 하더라.. 그래서 공부해본다.
QR 분해 A=QR 에서 Q는 A의 열벡터의 그람 슈미트 정규직교화Gram-Schmidt orthonormalization, R은 A의 열벡터의 정규직교기저에 관한 성분 표시이다.
이게 대체 무슨 말인가.

Orthogonal

orthogonal set의 p개 벡터는 서로 orthogonal 하다. 서로 수직이기에 내적은 0이 될 것이다.
orthogonal set이 0벡터가 없는 집합이라면 이 집합은 선형 독립이며 동시에 S에 span되는 subspace의 basis이다.
Orthogonal basis는 basis이면서 동시에 orthogonal한 경우를 말한다.

Orthogonal Decomposition 

$y = \hat{y}+z $ $\hat{y}$ 은 W에서 y에 가장 가까운 W위의 유일한 벡터
y에서 W에 수선의 발을 내린것과 마찬가지

Gram-Schmidt process

$mathbf{R}^{n}$의 nonzero subspace 의 basis${\mathbf{x}_{1}, \mathbf{x}_{2}}$로
orthonormal basis $ {\mathbf{v}_{1}, \mathbf{v}_{2}} $찾기

1. $\mathbf{x}$를 $\mathbf{v}$로 삼고 이에 수직하는 basis를 찾기
2. x2에서 x1에 수선의 발을 내려 수직인 벡터 찾기 
   $\hat{\mathbf{x}_{2}}=\frac{ \mathbf{x}_{2}\cdot \mathbf{x}_{1}}{ \mathbf{x}_{1}\cdot \mathbf{x}_{1}}$
   수직인 벡터 : $\mathbf{v}_{2}=  \mathbf{x}_{2} -  \hat{\mathbf{x}_{2}} $

이렇게 구한 Orthogonal basis를 크기가 1인 벡터로 정규화를 거치면 Orthonormal basis가 된다.

QR Factorization

(m x n) matrix $A=[\mathbf{x}_{1} \cdots \mathbf{x}_{n}]$ 에서 A=QR로 나타낼 수 있따.
Q는 Gram-schmidt 방법으로 구한 (m x n) 크기의 Orthonormal basis의 집합이며
R은 (n x n) 크기의 Upper triangle matrix이다. 

1. A의 Orthonormal basis를 구한다.
2. 구한 Q의 column이 orthonormal하므로 $Q^{\top}Q=I$ 가 성립한다. 
   때문에 $Q^{\top}A=R$ 이 성립하므로 R을 구할 수 있다.