6.5 Least Squares Problems

이번 포스트에서는 least-squares problems에 대해 알아보도록 하겠습니다.

1) Least-Squares Problems

(1) Least-Squares Problems

다음의 linear system을 생각해봅시다.

다음 linear system은 $A, \boldsymbol{b}$에 따라 3가지 종류의 solution이 존재할 수 있습니다. solution이 없거나(inconsistent), solution이 하나만 존재하거나, solution이 무수히 많이 존재하는 경우입니다. 이 중에서 solution이 존재하지 않는 경우를 생각해봅시다.

만약 위 system이 solution이 존재하지 않는 경우, 다음으로 생각해볼 수 있는 것은

를 만족하는 $\boldsymbol x$를 찾는 것입니다. 즉 $A\boldsymbol{x}$와 $\boldsymbol{b}$가 가장 비슷하게 만들어주는 $\boldsymbol{x}$를 solution으로 대체하는 것입니다. 그렇다면 $A\boldsymbol x$와 $\boldsymbol b$가 비슷하다는 것을 어떻게 정의할까요? 바로 distance를 이용합니다.

즉, $A\boldsymbol x$와 $\boldsymbol b$의 distance가 가장 가까워지는 $\boldsymbol x$를 solution으로 대체할 수 있습니다.

The least squares problem은 다음 distance

를 최소화하는 $\boldsymbol{x}$를 찾는 문제입니다.

(2) Least-squares solution

위의 least squares problem의 solution은 다음과 같이 정의합니다.

Definition : Least-squares solution

If $A$ is $m\times n$ matrix and $\boldsymbol b$ is in $\mathbb R^n$, a least-squares solution of $A\boldsymbol x = \boldsymbol{b}$ is an $\hat{\boldsymbol{x}}$ in $\mathbb R^n$ such that

for all $\boldsymbol{x} \in \mathbb R^n$

즉 $\|\boldsymbol{b}-A\boldsymbol{x}\|$를 최소화시키는 $\boldsymbol{x}$가 least-squares solution이 됩니다.

만약

가 solution이 존재한다면, least squares solution은 위 system의 solution이 됩니다. 이는 해당 system의 solution이

을 만족하기 때문입니다.

지금까지 least squares problem과 solution에 대해 알아봤습니다. 그렇다면 least-squares solution을 어떻게 찾을 수 있을까요?

(3) How to find the solution

least-squares solution을 찾는 방법에서의 핵심은 $A\boldsymbol{x}$의 의미를 파악하는 것입니다.

$A\boldsymbol{x}$는 $A$의 column의 linear combination으로 표현된 벡터입니다. 즉 모든 $\boldsymbol x \in \mathbb R^n$에 대해서

입니다. $A\boldsymbol{x} =\boldsymbol{b}$가 solution이 없는 경우는

인 것을 뜻합니다. 따라서, $A\boldsymbol{x} = \boldsymbol{b}$의 least squares solution을 찾는 것, 즉

를 만족시키는 $\hat{\boldsymbol{x}}$를 찾는 것은 $ColA$에서 $\boldsymbol{b}$와 가장 가까운 벡터를 만들어주는 $\hat{\boldsymbol{x}}$를 찾는 것과 같습니다.

$ColA$ 또한 $\mathbb R^m$의 subspace이므로, $\boldsymbol{b}$와 $ColA$와 가장 가까운 벡터는 projection을 통해 만들어줄 수 있습니다. 즉

를 만족하는 $\boldsymbol{x}$가 위 least-squares problem의 solution이 됩니다.

여기까지 least-squares problem of $A\boldsymbol{x}=\boldsymbol{b}$를 푸는 것은

를 푸는 것과 같다는 것을 밝혔습니다. 다음의 식을 조금 더 자세히 살펴보도록 합시다.

일 때,

를 만족합니다. $\hat{\boldsymbol{b}}$는 $A$의 column의 linear combination으로 이루어져 있기 때문에 $A$를

으로 정의하면

을 만족합니다. 이를 조금 더 정리하면

을 만족합니다. $j=1, ..., n$에 대해 성립하므로 이를 matrix와 vector의 곱으로 바꾸면

을 만족합니다. 그런데, $\hat{\boldsymbol{b}}=A\hat{\boldsymbol{x}}$이므로

이 되어

를 만족합니다. 즉 $A\boldsymbol{x}=\boldsymbol{b}$의 least squares problem을 푸는 것은

를 푸는 문제와 같게 됩니다. 여기서 만약 $A^TA$가 invertible하다면 least-squares solution은

로 unique하게 존재합니다.

$A^TA$의 invertibility와 least-squares solution에 관련된 정리는 다음과 같습니다.

Theorem

Let $A$ be an $m\times n$ matrix. The following statements are logically equivalent

1. The equation $A\boldsymbol{x}=\boldsymbol{b}$ has a unique least-squares solution for each $\boldsymbol{b}$ in $\mathbb R^n$
2. The columns of $A$ are linearly independent
3. The matrix $A^TA$ is invertible

When these statements are ture, the least-squares solution of $A\boldsymbol{x}=\boldsymbol{b}$, $\hat{\boldsymbol{x}}$ is given by

example

일 때, $A\boldsymbol x = \boldsymbol b$의 least-squares solution은

를 푸는 것과 같습니다. 따라서 $A^TA$와 $A^T\boldsymbol{b}$를 구하면

해당 matrix의 determinat가 0이 아니므로($17\times 5 - 1 \neq 0$) 해당 matrix는 invertible합니다. 따라서

가 됩니다.

지금까지 least-squares solution에 대해서 알아보았습니다. 다음 포스트에서는 inner product space에 대해 알아보도록 하겠습니다. 질문이나 오류 있으면 댓글 남겨주세요! 감사합니다!

Appendix : Proof of Theorem

Theorem

Let $A$ be an $m\times n$ matrix. The following statements are logically equivalent

1. The equation $A\boldsymbol{x}=\boldsymbol{b}$ has a unique least-squares solution for each $\boldsymbol{b}$ in $\mathbb R^n$
2. The columns of $A$ are linearly independent
3. The matrix $A^TA$ is invertible

• proof

1번 명제와 3번 명제는 동치입니다. 이는 $A\boldsymbol{x}=\boldsymbol{b}$의 least-squares problem을 푸는 것은

를 푸는 것과 같기 때문입니다. 만약 $A^TA$가 invertible하면위 solution은

로 unique하게 존재합니다. 반대의 경우에도, 위 equation이 unique한 solution을 가지면 invertible matrix theorem에 의해 $A^TA$가 invertible 합니다.

다음으로, 2번과 3번이 동치임을 밝혀 위 정리를 증명하겠습니다.

$A^TA$가 invertible하려면, $A^TA$의 column이 linearly independent합니다. 즉 다음의

의 equation이 trivial solution만을 가져야 합니다. 여기서 양변에 $\boldsymbol{x}^T$를 곱하면

을 만족합니다. 이 때 좌변의 식은

이므로 $A^TA\boldsymbol{x}=0$을 만족하는 $\boldsymbol{x}$는

을 만족해야 합니다. 이 때, $A$의 column이 linearly independent하므로 위 식을 만족하는 $\boldsymbol{x}$는

밖에 존재하지 않습니다. 즉

은 trivial solution밖에 가지지 않으므로, $A^TA$의 column이 linearly independent하고, 따라서 $A^TA$가 invertible합니다. 반대 과정 역시 같은 논리로 증명이 가능합니다.