연립방정식
에서 이면 정확한 해가 존재한다. 그러나 측정값이 많거나 noise가 포함된 데이터에서는 인 경우가 일반적이다.
이때 정확한 해 대신 residual norm을 최소화하는 를 찾는다.
이를 Least Squares Solution이라고 한다.
기하학적 의미
는 위에 있으면서 에 가장 가까운 벡터이다. 따라서
이다.
Residual Vector를
라고 하면 Projection의 성질에 따라
이다.
Normal Equation
Residual이 의 모든 column과 orthogonal하므로
이다. 정리하면
를 얻는다. 이를 Normal Equation이라고 한다.
는 항상 Symmetric Positive Semidefinite이다.
Full Column Rank인 경우
의 column들이 Linearly Independent하면
이고 는 Positive Definite이며 invertible하다.
따라서 유일한 Least Squares Solution은
이다.
예제
이다. 세 번째 equation은 이므로 exact solution은 없다.
이다.
Normal Equation을 풀면
이다.
이고 실제로
이다.
Projection Matrix
Full Column Rank이면
이다. 따라서 에 대한 Projection Matrix는
이다.
Residual Projection은
이며 로 Projection한다.
QR Factorization을 이용한 방법
이고 가 Full Column Rank라면
이다. 최적조건은
가 된다.
은 Upper Triangular Matrix이므로 Back Substitution으로 푼다. 를 만들지 않아 numerical stability가 더 좋다.
Rank가 부족한 경우
의 column들이 Linearly Dependent하면 는 singular하고 Least Squares Solution이 여러 개일 수 있다.
SVD
를 사용하면 Pseudoinverse
를 정의할 수 있다.
는 Least Squares Solution 중 norm이 가장 작은 Minimum-Norm Solution이다.
SVD 관점에서의 최소화
Orthogonal Matrix는 norm을 보존하므로
이다.
로 두면 nonzero Singular Value에 대해
로 선택하는 것이 residual을 최소화한다. zero Singular Value에 대응하는 coordinate는 0으로 두면 minimum norm이 된다.
직선 근사와 Linear Regression
데이터
에 직선
을 적합한다고 하자.
이다.
Least Squares는
를 최소화한다. Machine Learning의 기본 Linear Regression과 같은 구조이다.
Condition Number와 주의점
Normal Equation은 구현이 간단하지만
이다. 가 ill-conditioned하면 오차가 더 커질 수 있다.
일반적인 선택은 다음과 같다.
- 작고 well-conditioned한 문제: Normal Equation
- 일반적인 Full Rank 문제: QR Factorization
- Rank-deficient 또는 ill-conditioned 문제: SVD
정리
- Least Squares는 를 최소화한다.
- Residual은 와 orthogonal하다.
- Normal Equation은 이다.
- Full Column Rank이면 solution은 유일하다.
- QR 방식은 를 푼다.
- SVD의 는 Minimum-Norm Least Squares Solution이다.
확인 문제
세 점 에 가장 잘 맞는 직선 를 구한다.
풀이
이다.
Normal Equation을 풀면
이다. 따라서 근사 직선은
이다.