최적근사 : 최소제곱
정의1
$n$개의 미지수와 $m$개의 식으로 이루어진 $A\mathbf{x} = \mathbf{b}$와 같이 주어진 선형 시스템에서, $\mathrm{R}^{m}$의 유클리드 내적 관점에서 $\left\|\mathbf{b} - A \mathbf{x} \right\|$ 값을 최소화하는 벡터 $ \mathbf{x}$를 최소죄곱해(least squares solution)라고 부르며, $\mathbf{b} - A \mathbf{x}$를 최소제곱 오차벡터(least squares error vector), $\left\|\mathbf{b} - A \mathbf{x} \right\|$를 최소제곱 오차(least squares error)라 부른다.
정리1 최적 근사 정리
$W$가 내적공간 $V$의 유한차원 부분공간이면 $V$의 임의의 벡터 $ \mathbf{b}$에 대해서 $\mathrm{proj}_{W} \mathbf{b}$는 $W$상의 벡터에 의한 $\mathbf{b}$의 최적 근사(best approximation)이다. 즉, $\mathrm{proj}_{W} \mathbf{b}$와 다른 $W$상의 모든 벡터 $\mathbf{w}$에 대해서 다음이 성립한다.
$$\left\|\mathbf{b} - \mathrm{proj}_{W} \mathbf{b} \right\| < \left\|\mathbf{b} - \mathbf{w} \right\|$$
$W$의 임의의 벡터 $\mathbf{w}$에 대하여
$\mathbf{b} - \mathbf{w} = (\mathbf{b} - \mathrm{proj}_{W}\mathbf{b}) + (\mathrm{proj}_{W}\mathbf{b} - \mathbf{w})$
이다. 이때 $\mathrm{proj}_{W}\mathbf{b} - \mathbf{w}$는 $W$ 상의 벡터끼리의 차이이므로 $W$에 포함되고
$\mathbf{b} - \mathrm{proj}_{W}\mathbf{b}$는 $W$에 직교하므로
$\left\|\mathbf{b} - \mathbf{w} \right\|^{2} = \left\|\mathbf{b} - \mathrm{proj}_{W}\mathbf{b} \right\|^{2} + \left\|\mathrm{proj}_{W}\mathbf{b} - \mathbf{w} \right\|^{2}$
이다.
(내적공간-내적공간에서의 직도와 직교성편 정리3 참고)
$\mathbf{w} \neq \mathrm{proj}_{W}\mathbf{b}$이기 때문에 $0 < \left\|\mathrm{proj}_{W}\mathbf{b} - \mathbf{w} \right\|^{2}$이다. 즉,
$\left\|\mathbf{b} - \mathrm{proj}_{W}\mathbf{b} \right\|^{2} < \left\|\mathbf{b} - \mathbf{w} \right\|^{2}$
$\therefore$ $\left\|\mathbf{b} - \mathrm{proj}_{W}\mathbf{b} \right\| < \left\|\mathbf{b} - \mathbf{w} \right\|$
정리2
임의의 연립일차방정식 $A\mathbf{x} = \mathbf{b}$에 대해서
$$A^{T}A\mathbf{x} = A^{T}\mathbf{b}$$
는 일치하고 위의 모든 해는 $A\mathbf{x} = \mathbf{b}$의 최소제곱해이다. 더구나 $W$가 $A$의 열공간이고 $\mathbf{x}$가 $A\mathbf{x} = \mathbf{b}$의 임의의 최소제곱해이면, $\mathbf{b}$에서 $W$로의 정사영은 다음과 같다.
$$\mathrm{proj}_{W}\mathbf{b} = A\mathbf{x}$$
$A$의 열공간을 $W$라 하자.
위의 정리1에 의하여 $A\mathbf{x} = \mathbf{b}$의 최소제곱해를 구하는 방법은
$A\mathbf{x} = \mathrm{proj}_{W}\mathbf{b}$
를 푸는 것이다. 이는
$\mathbf{b} - A\mathbf{x} = \mathbf{b} - \mathrm{proj}_{W}\mathbf{b}$
와 같고 양변의 왼쪽에 $A^{T}$를 곱함으로써 다음을 얻는다.
$A^{T}(\mathbf{b} - A\mathbf{x}) = A^{T}(\mathbf{b} - \mathrm{proj}_{W}\mathbf{b})$
이때 $ \mathbf{b} - \mathrm{proj}_{W}\mathbf{b}$는 $A$의 열공간에 직교하는 $\mathbf{b}$의 성분이므로 $A^{T}$의 영공간에 존재한다.
(좌표와 기저-기본공간과 직교여공간편 정리3-2 참고)
즉,
$ A^{T}(\mathbf{b} - \mathrm{proj}_{W}\mathbf{b}) = \mathbf{0}$
이다. 따라서
$ A^{T}(\mathbf{b} - A\mathbf{x}) = \mathbf{0}$
이고 이를 정리하면
$A^{T}A\mathbf{x} = A^{T}\mathbf{b}$
이다.
정의2
위에 $$A^{T}A\mathbf{x} = A^{T}\mathbf{b}$$는 $A\mathbf{x} = \mathbf{b}$에 대한 정규방정식(normal equation) 또는 정규시스템(normal system)이라 한다.
정리3
$A$가 $m \times n$ 행렬이면 다음은 동등하다.
$(1)$ $A$는 일차독립 열벡터를 갖는다.
$(2)$ $A^{T}A$는 가역이다.
pf)
$\Rightarrow)$
$A^{T}A\mathbf{x} = \mathbf{0}$의 임의의 해를 $\mathbf{x}_{0}$라 하자.
그러면 $A\mathbf{x}_{0}$는 $A^{T}$의 영공간에 속하고 또한 $A$의 열공간에 속한다.
이들 공간은 직교여공간이므로
$A\mathbf{x}_{0} = \mathbf{0}$
이다.
(내적공간-내적공간에서 각도와 직교성편 정리4-2 참고)
이때 $A$는 일차독립 열벡터를 가지므로 $\mathbf{x}_{0} = \mathbf{0}$이다.
(연립일차방정식-행렬 기초 지식편 정의6 참고)
즉, $A^{T}A\mathbf{x} = \mathbf{0}$는 자명해만을 갖는다. 이때 $A^{T}A$의 크기는 $n \times n$이므로 $A^{T}A$는 가역이다.
(가역과 동등한 명제들 1편 (2) 참고)
$\Leftarrow)$
$A\mathbf{x} = \mathbf{0}$의 임의의 해를 $\mathbf{x}_{0}$라 하자. 즉,
$A\mathbf{x}_{0} = \mathbf{0}$
이다. 양변의 왼쪽에 $A^{T}$를 곱한뒤 정리하면
$A^{T}A\mathbf{x}_{0} = \mathbf{0}$
이다. 이때 $A^{T}A$는 가역이므로 $\mathbf{x}_{0} = \mathbf{0}$이다.
즉, $A\mathbf{x} = \mathbf{0}$은 자명해만을 갖는다.
$\therefore$ $A$는 일차독립 열벡터를 갖는다.
따름정리
$A$가 일차독립 열벡터들로 이루어진 $m \times n$ 행렬이라고 하면, 모든 $m \times 1$ 행렬 $\mathbf{b}$에 대해서, 선형 시스템 $A\mathbf{x} = \mathbf{b}$는 유일한 최소제곱해를 가진다. 이것의 해는 다음과 같이 주어진다.
$$\mathbf{x} = (A^{T}A)^{-1}A^{T}\mathbf{b}$$
또한 $W$가 $A$의 열공간이라면, $W$로의 $\mathbf{b}$의 정사영은 다음과 같게 된다.
$$\mathrm{proj}_{W}\mathbf{b} = A\mathbf{x} = A(A^{T}A)^{-1}A^{T}\mathbf{b}$$
정리4
만약 $A$가 일차독립 열벡터를 가지는 $m \times n$ 행렬이라고 하고, $A = QR$이 $A$의 $QR$-분해라고 할 때, $R^{m}$에 존재하는 각각의 $\mathbf{b}$에 대해서 $A\mathbf{x} = \mathbf{b}$의 최소제곱해는 다음과 같이 주어진다.
$\mathbf{x} = R^{-1}Q^{T}\mathbf{b}$
위의 따름정리에서 $A =QR$를 대입하고 $Q^{T}Q = I$를 이용하면
(응용-그람-슈미트 과정 : $QR$-분해편 보조정리2 참고)
$\mathbf{x} = ((QR)^{T}(QR))^{-1}(QR)^{T}\mathbf{b}$
$= (R^{T}Q^{T}QR)^{-1}(QR)^{T}\mathbf{b}$
$= R^{-1}(R^{T})^{-1}R^{T}Q^{T}\mathbf{b}$
$= R^{-1}Q^{T}\mathbf{b}$
정의3
$W$가 $R^{m}$의 부분공간일 때 $R^{m}$의 각 벡터 $\mathbf{x}$를 $W$로의 정사영 $\mathrm{proj}_{W}\mathbf{x}$로 사상하는 변환 $P : R^{m} \to W$를 $R^{m}$에서 $W$로의 정사영(orthogonal projection of $R^{m}$ on $W$)이라 한다.
# 변환 $P$의 표준행렬은 $[P] = A(A^{T}A)^{-1}A^{T}$이다.
(여기서 $A$는 $W$의 임의의 기저를 $A$의 열벡터로 사용하여 구성된다.)