인공지능을 위한 선형대수 - 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} \geq \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 \(\| \mathbf{v} \|\) defined as the square root of \(\mathbf{v} \cdot \mathbf{v}\):

\(\| \mathbf{v} \| = \sqrt{\mathbf{v} \cdot \mathbf{v}} \)

Properties of Vector Norm

\(\| c\mathbf{v} \| = |c|  \| \mathbf{v} \| \)

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}{\| \mathbf{v} \|} \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 \(mathbf{u}\) and \(mathbf{v}\) in \(\mathbb{R}^{n}\), the distance between \(mathbf{u}\) and \(mathbf{v}\), written as dist \((\mathbf{u}, \mathbf{v})\), is the length of the vector \(\mathbf{u}-\mathbf{v}\).

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

 

두 벡터간의 거리는 두 벡터의 차이 벡터의 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} =  \| \mathbf{u} \| \| \mathbf{v} \| 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} =  \| \mathbf{u} \| \| \mathbf{v} \| 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를 \(\|\mathbf{b}-A\mathbf{x}\|\)라고 정의하였을때, 이 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}} \|\mathbf{b}-A\mathbf{x}\|$$

 

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}\).