[제대로된 선형대수] Week 3-01 The Projection Theorem

영상 링크: https://www.youtube.com/watch?v=1y8NFtrPEWg

해당 글은 위 영상 링크의 내용을 토대로 작성한 것입니다.
좋은 컨텐츠를 제작하고 공유해주신 훈러닝님 감사합니다.

 

우린 임의 벡터 $v \in V$ 가 있을 때, $S$ 와 거리가 가장 짧은 $w \in S$ (= $\left \| v -w \right \|$ 의 최소값) 를 찾는다.

벡터 $v-w$ 와 $w$ 사이의 각도가 90도일 때, 거리가 제일 짧아진다.

다시 말해, 벡터 $v-w$ 와 any other 벡터 $\in S$ 와 직교해야한다.

 

<Formulation>

$w = argmin_{z \in S} \left \| v - z \right \| \rightleftharpoons \left \| v - w\right \| \leq \left \| v - z\right \| \; \forall z \in S$

$\to$ 이 때 $w$ 를 "Projection of $V$ onto $S$" ($Proj_S V$) 라 부름. 때때로 "Best approximation" 이라고도 부름.

 

"$w$ (=$Proj_S V$) always exists and is characterised by orthogonality condition."

 

Thrm 289. The Projection Theorem

$V:$ Inp. / $\mathbb{R}$, finite $S \subset V$

1. $\forall v \in V, \; \exists ! w \in S \; s.t. \; \left \| v - w \right \| \leq \left \| v - z \right \| \; \forall z \in S$

  $\to w = Proj_{S}V$

  which is...

  ① Best approximation from $V$ to $S$

  ② Orthogonal projection of $V$ onto $S$

 

2. $w = Proj_{S}V \; \; \mathrm{iff} \left < v - w, z \right > = 0 \; \forall z \in S$

 

3. $S = sp\left \{ u_1, \cdots, u_n \right \} \to Proj_{S}V = \sum_{i=1}^{n} x_i u_i$

  이 때, $X = \left [ x_1, \cdots, x_n \right ]^{\top} \; \mathrm{satisfies} \; GX = b$

  $\ast \; G_{ij} = \left < u_j, u_i \right >, b_i = \left < v, u_i \right >$

 

pf 2)

Fix $w \in S$

"Any other vector in $S$" can be written as $y = w + tz$ for some $t \in \mathbb{R}, z \in S$

$y \in S \rightleftharpoons y = w + tz \left ( t \in \mathbb{R}, z \in S \right )$

  $\left ( \Leftarrow \right )$ $w \left ( \in S \right ) + tz \left ( \in S \right ) \Rightarrow w + tz \in S \to y \in S$

  $\left ( \Rightarrow \right )$ $y \in S$, $t=1, z = y - w \to w + tz = w + 1 \cdot \left ( y - w \right ) = y$

$\ast$ 위 과정을 보여준 이유는 Thrm 289 의 2번에서 $z$ 를 $w + tz$ 로 바꿔서 사용하기 위해서

 

$\left \| v - z \right \|^2 = \left \| v - \left ( w + tz \right ) \right \|^2 = \left < \left ( v - w \right) - tz, \left ( v - w \right) - tz \right >$ (by Thrm 269)

                                       $= \left \| v - w \right \|^2 + t^2 \left \| z \right \|^2 - 2t \left < v-w, z \right >$

 

$\phi \left ( t \right ) = t^2 \left \| z \right \|^2 - 2t \left < v-w, z \right >$

For $\left \| v - z \right \|^2 \geq \left \| v - w \right \|^2$, 항상 should $\phi \geq 0$ $\Rightarrow$ so, $\left < v-w, z \right > = 0$

 

We can say

$\left \| v-z \right \|^2 \geq \left \| v-w \right \|^2 \rightleftharpoons \phi \left ( t \right ) \geq 0 \; \forall t$

                              $\rightleftharpoons \left < v - w, z \right > = 0$ (orthogonal condition) $\square$

 

pf 3)

① $S = sp\left \{ u_1, \cdots, u_n \right \}$

    WTS $\left < v-w, z \right > = 0 \; \forall z \in S \rightleftharpoons \left < v-w, u_i \right > = 0$

    $\left < v-w, \alpha_1 u_1 + \cdots + \alpha_n u_n \right >$

    $=\alpha_1 \left < v-w, u_1 \right > + \cdots \alpha_n \left < v-w, u_n \right > = 0$

    그런데 $\left \{ u_1, \cdots, u_n \right \} \in S$ 이므로

    $\left < v-w, u_1 \right > = 0$

             $\vdots$

    $\left < v-w, u_n \right > = 0$

    (by orthogonal condition.)

 

② $G_{ij} = \left < u_j, u_i \right >, b_i = \left < v, u_i \right >$

    $w \in S, w = \sum_{j = 1}^{n} x_ju_j$

    $\left < v-w, u_i \right > = 0$

    $\Rightarrow \left < v - \sum_{j = 1}^{n} x_ju_j, \; u_i \right > = 0$

    $\rightleftharpoons \sum_{j=1}^{n} x_j \left < u_j, u_i \right > = \left < v, u_i \right >$

    $\to G_{i} X = b_i$

    $\Rightarrow GX =b$ $\square$

 

pf 1)

그런데 $G$ 는 invertible 해서 (by Thrm 273) $X = G^{-1}b$

이 때, $X$ 는 unique 하기 때문에 $w = \sum_{j=1}^{n} x_ju_j$ 도 unique 하다. $\square$

 

 

Overdetermined Linear Systems $\left ( m > n \right )$

 

$T: \mathbb{R}^n \to \mathbb{R}^m \; s.t. \; T\left ( x \right ) = Ax \left ( A \in \mathbb{R}^{m \times n} \right )$

($\mathbb{R}^n, \: \mathbb{R}^m:$ Inp. 를 dot product 로 정의)

$y \in \mathbb{R}^m, Ax \in col\left ( A \right )$ (column space of A)

 

WTF $Proj_{col\left ( A \right )} y \in col\left ( A \right )$

 

 1) $Proj_{col\left ( A \right )} y$ 를 찾는 문제

      = $Ax = y$ 의 Least Squares Solution 의 $x$ 를 찾는 문제$^\ast$

 2) Such $Ax = Proj_{col\left ( A \right )} y$ uniquely exists (by the projection theorem)

 

$\ast$ 왜?

우선 $Proj_{col\left ( A \right )} y$ 에서 $y$ 를 $v$, $col(A)$ 를 $w \in S$ 로 생각할 수 있다.

사실 $Proj_{col\left ( A \right )} y$ 를 찾는다는 말은 $col(A) = Ax$ 로서 $\left \| y - Ax \right \|$ 가 최소일 때를 찾겠다는 의미와 같다.

LO 인 $A$ 는 고정되어 있기 때문에 $\left \| y- Ax \right \|$ 가 최소일 때의 $x$ 를 찾는다는 의미로 귀결된다.

그런데 여기서 $\left \| y - Ax \right \|$ 에 대한 square 의 least 값을 구하기 때문에, $Ax = y$ 의 Least Squares Solution 의 $x$ 를 찾는 문제라 할 수 있다.

 

 

Thrm 291. $x = argmin\left \{ \left \| y - Az \right \|_{2}^{2} \; | \; z \in \mathbb{R}^n \right \} \rightleftharpoons A^{\top}Ax = A^{\top}y$

  1. Inp. 가 dot product 로 정의되어 subscript 가 2 로 설정되었다.

  2. argmin & superscript 2 로 인해 least squares 를 찾는 문제가 되었다.

 

pf) $Ax = Proj_{col\left ( A \right )} y$ $\left ( \rightleftharpoons x = argmin \left \| y - Ax \right \|_2^2 \right )$

  $\rightleftharpoons \left ( y - Ax \right ) \cdot z = 0 \; \forall z \in col\left ( A \right )$ (by Thrm 289) (현재 Inp. 가 dot product 로 정의됨에 따라 표현이 바뀜)

  $\rightleftharpoons \left ( y - Ax \right ) \cdot Au = 0 \; \forall u \in \mathbb{R}^n$

  $\rightleftharpoons A^{\top} \left ( y-Ax \right ) \cdot u = 0 \; \forall u \in \mathbb{R}^n$ (by Thrm 270)

  $\to A^{\top} \left ( y - Ax \right ) = 0$

  $\Rightarrow A^{\top}y = A^{\top}Ax$

$\therefore$ $Ax = Proj_{col\left ( A \right )} y$ 일 때, 즉 $Ax = y$ 의 least squares 일 때, $A^{\top}y = A^{\top}Ax$ 이며 역일 때도 성립한다. $\square$

 

$\left ( + \alpha \right )$ $A$ 가 full rank (Def 101) $\to$ $A^{\top}A$ nonsingular / invertible $\to$ $X = \left ( A^{\top}A \right )^{-1} A^{\top} y$

        $A^{\top}A$ 가 singular 하더라도 Projection theorem 에 의해 $Ax$ 는 unique 하다. 하지만 $X$ 는 unique 하지 못한다.

 

 

Video watch on 2023. 03. 27.
Last update: 2023. 04. 21.
Written by Taejun Lim

 

복습

1. 2023/05/30