선형대수(HYU)_11-12 벡터투영과 최소제곱법

3.3 Projections and Least Squares

미지수(unknown)보다 식(equation)의 수가 더 많은 경우 대부분 solution이 존재하지 않는다: Overconstrained cases

 

Example

$$\begin{array}{ccc}2x& =& b_1\\ 3x& =& b_2\\ 4x& =& b_3\end{array}\to \left[\begin{array}{c}2\\ 3\\ 4\end{array}\right]x=\left[\begin{array}{c}{b}_1\\ b_2\\ b_3\end{array}\right]$$

 

Solution이 존재하는 경우는 $b$가 $C(A)$안에 있는 경우로 매우 드물다.

$$b=\left[\begin{array}{c}{b}_1\\ b_2\\ b_3\end{array}\right]\in C(A)\to b\text{is multiple of}a=\left[\begin{array}{c}2\\ 3\\ 4\end{array}\right]$$

Solution은 $x=b_1/2=b_2/3=b_3/4$

 

대부분의 경우 정확한 solution은 구할 수 없지만 column space $C(A)$안에 존재하는 vector중 가장 적합한 vector를 찾을 수 있다 → Least Squares

 

Optimal Solution : Least Squares

평균 오차(average error) $E$를 최소화 시키는 vector $x$를 구하는 것이 system의 optimal solution과 같다.

 

평균을 구하는 가장 보편적인 방법은 각 항목의 제곱(square)을 더하는 것으로 위의 system에 적용해보면

$$E^2=(2x-b_1{)}^2=(3x-b_2{)}^2+(4x-b_3{)}^3$$

 

이는 $x$에 대한 이차방정식이므로 미분값이 0이 되는 지점이 최소값으로 error가 최소가 되는 지점이다.

$$\frac{d{E}^2}{dx}=2[(2x-b_1)2+(3x-b_2)3+(4x-b_3)4]=0$$
$$\hat{x}=\frac{2b_1+3b_2+4b_3}{2^2+3^2+4^2}=\frac{a^{T}b}{a^{T}a}$$

 

보다 일반적인 경우,

$$E^2=\Vert ax-b{\Vert }^2=(a{x}_1-b_1{)}^2+\cdots +(a{x}_m-b_m{)}^2$$

$E^2$가 0이 되는 point $\hat{x}$는:
$$(a_1\hat{x}-b_1)a_1+\cdots +(a_m\hat{x}-b_m)a_m=0$$
$$\hat{x}=\frac{a_1{b}_1+\cdots a_m{b}_m}{a_1^2+\cdots +a_m^2}=\frac{a^{T}b}{a^{T}a}$$

미지수가 한 개인 system $ax=b$의 least-square solution은 line $a$에 projection한 결과와 같다.

 

Orthogonality of $a$ and $e$

least square problem을 기하학적으로 해석하면 결국 $b$와 $a$의 거리를 최소화하는 것이고 이전 단원에서와 동일하게 $b$와 $p$를 잇는 error vector $e$가 $a$에 수직이어야 한다.

$$a^T(b-\hat{x}a)=a^T-\frac{a^{T}b}{a^{T}a}{a}^{T}a=0$$

 

Least Squares Problems with Several Variables

---

전 단원에서 line에 한정지었던 projection을 space로 확장.

→ Matrix $A$가 m by n matrix. column의 수가 1개가 아닌 $n$개

그 외는 이전과 동일하다.

• $m>n$으로 inconsistent
• $b$는 $C(A)$ 밖에 있다. $A$의 column vector의 combination으로 나타낼 수 없다.
• 핵심은 오차를 최소화하는 vector $\hat{x}$를 찾는 것

 

오차는 $E=\Vert Ax-b\Vert$로 $b$와 column space 안의 $Ax$ 사이의 거리이다.

 

least-square solution $\hat{x}$를 찾기 위해서는 $b$에 가장 가까운 $p=A\hat{x}$를 구해야 하고 이는 $b$를 column space에 projection 시킨 point 이다.

 

그렇다면 error vector $e=b-A\hat{x}$가 column space에 수직이므로 이를 이용해서 $\hat{x}$와 $p=A\hat{x}$를 다음과 같은 방법으로 구할 수 있다.

1. column space와 수직인 모든 벡터는 left nullspace안에 있으므로 $e=b-A\hat{x}$는 $A^T$의 nullspace 안에 있다.
   $$A^T(b-A\hat{x})=0or{A}^{T}A\hat{x}=A^{T}b$$
2. error vector $e$가 각 column vector $a$에 orthogonal하다.
   $$a_i^T(b-A\hat{x})=0\to \left[\begin{array}{c}{a}_1^T\\ ⋮\\ a_n^T\end{array}\right]\left[\begin{array}{c}\\ b-A\hat{x}\\ \end{array}\right]=\left[\begin{array}{c}0\\ ⋮\\ 0\end{array}\right]$$
   $$A^T[b-A\hat{x}]=0or{A}^{T}A\hat{x}=A^{T}b$$
3. Calculus way
   $$E^2=\Vert Ax-b{\Vert }^2=(Ax-b{)}^T(Ax-b)$$
   $$\frac{d{E}^2}{dx}=A^T(Ax-b)+(Ax-b)A^T=2A^{T}Ax-2A^{T}b=0$$
   $$A^{T}Ax=A^{T}b$$

 

 

공통적으로 나온 식은 $Ax=b$ 양변에 $A^T$를 곱한 $A^{T}A\hat{x}=A^{T}b$으로 normal equations 라고 한다.

 

$Ax=b$가 inconsistent할 때 least-square solution은 다음을 만족한다.

• $\text{Normal equations: }{A}^{T}A\hat{x}=A^{T}b$

$A$의 column이 모두 linearly independent하면 $A^{T}A$가 invertible 하고 정확한 $\hat{x}$를 구할 수 있다.

• $\text{Best estimate: }\hat{x}=(A^{T}A{)}^{-1}{A}^{T}b$

$b$를 column space로 projection한 $p$는

• $\text{Projection: }p=A\hat{x}=A(A^{T}A{)}^{-1}{A}^{T}b$

 

Example

$$A=\left[\begin{array}{cc}1& 2\\ 1& 3\\ 0& 0\end{array}\right],b=\left[\begin{array}{c}4\\ 5\\ 6\end{array}\right],Ax=b\text{has no solution}$$

우선 별도의 계산 없이,

• $A$의 마지막 항이 모두 0이므로 column space는 $R^3$에서 x-y plane이다.
• $b=(4,5,6)$는 공간상에 놓인 한 점이므로
• 이를 x-y plane에 projection하면 $p=(4,5,0)$이다.

Normal equation을 풀어서 확인해보면
$$\begin{array}{ccc}{A}^{T}A& =& \left[\begin{array}{ccc}1& 1& 0\\ 2& 3& 0\end{array}\right]\left[\begin{array}{cc}1& 2\\ 1& 3\\ 0& 0\end{array}\right]=\left[\begin{array}{cc}2& 5\\ 5& 13\end{array}\right]\\ \\ \hat{x}=(A^{T}A{)}^{-1}{A}^{T}b& =& \left[\begin{array}{cc}13& -5\\ -5& 2\end{array}\right]\left[\begin{array}{ccc}1& 1& 0\\ 2& 3& 0\end{array}\right]\left[\begin{array}{c}4\\ 5\\ 6\end{array}\right]=\left[\begin{array}{c}2\\ 1\end{array}\right]\\ \\ p=A\hat{x}& =& \left[\begin{array}{cc}1& 2\\ 1& 3\\ 0& 0\end{array}\right]\left[\begin{array}{c}2\\ 1\end{array}\right]=\left[\begin{array}{c}4\\ 5\\ 0\end{array}\right]\end{array}$$

 

$A$는 위의 matrix가 아니더라도 x-y plane을 구성할 수만 있으면 되기 때문에 계산이 간단한 matrix로 잡는 것이 편하다. e.g $\left[\begin{array}{cc}1& 0\\ 0& 1\\ 0& 0\end{array}\right]$

 

Remarks

Remarks 1

$b$가 이미 $A$의 column space안에 있는 vector라면 ($Ax=b$) $b$를 projection한 결과는 여전히 $b$이다.

$b\text{in column space}$

• $p=A(A^{T}A{)}^{-1}{A}^{T}b=A(A^{T}A{)}^{-1}{A}^{T}Ax=Ax=b$

Remarks 2

정반대의 경우로 $b$가 column space의 모든 column에 수직인 vector이면 ($A^{T}b=0)$b$는 zero다. vector로 projection한다.

$b\text{in left nullspace}$

• $p=A(A^{T}A{)}^{-1}{A}^{T}b=a(A^{T}A{)}^{-1}0=0$

Remarks 3

일련의 실험을 진행해서input $t$에 대한 linear function의 결과로 output $b$가 나오는 일련의 실험을 진행했다고 가정하자.$A$가 square matrix이고 invertible 하면 column space는 whole space이다. 모든 vector는 자기 자신으로 project한다. $p$는 $b$와 같고 $\hat{x}=x$이다.

$\text{If A is invertible}$

• $p=A(A^{T}A{)}^{-1}{A}^{T}b=A{A}^{-1}(A^T{)}^{-1}{A}^{T}b=b$

 

The Cross-Product Matrix $A^{T}A$

---

$A^{T}A$는 symmetric하다.

$$(A^{T}A{)}^T=A^T{A}^{T}T=A^{T}A$$

 

문제는 $A$가 invertible하냐는 것이다. 다행히:

$A^{T}A$는 $A$와 같은 nulspace를 갖는다.

proof

1. $Ax=0$ 이면 $A^{T}Ax=0$이다.
2. 반대 방향으로도 성립하는지 보기 위해 $A^{T}Ax=0$이라고 가정한 뒤 $x$를 내적하면
   
   $x^T{A}^{T}Ax=0,or\Vert Ax{\Vert }^2=0,orAx=0$

 

$A$가 independent columns를 가지면 $A^{T}A$는 $\text{square, symmetric}$ and $\text{invertible}$ 하다.

 

Projection Matrices

---

위에서 $b$에 가장 가까운 point $p$를 나타내는 식이 $p=A(A^{T}A{)}^{-1}{A}^{T}b$임을 밝혔다.

이 식은 $b$에서 $A$의 column space로 수직인 line을 내리는 matrix를 나타낸다.

$$\text{Projection matrix}P=A(A^{T}A{)}^{-1}{A}^T$$

• Matrix $P$는 임의의 vector $b$를 $A$의 column space로 project한다.
  $$p=pb\in C(A)$$
• 그 외의 component는 $C(A)$에 orthogonal하다. 즉, $A$의 left nullspace 안에 있다.
  $$e=b-Pb\in N(A^T)$$

 

Projection matrix $P=A(A^{T}A{)}^{-1}{A}^T$는 기본적으로 두 성질을 갖는다.

• $\text{It equals its square: }{P}^2=P$
• $\text{It equals its transpose: }{P}^T=P$

Proof

$P^2=P$

임의의 $b$에서 시작하더라도 $Pb$는 우리가 project하는 subspace안에 놓이게 된다. 이를 다시 project하더라도 $Pb$는 이미 subspace안에 존재하기 때문에 변하는 것이 없고 $P(Pb)$는 여전히 $Pb$이다.

$$P^2=A(A^{T}A{)}^{-1}{A}^{T}A(A^{T}A{)}^{-1}{A}^T=A(A^{T}A{)}^{-1}{A}^T=P$$

$P^T=P$

$P$의 transpose를 취해서 (A^TA)^{-1}의 symmetry를 이용해 역순으로 곱해나가면 $P$로 돌아오게된다.

$$P^T=(A^T{)}^T((A^{T}A{)}^{-1}{)}^T{A}^T=A(A^{T}A{)}^{-1}{A}^T=P$$

 

반대로, $P^2=P$와 $P^T=P$로부터 $Pb$가 $b$를 $P$의 column space로 projection하는 것이라는 것을 알아낼 수 있다.

$b-Pb$는 space에 orthogonal하기 때문에 space안의 임의의 vector $Pc$와 내적하면 그 값은 0이다.
$$(b-Pb{)}^{T}Pc=b^T(I-P{)}^{T}Pc=b^T(P-P^2)c=0$$
그러므로 $b-Pb$가 space에 orthogonal하면 $Pb$는 column space로 projection한 것과 같다

 

Example
$A$를 invertible한 4 by 4 matirx이고 네 개의 column이 모두 independent하다고 하면 column space는 whole space인 $R^4$이다.

Whole space인 $A$로 projection하는 matrix는 identity matrix이다.

$$P=A(A^{T}A{)}^{-1}{A}^T=A{A}^{-1}(A^T{)}^{-1}{A}^T=I$$

Identity matrix는 symmetric하고 $I^2=I$이며 error $b-Ib$는 zero다.

 

Least-Squares Fitting of Data

---

Input $t$에 대한 linear function의 결과로 output $b$가 나오는 일련의 실험을 진행했다고 가정하자.

이 때, 실험 결과를 나타내는 $\text{straight line }b=C+Dt$를 찾으려한다.

만약 실험오차가 없다면 $b$의 두 결과값을 골라 $C,D$를 찾을 수 있겠지만, 그렇지 않다면 optimal line을 찾기 위해 실험결과의 "평균"을 찾아야한다.

$$\begin{array}{c}C+D{t}_1=b_1\\ C+D{t}_2=b_2\\ ⋮\\ C+D{t}_m=b_m\end{array}$$

이는 2개의 미지수와 m개의 equation이 있는 overdetermined system이기 때문에 오차가 있다면 solution이 존재하지 않는다.

$$\left[\begin{array}{cc}1& t_1\\ 1& t_2\\ ⋮& ⋮\\ 1& t_m\end{array}\right]\left[\begin{array}{c}C\\ D\end{array}\right]=\left[\begin{array}{c}{b}_1\\ b_2\\ ⋮\\ b_m\end{array}\right],orAx=b$$

Best solution $\hat{x}=(\hat{C},\hat{D})$는 squared error $E^2$를 최소화하는 $x$이다.

이 때 error는 straight line으로 까지의 $\text{Vertical distance }b-C-Dt$이다. 즉, 이 값들을 제곱한 뒤 더해서 최소가 되는 $b$를 구하는 것이라고 할 수 있다.

$$\text{Minimize}{E}^2=\Vert b-Ax{\Vert }^2=(b_1-C-D{t}_1{)}^2+\cdots +(b_m-C-D{t}_m{)}^2$$

 

Example (12강 일차 연립방정식의 풀이 부분)

 

 

측정값 $(b,t)$ 세 개가 각각 $(1,-1),(1,1),(3,2)$ 일때,

세 point를 모두 지나는 line을 가정해서 equation을 적으면,
$$Ax=bis\begin{array}{ccccc}C& -& D& =& 1\\ C& +& D& =& 1\\ C& +& 2D& =& 3\end{array}or\left[\begin{array}{cc}1& -1\\ 1& 1\\ 1& 2\end{array}\right]\left[\begin{array}{c}C\\ D\end{array}\right]=\left[\begin{array}{c}1\\ 1\\ 3\end{array}\right]$$

세 포인트는 하나의 line에 놓여있지 않으므로 $Ax=b$는 least square을 이용해서 풀어야 한다.

$$A^{T}A\hat{x}=A^{T}bis\left[\begin{array}{cc}3& 2\\ 2& 6\end{array}\right]\left[\begin{array}{c}\hat{C}\\ \hat{D}\end{array}\right]=\left[\begin{array}{c}5\\ 6\end{array}\right]$$

$\hat{C}=\frac{9}{7},\hat{D}=\frac{4}{7}$이므로 best line은 $\frac{9}{7}+\frac{4}{7}t$

 

이 문제를 line과 space 두 관점으로 볼 수 있다.

 

예시에서 세 point는 하나의 line위에 존재하지 않는다. 즉 Figure b에서와 같이 $b$는 $(1,1,1)$과 $(-1,1,2)$의 combination(plane)에 존재하지 않는다.

이를 해결하기 위해서는 least squares로 line위에 있지 않은 point $b$를 line위에 있는 point $p$로 바꾼다.

 

Fitting한 line은 -1, 1, 2 지점에서 각각 $\frac{5}{7}$, $\frac{13}{7}$, $\frac{17}{7}$의 값을 갖는다. 그러므로 column space의 $p=($5 \over 7$,$13 \over 7$,$17 \over 7$)이다.그리고이vector는$b$를 column space로 projetion한 vector다.

$p$에서 $b$를 뺀 error $e=(\frac{2}{7},-\frac{6}{7},\frac{4}{7})$은 line의 vertical error 값과 같다. $e$ vector는 A의 첫 columne과 두 번쨰 column에 모두 orthogonal하므로 ($e\perp C(A)$) $A$의 left nullspace에 놓여있다.

 

straight line에 fitting 하기 위한 equation을 정리하면

 

임의의 각 point $t_1,\cdots ,t_m$에 대한 측정값이 $b_1,\cdots ,b_m$일 때 에러 $E^2$를 최소화 시키는 line $\hat{C}+\hat{D}t$는

$$A^{T}A\left[\begin{array}{c}\hat{C}\\ \hat{D}\end{array}\right]=A^{T}bor\left[\begin{array}{ccc}1& \cdots & 1\\ t_1& \cdots & t_n\end{array}\right]\left[\begin{array}{cc}1& t_1\\ ⋮& ⋮\\ 1& t_n\end{array}\right]\left[\begin{array}{c}\hat{C}\\ \hat{D}\end{array}\right]=\left[\begin{array}{cc}m& \mathrm{\Sigma }{t}_i\\ \mathrm{\Sigma }{t}_i& \mathrm{\Sigma }{t}_i^2\end{array}\right]\left[\begin{array}{c}\hat{C}\\ \hat{D}\end{array}\right]=\left[\begin{array}{c}\mathrm{\Sigma }{b}_i\\ \mathrm{\Sigma }{t}_i{b}_i\end{array}\right]$$

 

Weighted Least Squares

---

추후에 작성

 

2020.05.15 23:25 작성.