Orthogonal Projections

Projections(투영)은 rotations, reflections과 linear transformations에서 매우 중요한 클래스이며, graphics, coding theory, statistics, machine learning에서 매우 중요한 역할을 합니다. 머신러닝에서는 보통 고차원의 데이터를 다룹니다. 그리고 고차원의 데이터는 시각화하거나 분석하기가 어렵습니다. 그러나 고차원 데이터에서는 몇몇 소수의 차원에 대부분의 정보들이 포함되어 있고 나머지 대부분의 차원에는 불필요한 속성들을 갖는 경우가 많습니다. 고차원의 데이터를 압축하거나 시각화할 때, 정보는 손실됩니다. 이러한 압축 손실(compression loss)를 최소화하기 위해서는 데이터에서 가장 정보를 많이 담고 있는 차원을 찾는 것이 이상적입니다.

1장에서 언급했듯이, 데이터는 벡터로 표현될 수 있고 3.8장에서는 데이터를 압축하는 기본적인 방법을 살펴봅니다. 구체적으로, 원본의 고차원 데이터를 더 낮은 차원의 feature space로 projection하고, 더 낮은 차원의 space에서 데이터셋에 관련하여 학습하고 관련된 패턴을 추출합니다. 예를 들어, PCA 또는 DNN(Deep Neural Network)과 같은 머신러닝 알고리즘은 차원 축소(dimensionality reduction)를 많이 활용합니다.

이번 장에서는 orthogonal projection(정사영)을 중점으로 살펴볼텐데, 이는 10장의 linear dimensionality reduction, 12장의 classification에서 사용됩니다. 9장에서 살펴볼 linear regression에서도 orthogonal projection을 사용하여 해석할 수 있습니다.

주어진 저차원의 subspace에서, 고차원 데이터의 orthogonal projection은 가능한 많은 정보를 유지하고, 원본 데이터와의 차이나 오차를 최소화합니다. 아래 그림은 2차원 데이터를 1차원의 subspace로 orthogonal projection하는 예를 보여줍니다.

Definition 3.10 (Projection). Vector space $V$ 와 $V$ 의 subspace $U \subseteq V$ 가 있을 때, linear mapping $\pi$ 가 $\pi^2 = \pi\circ\pi = \pi$ 를 만족한다면, linear mapping $\pi$ 를 projection 이라고 합니다.

Linear mapping은 transformation matrix로 표현될 수 있기 때문에, linear mapping $\pi$ 는 projection matrices $\boldsymbol{P}_\pi$ 로 표현될 수 있습니다. 그리고 속성 $\pi^2 = \pi\circ\pi = \pi$ 은 $\boldsymbol{P}_\pi^2 = \boldsymbol{P}_\pi$ 를 만족합니다.

Projection onto One-Dimensional Subspaces (Lines)

원본 데이터로부터 Basis vector가 $\boldsymbol{b} \in \mathbb{R}^n$ 인 1차원 subspace인 직선이 주어졌다고 가정해봅시다. 이 직선은 $\boldsymbol{b}$ 에 의해 span되는 1차원 subspace $U \subseteq \mathbb{R}^n$ 입니다. $\boldsymbol{x} \in \mathbb{R}^n$ 을 $U$ 로 projection할 때, 우리는 $\boldsymbol{x}$ 에 가장 가까운 벡터 $\pi_U(\boldsymbol{x}) \in U$ 를 찾습니다. 이때, geometric arguments를 사용하여 projection $\pi_U(\boldsymbol{x})$ 의 속성은 다음과 같습니다.

아래 그림은 설명하는 속성들을 그림으로 보여줍니다.

• Projection $\pi_U(\boldsymbol{x})$ 는 $\boldsymbol{x}$ 와 가장 가깝습니다. 여기서 가장 가깝다는 것은 distance $\|\boldsymbol{x} - \pi_U(\boldsymbol{x})\|$ 가 최소라는 의미입니다. 이는 $\pi_U(\boldsymbol{x}$ 에서 $\boldsymbol{x}$ 까지의 segment $\pi_U(\boldsymbol{x}) - \boldsymbol{x}$ 가 $U$ 에 직교한다는 것을 의미하며, 따라서 basis vector $\boldsymbol{b}$ 와도 직교합니다. 벡터 간의 각도가 내적을 통해 정의되므로, Orthogonality condition은 $\langle\pi_U(\boldsymbol{x}) - \boldsymbol{x}, \boldsymbol{b}\rangle = 0$ 을 만족해야 합니다.
• Projection $\pi_U(\boldsymbol{x})$ 는 반드시 $U$ 의 element 이어야 합니다. 그러므로, basis vector $\boldsymbol{b}$ 로 표현할 수 있으며, $\lambda \in \mathbb{R}$ 에 대해 $\pi_U(\boldsymbol{x}) = \lambda\boldsymbol{b}$ 입니다. (따라서, $\lambda$ 는 $\boldsymbol{b}$ 에 대한 $\pi_U(\boldsymbol{x})$ 의 coordinate, 즉, 좌표입니다)

다음의 3 steps를 통해 coordinate $\lambda$ , projection $\pi_U(\boldsymbol{x}) \in U$ , $\boldsymbol{x} \in \mathbb{R}^n$ 을 $U$ 로 mapping하는 projection matrix $\boldsymbol{P}_\pi$ 를 결정할 수 있습니다.

1. 다음의 orthogonality condition을 통해 coordinate $\lambda$ 를 찾을 수 있습니다.

   \[\langle\boldsymbol{x} -\pi_U(\boldsymbol{x}), \boldsymbol{b}\rangle = 0 {\overset{\pi_U(\boldsymbol{x}) = \lambda\boldsymbol{b}}\Longleftrightarrow} \langle\boldsymbol{x} - \lambda\boldsymbol{b}, \boldsymbol{b}\rangle = 0 \tag{3.39}\]

   내적의 bilinearity(3.2장 참조)를 활용하여 다음의 식을 도출해낼 수 있고,

   \[\langle\boldsymbol{x} - \lambda\boldsymbol{b}, \boldsymbol{b}\rangle = 0 \Longleftrightarrow \lambda = \frac{\langle\boldsymbol{x},\boldsymbol{b}\rangle}{\langle\boldsymbol{b},\boldsymbol{b}\rangle} = \frac{\langle\boldsymbol{b},\boldsymbol{x}\rangle}{\|\boldsymbol{b}\|^2} \tag{3.40}\]

   마지막으로 내적은 symmetric 하다는 사실을 활용합니다. 만약 내적으로 dot product를 사용한다면, 다음의 식을 얻습니다.

   \[\lambda = \frac{\boldsymbol{b}^\top\boldsymbol{x}}{\boldsymbol{b}^\top\boldsymbol{b}} = \frac{\boldsymbol{b}^\top\boldsymbol{x}}{\|\boldsymbol{b}\|^2} \tag{3.41}\]

   만약 $\|b\| = 1$ 이라면, projection의 coordinate $\lambda$ 는 $\boldsymbol{b}^\top\boldsymbol{x}$ 로 주어집니다.

   
   

2. Projection point $\pi_U(\boldsymbol{x}) \in U$ 를 찾습니다. $\pi_U(\boldsymbol{x}) = \lambda\boldsymbol{b}$ 이기 때문에, (3.40)을 통해 다음의 식을 얻을 수 있습니다. 이때, 마지막 등호는 내적이 dot product일 때만 성립합니다.

   \[\pi_U(\boldsymbol{x}) = \lambda\boldsymbol{b} = \frac{\langle\boldsymbol{x},\boldsymbol{b}\rangle}{\|\boldsymbol{b}\|^2}\boldsymbol{b} = \frac{\boldsymbol{b}^\top\boldsymbol{x}}{\|\boldsymbol{b}\|^2}\boldsymbol{b} \tag{3.42}\]

   또한, definition 3.1을 통해 $\pi_U(\boldsymbol{x})$ 의 길이를 다음과 같이 계산할 수 있습니다.

   \[\|\pi_U(\boldsymbol{x})\| = \|\lambda\boldsymbol{b}\| = \begin{vmatrix}\lambda\end{vmatrix}\|\boldsymbol{b}\| \tag{3.43}\]

   그러므로, projection의 길이는 $\boldsymbol{b}$ 의 길이에 $\lambda$ 배 한 것과 같습니다. 그리고, 위 식은 $\lambda$ 는 basis vector $\boldsymbol{b}$ 에 대한 $\pi_U(\boldsymbol{x})$ 의 coordinate라는 것을 보여줍니다.
   만약 내적으로 dot product를 사용한다면, 아래의 식을 얻을 수 있습니다.

   \[\|\pi_U(\boldsymbol{x})\| \overset{(3.42)}= \frac{\begin{vmatrix}\boldsymbol{b}^\top\boldsymbol{x}\end{vmatrix}}{\|\boldsymbol{b}\|^2}\|\boldsymbol{b}\| \overset{(3.25)}= \begin{vmatrix}\cos\omega\end{vmatrix}\|\boldsymbol{x}\|\|\boldsymbol{b}\|\frac{\|\boldsymbol{b}\|}{\|\boldsymbol{b}\|^2} = \begin{vmatrix}\cos\omega\end{vmatrix}\|\boldsymbol{x}\| \tag{3.44}\]

   여기서 $\omega$ 는 $\boldsymbol{x}$ 와 $\boldsymbol{b}$ 사이의 각도(angle) 입니다. 식 (3.44)는 trigonometry와 비슷한데, 만약 $\|x\|=1$ 이라면 $\boldsymbol{x}$ 는 단위 원(unit circle)에 놓여 있으며, 이 때의 projection을 위의 그림 (b) 에서 자세히 보여줍니다.

   
   

3. 마지막으로 proejction matrix $\boldsymbol{P}_\pi$ 를 찾습니다. 우리는 이미 definition 3.10을 통해 projection이 linear mapping이라는 것을 알고 있습니다. 따라서, $\pi_U(\boldsymbol{x}) = \boldsymbol{P}_\pi\boldsymbol{x}$ 를 만족하는 projection matrix $\boldsymbol{P}_\pi$ 가 존재합니다. 내적을 dot product라고 하면, 다음의 식을 통해

   \[\pi_U(\boldsymbol{x}) = \lambda\boldsymbol{b} = \boldsymbol{b}\lambda = \boldsymbol{b}\frac{\boldsymbol{b}^\top\boldsymbol{x}}{\|\boldsymbol{b}\|^2} = \frac{\boldsymbol{bb}^\top}{\|\boldsymbol{b}\|^2}\boldsymbol{x} \tag{3.45}\]

   다음의 projection matrix를 구할 수 있습니다.

   \[\boldsymbol{P}_\pi = \frac{\boldsymbol{bb}^\top}{\|\boldsymbol{b}\|^2} \tag{3.46}\]

   여기서 $\boldsymbol{bb}^\top$ 은 symmetric matrix(rank 1)이며, $\|\boldsymbol{b}\|^2 = \langle\boldsymbol{b},\boldsymbol{b}\rangle$ 은 scalar 입니다.

Projection Matrix $\boldsymbol{P}_\pi$ 는 모든 벡터 $\boldsymbol{x}\in\mathbb{R}^n$ 을 원점을 통과하고 방향이 $\boldsymbol{b}$ 인 직선으로 projection 합니다.

Example 3.10 (Projection onto a Line)
$\boldsymbol{b} = \begin{bmatrix}1&2&2\end{bmatrix}^\top$ 에 의해 span되는 origin에서 line으로 projection하는 projection matrix $\boldsymbol{P}_\pi$ 를 찾아봅시다. $\boldsymbol{b}$ 는 direction이면서 1차원 subspace의 basis 입니다.

식 (3.46)에 의해, 다음과 같이 projection matrix를 구할 수 있습니다.

\[\boldsymbol{P}_\pi = \frac{\boldsymbol{bb}^\top}{\boldsymbol{b}^\top\boldsymbol{b}} = \frac{1}{9}\begin{bmatrix}1\\2\\2\end{bmatrix}\begin{bmatrix}1&2&2\end{bmatrix} = \frac{1}{9}\begin{bmatrix}1&2&2\\2&4&4\\2&4&4\end{bmatrix} \tag{3.47}\]

이제 특정 $\boldsymbol{x}$ 를 선택하고, 이 벡터가 $\boldsymbol{b}$ 에 의해 span되는 subspace에 있는 line에 놓이는지 확인해보도록 하겠습니다. $\boldsymbol{x} = \begin{bmatrix}1&1&1\end{bmatrix}^\top$ 에 대한 projection은 다음과 같습니다.

\[\pi_U(\boldsymbol{x}) = \boldsymbol{P}_\pi\boldsymbol{x} = \frac{1}{9}\begin{bmatrix}1&2&2\\2&4&4\\2&4&4\end{bmatrix}\begin{bmatrix}1\\1\\1\end{bmatrix} = \frac{1}{9}\begin{bmatrix}5\\10\\10\end{bmatrix} \in \text{span}\lbrack\begin{bmatrix}1\\2\\2\end{bmatrix}\rbrack \tag{3.48}\]

여기서 $\pi_U(\boldsymbol{x})$ 에 $\boldsymbol{P}_\pi$ 를 적용해도 아무것도 변경하지 않습니다. 즉, $\boldsymbol{P}_\pi\pi_U(\boldsymbol{x}) = \pi_U(\boldsymbol{x})$ 이며, 이는 definition 3.10에 따라 $\boldsymbol{P}_\pi^2\boldsymbol{x} = \boldsymbol{P}_\pi\boldsymbol{x}$ 이기 때문입니다.

Projection onto General Subspaces

이번에는 1차원이 아닌 1 이상인 m 차원 subspace $U \in \mathbb{R}^n$ 에 orthogonal projection 하는 경우를 살펴보도록 하겠습니다. 아래 그림은 3차원 데이터를 2차원으로 projection하는 것을 보여줍니다.

$U$ 의 ordered basis를 $(\boldsymbol{b}_1,\dotsc,\boldsymbol{b}_m)$ 이라고 가정합시다. 모든 $U$ 로의 projection $\pi_U(\boldsymbol{x})$ 는 필연적으로 $U$ 의 element 입니다. 따라서, $U$ 의 basis vector $\boldsymbol{b}_1,\dotsc,\boldsymbol{b}_m$ 의 linear combination으로 다음과 같이 표현할 수 있습니다.

\[\pi_U(\boldsymbol{x}) = \sum_{i=1}^m\lambda_i\boldsymbol{b}_i\]

1차원의 subspace로 projection하는 경우와 마찬가지로 projection $\pi_U(\boldsymbol{x})$ 와 projection matrix $\boldsymbol{P}_\pi$ 를 다음의 3 단계를 통해 구할 수 있습니다.

1. Projection의 coordinates $\lambda_1,\dotsc,\lambda_m$ 을 찾습니다. 아래의 linear combinations 는

   \[\begin{align*}&\pi_U(\boldsymbol{x}) = \sum_{i = 1}^m\lambda_i\boldsymbol{b}_i = \boldsymbol{B\lambda} \tag{3.49} \\ &\boldsymbol{B} = \lbrack\boldsymbol{b}_1,\dotsc,\boldsymbol{b}_m\rbrack\in\mathbb{R}^{n \times m}, \quad \boldsymbol{\lambda} = \lbrack\lambda_1,\dotsc,\lambda_m\rbrack^\top \in \mathbb{R}^m \tag{3.50} \end{align*}\]

   $\boldsymbol{x}$ 에서 가장 가깝습니다. 1차원의 케이스처럼, 가깝다라는 것은 ‘minimum distance’를 의미하며, $\pi_U(\boldsymbol{x}) \in U$ 와 $\boldsymbol{x} \in \mathbb{R}^n$ 을 연결하는 모든 벡터는 $U$ 의 basis vectors와 직교(orthogonal)합니다. 따라서, 동시에 만족해야 하는 m개의 조건들을 얻습니다. 여기서 내적은 dot product라고 가정합니다.

   \[\begin{align*} \langle\boldsymbol{b}_1, \boldsymbol{x} - \pi_U(\boldsymbol{x})\rangle &= \boldsymbol{b}_1^\top(\boldsymbol{x}-\pi_U(\boldsymbol{x})) = 0 \tag{3.51} \\ \vdots \\ \langle\boldsymbol{b}_m, \boldsymbol{x} - \pi_U(\boldsymbol{x})\rangle &= \boldsymbol{b}_m^\top(\boldsymbol{x}-\pi_U(\boldsymbol{x})) = 0 \tag{3.52} \end{align*}\]

   $\pi_U(\boldsymbol{x}) = \boldsymbol{B\lambda}$ 이므로, 위 식은 다음과 같이 쓸 수 있습니다.

   \[\begin{align*} \boldsymbol{b}_1^\top(\boldsymbol{x} - \boldsymbol{B\lambda}) &= 0 \tag{3.53} \\ \vdots \\ \boldsymbol{b}_m^\top(\boldsymbol{x} - \boldsymbol{B\lambda}) &= 0 \tag{3.54} \end{align*}\]

   라서, 다음의 homogeneous linear equation system을 얻을 수 있습니다.

   \[\begin{align*} \begin{bmatrix}\boldsymbol{b}_1^\top\\\vdots\\\boldsymbol{b}_m^\top\end{bmatrix}\begin{bmatrix}\boldsymbol{x}-\boldsymbol{B\lambda}\end{bmatrix} = 0 &\Longleftrightarrow \boldsymbol{B}^\top(\boldsymbol{x} - \boldsymbol{B\lambda}) = 0 \tag{3.55} \\ &\Longleftrightarrow \boldsymbol{B}^\top\boldsymbol{B\lambda} = \boldsymbol{B}^\top\boldsymbol{x} \tag{3.56} \end{align*}\]

   여기서 마지막 표현식을 normal equation 이라고 부릅니다. $\boldsymbol{b}_1, \dotsc,\boldsymbol{b}_m$ 은 $U$ 의 basis 이고, 따라서 linearly independent 이기 때문에 $\boldsymbol{B}^\top\boldsymbol{B} \in \mathbb{R}^{m\times m}$ 은 regular 이며 역행렬이 존재합니다. 따라서, coordiante를 다음과 같이 구할 수 있습니다.

   \[\boldsymbol{\lambda} = (\boldsymbol{B}^\top\boldsymbol{B})^{-1}\boldsymbol{B}^\top\boldsymbol{x} \tag{3.57}\]

   $(\boldsymbol{B}^\top\boldsymbol{B})^{-1}\boldsymbol{B}^\top$ 행렬은 $\boldsymbol{B}$ 의 pseudo-inverse(유사 역행렬)이라고도 하며, 정사각 행렬이 아닌 행렬에 대해서도 계산할 수 있습니다. 유사 역행렬을 사용할 수 있는 유일한 조건은 $\boldsymbol{B}^\top\boldsymbol{B}$ 가 positive definite 해야한다는 것인데, 이는 $\boldsymbol{B}$ 가 full rank이어야 한다는 것을 의미합니다.

   
   

2. 다음으로 Prjoection $\pi_U(\boldsymbol{x}) \in U$ 를 찾습니다. $\pi_U(\boldsymbol{x}) =\boldsymbol{B\lambda}$ 라는 것을 알고 있기 때문에, 식 (3.57)로부터 다음과 같이 구할 수 있습니다.

   \[\pi_U(\boldsymbol{x}) = \boldsymbol{B}(\boldsymbol{B}^\top\boldsymbol{B})^{-1}\boldsymbol{B}^\top\boldsymbol{x} \tag{3.58}\]

   
   

3. Projection matrix $\boldsymbol{P}_\pi$ 를 찾습니다. 식 (3.58)로부터 $\boldsymbol{P}_\pi\boldsymbol{x} = \pi_U(\boldsymbol{x})$ 를 풀면 간단하게 projection matrix를 찾을 수 있습니다.

   \[\boldsymbol{P}_\pi = \boldsymbol{B}(\boldsymbol{B}^\top\boldsymbol{B})^{-1}\boldsymbol{B}^\top \tag{3.59}\]

Example 3.11 (Projection onto a Two-dimensional Subspace)

Subspace $U = \text{span}\lbrack\begin{bmatrix}1\\1\\1\end{bmatrix},\begin{bmatrix}0\\1\\2\end{bmatrix}\rbrack \in \mathbb{R}^3$ 과 $\boldsymbol{x} = \begin{bmatrix}6\\0\\0\end{bmatrix} \in \mathbb{R}^3$ 이 있을 때, $\boldsymbol{x}$ 의 coordinate $\boldsymbol{\lambda}$ 와 projection point $\pi_U(\boldsymbol{x})$ , projection matrix $\boldsymbol{P}_\pi$ 를 단계별로 찾아보도록 하겠습니다.

첫 번째, $U$ 의 generating set이 basis(linear independence)이라는 것을 볼 수 있고, $U$ 의 basis vector를 행렬 $\boldsymbol{B} = \begin{bmatrix}1&0\\1&1\\1&2\end{bmatrix}$ 로 쓸 수 있습니다.

두 번째, $\boldsymbol{B}^\top\boldsymbol{B}$ 와 $\boldsymbol{B}^\top\boldsymbol{x}$ 를 다음과 같이 계산할 수 있습니다.

\[\boldsymbol{B}^\top\boldsymbol{B} = \begin{bmatrix}1&1&1\\0&1&2\end{bmatrix}\begin{bmatrix}1&0\\1&1\\1&2\end{bmatrix} = \begin{bmatrix}3&3\\3&5\end{bmatrix}, \quad \boldsymbol{B}^\top\boldsymbol{x} = \begin{bmatrix}1&1&1\\0&1&2\end{bmatrix}\begin{bmatrix}6\\0\\0\end{bmatrix} = \begin{bmatrix}6\\0\end{bmatrix} \tag{3.60}\]

세 번째, $\boldsymbol{\lambda}$ 를 찾기 위해 normal equation $\boldsymbol{B}^\top\boldsymbol{B\lambda} = \boldsymbol{B}^\top\boldsymbol{x}$ 를 풀면 됩니다.

\[\begin{bmatrix}3&3\\3&5\end{bmatrix}\begin{bmatrix}\lambda_1\\\lambda_2\end{bmatrix} = \begin{bmatrix}6\\0\end{bmatrix} \Longleftrightarrow \boldsymbol{\lambda} = \begin{bmatrix}5\\-3\end{bmatrix} \tag{3.61}\]

네 번째로, 식 (3.49)를 통해 $U$ 로의 projection $\pi_U(\boldsymbol{x})$ 를 찾습니다.

\[\pi_U(\boldsymbol{x}) = \boldsymbol{B\lambda} = \begin{bmatrix}5\\2\\-1\end{bmatrix} \tag{3.62}\]

여기서 projection error 는 original vector와 projection point 간 difference vector의 norm 이며, 다음과 같이 계산됩니다.

\[\|\boldsymbol{x} - \pi_U(\boldsymbol{x})\| = \left\|\begin{bmatrix}1&-2&1\end{bmatrix}^\top\right\| = \sqrt{6} \tag{3.63}\]

다섯 번째, 식 (3.59)를 통해 projection matrix를 구합니다.

\[\boldsymbol{P}_\pi = \boldsymbol{B}(\boldsymbol{B}^\top\boldsymbol{B})^{-1}\boldsymbol{B}^\top = \frac{1}{6}\begin{bmatrix}5&2&-1\\2&2&2\\-1&2&5\end{bmatrix} \tag{3.64}\]

결과를 검증하기 위해, (a) displacement vector $\pi_U(\boldsymbol{x}) -\boldsymbol{x}$ 가 $U$ 의 모든 basis vector에 직교하는지 확인하고, (b) $\boldsymbol{P}_\pi = \boldsymbol{P}_\pi^2$ (definition 3.10)을 만족하는지 확인하면 됩니다.

Projection은 해가 없는 선형 시스템 $\boldsymbol{Ax} = \boldsymbol{b}$ 에서 사용될 수 있습니다. 해가 없다는 것은 $\boldsymbol{b}$ 가 $\boldsymbol{A}$ 의 span 상에 놓여있지 않다는 것을 의미합니다. 즉, 벡터 $\boldsymbol{b}$ 는 $\boldsymbol{A}$ 의 columns에 의해 span되는 subspace에 놓여있지 않다는 것입니다. 주어진 선형 시스템을 정확히 풀 수 없을 때에는 approximate solution(근사해)를 찾을 수 있습니다. 근사해를 구하는 핵심 아이디어는 $\boldsymbol{b}$ 와 가장 가까이 있는 $\boldsymbol{A}$ 의 columns에 의해 span되는 subspace에서 찾는 것입니다. 즉, $\boldsymbol{A}$ 의 columns에 의해 span되는 subspace에 대한 $\boldsymbol{b}$ 의 orthogonal projection을 계산하는 것입니다. 이러한 문제는 실제로도 자주 발생하며, 이러한 해를 least-squars solution of an overdetermined system 이라고 합니다 (내적을 dot product라고 가정). 이에 대한 내용은 9.4장에서 조금 더 살펴봅니다.

Gram-Schmidt Orthogonalization

Gram-Schmidt method는 n-차원 vector space $V$ 의 어떠한 basis $(\boldsymbol{b}_1,\dotsc,\boldsymbol{b}_n)$ 을 orthogonal/orthonormal basis $(\boldsymbol{u}_1,\dotsc,\boldsymbol{u}_n)$ 으로 변환할 수 있도록 해줍니다. 이렇게 변환된 basis는 항상 존재하며, $\text{span}\lbrack\boldsymbol{b}_1,\dotsc,\boldsymbol{b}_n\rbrack = \text{span}\lbrack\boldsymbol{u}_1,\dotsc,\boldsymbol{u}_n\rbrack$ 입니다.

Gram-Schmidt orthogonalization method는 다음과 같이 orthogonal basis $(\boldsymbol{u}_1,\dotsc,\boldsymbol{u}_n)$ 를 구합니다.

\[\begin{align*} \boldsymbol{u}_1 &:= \boldsymbol{b}_1 \tag{3.67} \\ \boldsymbol{u}_k &:= \boldsymbol{b}_k - \pi_{\text{span}\lbrack\boldsymbol{u}_1,\dotsc,\boldsymbol{u}_{k-1}\rbrack}(\boldsymbol{b}_k), \quad k = 2,\dotsc,n \tag{3.68} \end{align*}\]

(3.68) 식에서 k번째 basis vector $\boldsymbol{b}_k$ 는 이전에 구한 k-1개의 orthogonal vector $\boldsymbol{u}_1,\dotsc,\boldsymbol{u}_{k-1}$ 에 의해 span되는 subspace에 projection 됩니다 ($\pi_{\text{span}\lbrack\boldsymbol{u}_1,\dotsc,\boldsymbol{u}_{k-1}\rbrack}(\boldsymbol{b}_k)$). 그런 다음 $\boldsymbol{b}_k$ 에서 이 projection을 빼서 $\boldsymbol{u}_k$ 를 구합니다. 결과적으로 $\boldsymbol{u}_k$ 는 $\boldsymbol{u}_1,\dotsc,\boldsymbol{u}_{k-1}$ 에 의해 span되는 (k-1) 차원의 subspace에 직교(orthogonal) 합니다. 이 과정을 모든 n개의 basis vector $\boldsymbol{b}_1,\dotsc,\boldsymbol{b}_n$ 에 대해 반복하여 orthogonal basis $(\boldsymbol{u}_1,\dotsc,\boldsymbol{u}_n)$ 를 구합니다. $\boldsymbol{u}_k$ 를 정규화(normalization)하면, ONB(orthonormal basis)를 구할 수 있습니다 ($\|\boldsymbol{u}_k\| = 1$ ).

Example 3.12 (Gram-Schmidt Orthogonalization)

위 그림의 (a)와 같이 $\mathbb{R}^2$ 의 basis $(\boldsymbol{b}_1,\boldsymbol{b}_2)$ 가 다음과 같을 때,

\[\boldsymbol{b}_1 = \begin{bmatrix}2\\0\end{bmatrix}, \quad \boldsymbol{b}_2 = \begin{bmatrix}1\\1\end{bmatrix} \tag{3.69}\]

Gram-Schmidt 방법을 통해 계산된 orthogonal basis $(\boldsymbol{u}_1, \boldsymbol{u}_2)$ 는 다음과 같습니다. 여기서 내적은 dot product라고 가정합니다.

\[\begin{align*} \boldsymbol{u}_1 &:= \boldsymbol{b}_1 = \begin{bmatrix}2\\0\end{bmatrix} \tag{3.70} \\ \boldsymbol{u}_2 &:= \boldsymbol{b}_2 - \pi_{\text{span}\lbrack\boldsymbol{u}_1\rbrack}(\boldsymbol{b}_2) \overset{(3.45)}= \boldsymbol{b}_2 - \frac{\boldsymbol{u}_1\boldsymbol{u}_1^\top}{\|\boldsymbol{u}_1\|}\boldsymbol{b}_2 = \begin{bmatrix}1\\1\end{bmatrix} - \begin{bmatrix}1&0\\0&0\end{bmatrix}\begin{bmatrix}1\\1\end{bmatrix} = \begin{bmatrix}0\\1\end{bmatrix} \tag{3.71} \end{align*}\]

이 과정을 위 그림의 (b), (c)에서 보여주고 있습니다. 그림을 통해 $\boldsymbol{u}_1$ 과 $\boldsymbol{u}_2$ 가 서로 직교한다는 것을 알 수 있으며, 따라서, $\boldsymbol{u}_1^\top\boldsymbol{u}_2 = 0$ 입니다.

Projection onto Affine Subspaces

이번에는 벡터를 affine space에 projection하는 방법을 살펴보도록 하겠습니다.

위 그림의 (a)를 살펴봅시다. Affine space $L = \boldsymbol{x}_0 + U$ 가 주어져 있으며, $U$ 의 basis vector는 $\boldsymbol{b}_1, \boldsymbol{b}_2$ 입니다. $L$ 에 투영되는 $\boldsymbol{x}$ 의 orthogonal projection $\pi_L(\boldsymbol{x})$ 를 구하기 위해서, 이 문제를 vector subspace에 투영하는 문제로 변형하여 쉽게 풀 수 있습니다. 그림 (b)에서 보여주는 것처럼 $\boldsymbol{x}$ 와 $L$ 에 support point $\boldsymbol{x}_0$ 를 빼주면 vector subspace $U = L - \boldsymbol{x}_0$ 을 얻을 수 있습니다. 이제 3.8.2장에서 살펴 본 방법을 사용하여 projection $\pi_U(\boldsymbol{x} -\boldsymbol{x}_0)$ 을 얻을 수 있습니다. 얻은 projection은 다시 $\boldsymbol{x}_0$ 을 더해 $L$ 로 변환될 수 있으므로, 다음과 같이 affine space $L$ 로의 orthogonal projection을 얻을 수 있습니다.

\[\pi_L(\boldsymbol{x}) = \boldsymbol{x}_0 + \pi_U(\boldsymbol{x}-\boldsymbol{x}_0) \tag{3.72}\]

여기서 $\pi_U(\cdot)$ 은 subspace $U$ 로의 orthogonal projection이며, 그림 (c)에서 보듯이 $L$ 의 direction space 입니다.

Figure 3.13 (c)로부터, affien space $L$ 와 $\boldsymbol{x}$ 의 distance는 $U$ 와 $\boldsymbol{x}-\boldsymbol{x}_0$ 사이의 distance와 같다는 것을 알 수 있으며, 식으로 표현하면 다음과 같습니다.

\[\begin{align*} d(\boldsymbol{x},L) &= \|\boldsymbol{x} -\pi_L(\boldsymbol{x})\| = \|\boldsymbol{x} - (\boldsymbol{x}_0 + \pi_U(\boldsymbol{x}-\boldsymbol{x}_0))\| \tag{3.73a} \\ &= d(\boldsymbol{x}-\boldsymbol{x}_0, \pi_U(\boldsymbol{x}-\boldsymbol{x}_0)) \tag{3.73b} \end{align*}\]

12.1장에서는 separting hyperplane의 개념을 유도하기 위해 affine subspace로의 projection을 사용합니다.