How does the solution always exists in normal equation?

Question.

우리가 normal equation 이용해서 해를 구한다면, 우리는 언제나 Ax = b에서 b를 표현하는 x를 찾을 수 있게 된다.

도대체 어떻게 "해가 없는 상황"은 존재하지 않게 되는 것일까?

 

Proposition.

Normal equation을 사용하면, over-determined 상황에서 임의의 행렬 A가 가역행렬이든 아니든 해는 언제나 존재하게 된다.

 

Proof.

출처: https://mathworld.wolfram.com/NormalEquation.html

가장 먼저, 위의 식 normal equation은 아래와 같은 의미임을 알 수 있다.

 

즉, 애초에 양쪽의 두 항은 A^T의 column들의 조합으로 이뤄진 공간이라는 것이다.

그러나, 그렇다고 해서 두 항이 언제나 같은 공간을 표현한다고 말할 수는 없다.

 

그러나, A^TA와 A^T는 아래의 조건을 만족하기에 항상 해가 존재하게 된다.

따라서, 아래를 증명해야 한다.

A^TA의 column space = A^T의 column space

 

위의 식이 성립하게 되는 이유는, 아래의 식이 성립하기 때문이다.

rank(A^TA) = rank(A^T)

위 식에 대한 증명: https://onebyonebyone.tistory.com/183

따라서, 두 행렬의 rank가 같으므로 A^TA와 A^T의 column space의 차원이 같게 된다.

따라서, A^TA와 A^T의 column space가 같게 된다.

 

Summary.

출처: https://mathworld.wolfram.com/NormalEquation.html

위 식의 A^TAx와 A^Tb가 만들어내는 column space가 동일하게 된다.

그렇기 때문에, A^TAx는 언제나 A^Tb를 표현할 수 있다.

따라서, normal equation은 언제나 해가 존재한다.