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\left \| B - A \right \|\)

 

- 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가 증명된다.

 

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

로 얻어진다 끝~