[Linear Algebra] 15. Least squares & Projection matrix + Gram-Schmidt Orthogonalization

이번 글에서는 최소 자승법(least square method)에 대해 알아볼 것이다.

 

Problem

최소 자승법이 풀고자 하는 문제는 다음과 같다.

 

rank($A$)=2인 $\underset{3 \times 2} A$와 $A$의 column space에 속하지 않는 3-D 벡터 $\mathbf{\vec{b}}$가 있을 때,

어떤 $A \mathbf{\vec{x}}$도 $\mathbf{\vec{b}}$와 같아질 수 없다. 즉, $A \mathbf{\vec{x}} = \mathbf{\vec{b}}$의 해는 존재하지 않는다.

 

그러면, 최대한 $\mathbf{\vec{b}}$와 최대한 가까운 $A \mathbf{\vec{x}}$라도 구해보자!!

다시 말해, $\mathbf{\vec{e}}(=\mathbf{\vec{b}} - A \mathbf{\vec{x}})$의 길이 즉, $\lVert \mathbf{\vec{e}} \rVert_2^2$($=\mathbf{\vec{e}}$의 2-norm 제곱)이 최소가 되는 벡터 $\mathbf{\vec{x}}$를 구해보자!!

(그래서 이름이 least squares다. 직역하면 "제곱들의 최소"이니까)

Solution

$\lVert \mathbf{\vec{e}} \rVert_2^2$이 가장 작으려면 $\mathbf{\vec{e}}$와 $A \mathbf{\vec{x}}$가 수직 관계에 있어야 한다.

그러므로, $\mathbf{\vec{b}} - A\mathbf{\vec{x}}$와 $A\mathbf{\vec{x}}$의 내적이 0이 되는 $\mathbf{\vec{x}}$ 즉, $\mathbf{\hat{x}}$을 찾으면 문제를 풀 수 있다. 식 전개는 다음과 같다.

 

$$\begin{matrix}(\mathbf{\vec{b}} - A\mathbf{\hat{x}})^\top A\mathbf{\hat{x}} = 0 \rightarrow (\mathbf{\vec{b}}^\top A - \mathbf{\hat{x}}^\top A^\top A) \mathbf{\hat{x}} = 0 \\ \mathbf{\vec{b}}^\top A - \mathbf{\hat{x}}^\top A^\top A = 0 \\ \mathbf{\vec{b}}^\top A = \mathbf{\hat{x}}^\top A^\top A \leftrightarrow A^\top \mathbf{\vec{b}} =  A^\top A \mathbf{\hat{x}} \\ \mathbf{\hat{x}} = (A^\top A)^{-1}A^\top \mathbf{\vec{b}} \end{matrix}$$

 

이때, 정사영된 벡터는 $A \mathbf{\hat{x}} = A( A^\top A)^{-1}A^\top \mathbf{\vec{b}}$로 표현할 수 있으며,

$A( A^\top A)^{-1}A^\top \mathbf{\vec{b}}$는 projection matrix이라고 부른다.

 

---

응용: Gram-Schmidt Orthogonalization

Problem

서로 independent한 벡터 $\mathbf{\vec{a_1}}, \mathbf{\vec{a_2}}, \mathbf{\vec{a_3}}, \mathbf{\vec{a_4}}$이 있을 때, 이 벡터들은 4차원 공간을 span한다.

이때, span하는 4차원 공간의 orthogonal basis $\mathbf{\vec{v_1}}, \mathbf{\vec{v_2}}, \mathbf{\vec{v_3}}, \mathbf{\vec{v_4}}$를 찾아보자!! (by $\mathbf{\vec{a_1}}, \mathbf{\vec{a_2}}, \mathbf{\vec{a_3}}, \mathbf{\vec{a_4}}$)

 

Solution

1. $\mathbf{\vec{a_1}}$을 첫번째 orthogonal basis $\mathbf{\vec{v_1}}$으로 삼는다.

$$\mathbf{\vec{v_1}} = \mathbf{\vec{a_1}}$$

 

2. $\mathbf{\vec{a_2}}$ 벡터에서 "$\mathbf{\vec{a_2}}$를 $\mathbf{\vec{v_1}}$에 정사영 내린 벡터"를 뺀다.

$$\mathbf{\vec{v_2}} = \mathbf{\vec{a_2}} - \left(\mathbf{\vec{a_2}}^\top \cdot \frac{\mathbf{\vec{v_1}}}{\lVert\mathbf{\vec{v_1}}\rVert_2}\right)\cdot \frac{\mathbf{\vec{v_1}}}{\lVert\mathbf{\vec{v_1}}\rVert_2} = \mathbf{\vec{a_2}} - \frac{\mathbf{\vec{a_2}}^\top \mathbf{\vec{v_1}}}{\lVert\mathbf{\vec{v_1}}\rVert_2^2}\cdot \mathbf{\vec{v_1}}$$

 

3. 여기서 least square에서 배운 내용을 활용한다.

즉, $\mathbf{\vec{a_3}}$ 벡터에서 "$\mathbf{\vec{a_3}}$을 $V = \begin{bmatrix} \mathbf{\vec{v_1}} & \mathbf{\vec{v_2}} \end{bmatrix}$의 column space에 정사영 내린 벡터 $V\mathbf{\hat{x}}$"를 뺀다.

 

$$V \mathbf{\hat{x}} = V( V^\top V)^{-1}V^\top \mathbf{\vec{a_3}} \rightarrow \mathbf{\vec{v_3}} = \mathbf{\vec{a_3}} - V( V^\top V)^{-1}V^\top \mathbf{\vec{a_3}} \\ \mathbf{\vec{v_3}} = \mathbf{\vec{a_3}} - \begin{bmatrix} \mathbf{\vec{v_1}} & \mathbf{\vec{v_2}} \end{bmatrix} \left(\begin{bmatrix} \mathbf{\vec{v_1}}^\top \\ \mathbf{\vec{v_2}}^\top \end{bmatrix} \begin{bmatrix} \mathbf{\vec{v_1}} & \mathbf{\vec{v_2}} \end{bmatrix} \right)^{-1} \begin{bmatrix} \mathbf{\vec{v_1}}^\top \\ \mathbf{\vec{v_2}}^\top \end{bmatrix} \mathbf{\vec{a_3}}$$

$$\mathbf{\vec{v_3}} = \mathbf{\vec{a_3}} - \begin{bmatrix} \mathbf{\vec{v_1}} & \mathbf{\vec{v_2}} \end{bmatrix} \begin{bmatrix} \frac{1}{\lVert\mathbf{\vec{v_1}}\rVert_2} & 0 \\ 0 & \frac{1}{\lVert\mathbf{\vec{v_1}}\rVert_2} \end{bmatrix} \begin{bmatrix} \mathbf{\vec{v_1}}^\top \\ \mathbf{\vec{v_2}}^\top \end{bmatrix} \mathbf{\vec{a_3}}$$

$$\mathbf{\vec{v_3}} = \mathbf{\vec{a_3}} - \begin{bmatrix} \frac{\mathbf{\vec{v_1}}}{\lVert\mathbf{\vec{v_1}}\rVert_2} & \frac{\mathbf{\vec{v_2}}}{\lVert\mathbf{\vec{v_1}}\rVert_2} \end{bmatrix} \begin{bmatrix} \mathbf{\vec{v_1}}^\top \\ \mathbf{\vec{v_2}}^\top \end{bmatrix} \mathbf{\vec{a_3}}$$

$$\mathbf{\vec{v_3}} = \mathbf{\vec{a_3}} - \begin{bmatrix} \frac{\mathbf{\vec{v_1}}\mathbf{\vec{v_1}}^\top \mathbf{\vec{a_3}}}{\lVert\mathbf{\vec{v_1}}\rVert_2} & \frac{\mathbf{\vec{v_2}}\mathbf{\vec{v_2}}^\top \mathbf{\vec{a_3}}}{\lVert\mathbf{\vec{v_1}}\rVert_2} \end{bmatrix}\mathbf{\vec{a_3}}$$

$$\mathbf{\vec{v_3}} = \mathbf{\vec{a_3}} - \frac{\mathbf{\vec{a_3}}\mathbf{\vec{v_1}}}{\lVert\mathbf{\vec{v_1}}\rVert_2^2}\mathbf{\vec{v_1}} - \frac{\mathbf{\vec{a_3}}\mathbf{\vec{v_2}}}{\lVert\mathbf{\vec{v_2}}\rVert_2^2}\mathbf{\vec{v_2}}$$

 

4. $V = \begin{bmatrix} \mathbf{\vec{v_1}} & \mathbf{\vec{v_2}} & \mathbf{\vec{v_3}} \end{bmatrix}$로 수정하고 3번을 반복한다. 식 전개는 생략하겠다.

 

$$\mathbf{\vec{v_4}} = \mathbf{\vec{a_4}} - \frac{\mathbf{\vec{a_4}}\mathbf{\vec{v_1}}}{\lVert\mathbf{\vec{v_1}}\rVert_2^2}\mathbf{\vec{v_1}} - \frac{\mathbf{\vec{a_4}}\mathbf{\vec{v_2}}}{\lVert\mathbf{\vec{v_2}}\rVert_2^2}\mathbf{\vec{v_2}} - \frac{\mathbf{\vec{a_4}}\mathbf{\vec{v_3}}}{\lVert\mathbf{\vec{v_3}}\rVert_2^2}\mathbf{\vec{v_3}}$$