Least Square Problem(최소제곱법) 과 Normal Eq(정규방정식)

1. 정의

---

 저번 포스팅 에서도 Normal eq를 다뤘었지만, 요번 포스팅은 좀 더 선형수학의 관점에서 Normal Eq를 다뤄 보려고 한다. 우선 Least Square Problem 의 정의부터 살펴보아야 하는데,

- Given an overdetermined system 𝐴𝐱 ≃ 𝐛 where 𝐴 ∈ ${\mathbb{R}}^{m\times n}$ , 𝐛 ∈ ${\mathbb{R}}^n$, and 𝑚 ≫ 𝑛, a least squares solution $\hat{x}$ is defined as $\hat{x}$ = $argmin\Vert B-A\Vert$

 

- Least Square Problem 을 풀기 위해서는 주어진 식이

Overdetermined 되었다는 뜻이 중요한데, 이는 행렬 A의 미지수(feature 의 갯수)보다 차원(row)이 많은 경우, rank 가 m 보다는 작고, 최소 n 이 되기 때문에, 벡터 b를 만족시키는 X를 찾기 위해서는 B에 제일 가까운 Ax 를 찾을 수 밖에 없게 되고 이것이 Least Sqare Problem 이 되게 된다.

 

예시)

다음과 같이 Overdetermine 되었다는 뜻은 m(row) = 4, n = 3 으로 주어진 벡터 [11,2,-7,21]와 같은 [x1,x2,x3]를 찾기는 불가능 하다.

 

 

 

 

 

 

 

2. 기하학적 의미

---

- 기하학적 의미를 살펴보기전, 한가지 집고 넘어가야 할 점은 $Ax$ 가 Col A 의 Span 상에 있다는 점이다. 따라서 이를 잘 음미해보면서, 기하학적 의미를 살펴보자.

딱 이 그림이 아주 적절한 표현이다. 우리가 구하는 $Ax$ 는 A의 Span 위에 존재하므로, 우리가 원하는 b와 가장 근접하게 계산이 되려면 b에서 A의 span 위에 수직으로 내린 선분이 바로 원하는 $Ax$ 가 되게 된다.

- 간단하게 생각하면, 우리가 직선위 밖에 못 지나간다 할때, 점에서 선분과 가장 가까운 점은 점과 직선이 수직이 되는 점이다.

 

따라서 , 벡터공간에서 표현하게 되면, 주어진 벡터 $B-Ax$ 는 A 의 Span 내에 존재하는 모든 벡터들과 수직이 되게 되고(위의 그림에서는 $x1a1,x2a2$ 와 수직이다.), 따라서 일반식으로 쓰게 되면

$$|B-Ax|\perp [x1a1,x2a2,x3,a3...xpan]$$  

이 되게 된다.

결국, $|B-Ax|$  가 A의 col 벡터들과 모두 수직일때, $min|B-Ax|$ 을 만족시키게 되고, 이를 수식으로 나타내면 다음과 같이 된다. $a_1,a_2,a_3...a_n$ 들은 모두 A의 col 벡터들이다.

따라서, 여기서 

이 $A^T$ 이 되게되면서, 결국 식은 $A^T(b-Ax\hat{})=0$ 을 만족시키게 된다. 그리고 이제 $A^T(b-Ax\hat{})=0$ 식을 풀어주게 되면

이 나오게 되고, 최종적으로 우리는 $x\hat{}$ 을 알고 싶은 것이므로, 

최종 normal eq 의 식

을 만족시키는 Normal Eq 를 다시금 증명해냈다!!!

 

 

 

 

 

 

 

3. 수식적 증명

---

하지만 좀 더 간단히 수식적으로 증명하고 싶은 분들은...

다음을 보게 된다면,

이 수식에서 $x\hat{}=argmin||b-Ax||$ 의 식이 결국 $argmin||b-Ax|{|}^2$ 의 최소를 구하라는 말과 동치이므로 $argmin||b-Ax|{|}^2$ 의 크기는

로 풀어 나타내어지고, 행렬의 전치행렬도 결국 선형 변환으로 나타내어 지므로,

$(B-Ax{)}^T=b^T-(Ax{)}^T$ 가 되게 되어, 식을 전개해서 풀어주게 되면은

이 되게 되어 결국엔 같은 Normal Eq가 증명된다.

 

따라서 우리가 얻고자 하는 방정식은

로 얻어진다 끝~