인공지능을 위한 선형대수 - CHAPTER 3.1 Least Squares Problem 소개

www.edwith.org/linearalgebra4ai/lecture/24129/

[LECTURE] Least Squares Problem 소개 : edwith

Over-determined Linear Systems

Linear System에서 방정식의 개수가 미지수가 많은 경우, Over-determined Linear System이라고 부릅니다. 이러한 경우 대개 Solution이 없습니다.

Motivation for Least Squares

Even if no solution exists, we want to approximately obtation the solution for an over-determined system.

 

Then, how can we define the best approximate solution for our purpose?

Properties of Inner Product

Theorem: Let $\mathbf{u}$, $\mathbf{v}$, and $\mathbf{w}$ be vectros in ${\mathbb{R}}^n$, and let $c$ be a scalar.

Then

a) $\mathbf{u}\cdot \mathbf{v}=\mathbf{v}\cdot \mathbf{u}={\mathbf{u}}^T\mathbf{v}$

b) $(\mathbf{u}+\mathbf{v})\cdot \mathbf{w}=\mathbf{u}\cdot \mathbf{w}+\mathbf{v}\cdot \mathbf{w}$

c) $(c\mathbf{u})\cdot \mathbf{v}=c(\mathbf{u}\cdot \mathbf{v})=\mathbf{u}\cdot (c\mathbf{v})$

d) $\mathbf{u}\cdot \mathbf{u}\ge \mathbf{0}$, and $\mathbf{u}\cdot \mathbf{u}=\mathbf{0}$ if and only if $\mathbf{u}=\mathbf{0}$

Vector Norm

Vector의 Norm은 직관적인 의미로 벡터의 길이를 의미합니다.

Definition: The length (or norm) of $\mathbf{v}$ is the non-negative scalar $\Vert \mathbf{v}\Vert$ defined as the square root of $\mathbf{v}\cdot \mathbf{v}$:

$\Vert \mathbf{v}\Vert =\sqrt{\mathbf{v}\cdot \mathbf{v}}$

Properties of Vector Norm

$\Vert c\mathbf{v}\Vert =|c|\Vert \mathbf{v}\Vert$

Unit Vector

A vector whose length is $1$ is called a unit vector.

Normalizing a vector: Given a nonzero vector $\mathbf{v}$, if we divide it by its length, we obtain a unit vector $\mathbf{u}=\frac{1}{\Vert \mathbf{v}\Vert }\mathbf{v}$.

 

$\mathbf{u}$ is the same direction as $\mathbf{v}$, but its length is 1.

Distance between Vectors in ${\mathbb{R}}^n$

Definition: For $mathbfu$ and $mathbfv$ in ${\mathbb{R}}^n$, the distance between $mathbfu$ and $mathbfv$, written as dist $(\mathbf{u},\mathbf{v})$, is the length of the vector $\mathbf{u}-\mathbf{v}$.

That is, dist $(\mathbf{u},\mathbf{v})=\Vert \mathbf{u}-\mathbf{v}\Vert$

 

두 벡터간의 거리는 두 벡터의 차이 벡터의 Norm을 의미합니다.

Inner Product and Angle Between Vectors

Inner product between $\mathbf{u}$ and $\mathbf{v}$ can be rewritten using their norms and angle.

$$\mathbf{u}\cdot \mathbf{v}=\Vert \mathbf{u}\Vert \Vert \mathbf{v}\Vert cos\theta$$

 

Inner Product와 Norm을 알면 두 벡터간의 각도를 구할 수 있습니다.

Orthogonal Vectors

Definition: $\mathbf{u}\in {\mathbb{R}}^n$ and $\mathbf{v}\in {\mathbb{R}}^n$ are orthogonal (to each other) if \(\mathbf{u} \cdot \mathbf{v} = 0\).

That is,

$\mathbf{u}\cdot \mathbf{v}=\Vert \mathbf{u}\Vert \Vert \mathbf{v}\Vert cos\theta =0$.

 

$cos\theta =0$ for nonzero vectors $\mathbf{u}$ and $\mathbf{v}$

$\theta ={90}^{\circ }(\mathbf{u}\perp \mathbf{v})$.

That is, $\mathbf{u}$ and $\mathbf{v}$ are perpendicular each other.

Least Squares: Best Approximation Criterion

Over-determined Linear System $A\mathbf{x}\simeq \mathbf{b}$가 있습니다. 이때, 구하고자 하는 최적의 Solution $\mathbf{x}$에 대한 평가지표로써 Error를 $\Vert \mathbf{b}-A\mathbf{x}\Vert$라고 정의하였을때, 이 Error를 최소화하는 Solution을 찾는 방법이 Least Squares 방법입니다.

 

Definition: Given an over-determined system $A\mathbf{x}\simeq \mathbf{b}$ where $A\in {\mathbb{R}}^{m\times n}$, $\mathbf{b}\in {\mathbb{R}}^n$, and  $m\ll n$, a least squares solution $\hat{\mathbf{x}}$ is defined as

$$\hat{\mathbf{x}}=\underset{x}{\mathrm{argmin}}\Vert \mathbf{b}-A\mathbf{x}\Vert$$

 

The most important aspect of the least-squares problem is that no matter what $\mathbf{x}$ we select, the vector $A\mathbf{x}$ will necessarily be in the column space Col $A$.

 

Thus, we seek for $\mathbf{x}$ that makes $A\mathbf{x}$ as the closest point in Col $A$ to $\mathbf{b}$.