선형대수학 :: Gram-Schmidt Process

Orthonormal Vectors

• q1 ~ qn까지 전부 Orthonormal

 

$\begin{gather*}q_1 ...q_n, \ \ \ \ \ \ q_i^Tq_j=\begin{cases} 1 & i=j \\ 0 & i \not=j \end{cases}\end{gather*}$

 

$\begin{gather*}Q=[q_1 \ q_2 ... q_n] \in R^{m*n} \\ Q^TQ = I\end{gather*}$

---

Orthogonal Matrix

• 만약 m = n 이라면

 

$\begin{gather*}Q^TQ=I \\ Q^T=Q^{-1}\end{gather*}$

 

ex) Permutation, Rotation, Haar…

 

---

Orthonormal Basis

• Orthonormal 한 basis들.
• C(A)로의 Projection (일반적인 방법)

 

$\begin{gather*}P = A(A^TA)^{-1}A^T\end{gather*}$

 

• Q가 Orthogonal Matrix 일 때 C(Q)와 C(A)가 같다면, C(A)로의 Projection은?
  1. Q를 Normalize. (C(Q)는 Normalize에 의해 변하지 않기 때문)
  2. Q는 Orthonormal Basis

 

$\begin{gather*}P= Q(Q^TQ)^{-1}Q^T\end{gather*}$

 

          3. 이때 Q^TQ는 I 이므로

 

$\begin{gather*}P = QQ^T\end{gather*}$

 

• b 를 Orthonormal C(Q)로 Projection

 

$\begin{gather*}Pb = QQ^Tb \\ = q_1q_1^Tb + q_2q_2^Tb +...+q_nq_n^Tb \\ = \frac{q_1q_1^T}{q_1^Tq_1}b + \frac{q_2q_2^T}{q_2^Tq_2}b+...+\frac{q_nq_n^T}{q_n^Tq_n}b\end{gather*}$

 

⇒ 벡터 b를 q_i 벡터로 정사영한 것들의 합.

 

---

Gram-Schmidt Process

• Orthonormal Basis를 어떻게 찾을 수 있을까?

 

• v_1, v_2, v_3 : Linearly independent
  1. w_1 은 v_1 으로 고정

 

$\begin{gather*}w_1 =v_1\end{gather*}$

  

          2. w_2는 v_2를 w_1으로 정사영한 것을 이용.

 

$\begin{gather*}w_2 = v_2 -\frac{w_1w_1^T}{w_1^Tw_1}v_2\end{gather*}$

 

          3. w_3 는 v_3을 w_1과 w_2로 정사영한 것을 이용

 

$\begin{gather*}w_3 = v_3 -\frac{w_1w_1^T}{w_1^Tw_1}v_3-\frac{w_2w_2^T}{w_2^Tw_2}v_3\end{gather*}$

 

          ⇒ w_1ㅗw_2, w_1ㅗw_3, w_2ㅗw_3

 

---

QR Factorization

$\begin{gather*}q_1 = \frac{w_1}{||w_1||}=\frac{v_1}{||v_1||}\end{gather*}$

 

$\begin{gather*}v_1 = \frac{w_1w_1^T}{w_1^Tw_1}v_1 = \frac{w_1w_1^T}{||w_1^||||w_1||}v_1 \\= q_1q_1^Tv_1\end{gather*}$

 

$\begin{gather*}v_2=\frac{w_1w_1^T}{w_1^Tw_1}v_2 + w_2 = q_1q_1^Tv_2 + \frac{w_2w_2^T}{w_2^Tw_2}v_2 \\= q_1q_1^Tv_2 + q_2q_2^Tv_2\end{gather*}$

 

$\begin{gather*}v_3 = q_1q_1^Tv_3 + q_2q_2^Tv_3 + q_3q_3^Tv_3\end{gather*}$

 

• QR Factorization
  A = QR
  A는 independent columns
  Q는 orthonormal columns
  R은 invertible upper triangle matrix
  
  

$\begin{gather*}\begin{bmatrix} v_1 & v_2 & v_3 \end{bmatrix} = \begin{bmatrix} q_1 & q_2 & q_3 \end{bmatrix} \begin{bmatrix} q_1^Tv_1 & q_1^Tv_2 & q_1^Tv_3 \\ 0 & q_2^Tv_2 & q_2^Tv_3 \\ 0 & 0 & q_3^Tv_3 \end{bmatrix}\end{gather*}$

 

$\begin{gather*}A = QR \\ A^TA = R^TQ^TQR\end{gather*}$

 

• Q 는 orthonormal 이므로

 

$\begin{gather*}A^TA = R^TR\end{gather*}$

 

$\begin{gather*}A^TA\hat x = A^Tb \\ R^TR\hat x = R^TQ^Tb \end{gather*}$

 

$\begin{gather*}\hat x = R^{-1}Q^Tb\end{gather*}$

 

$\begin{gather*}\hat x = (A^TA)^{-1}A^Tb\end{gather*}$