Singular Value Decomposition

행렬의 singular value decomposition(SVD, 특잇값 분해)는 선형대수학에서 중심이 되는 matrix decomposition method 입니다. 이는 square matrix뿐만 아니라 모든 행렬에 대해 적용할 수 있고, 항상 존재하기 때문에 ‘fundamental theorem of linear algebra’ 라고 불립니다. 또한, linear mapping $\Phi: V\rightarrow W$ 을 나타내는 행렬 $\boldsymbol{A}$ 의 SVD는 두 vector spaces의 기하학적 변화를 정량화합니다.

Theorem 4.22 (SVD Theorem). 행렬 $\boldsymbol{A}\in\mathbb{R}^{m\times n}$ 가 rank $r \in \lbrack0, \min(m, n)\rbrack$ 인 rectangular matrix라 할 때, $\boldsymbol{A}$ 의 SVD는 아래 형태의 decomposition 입니다.

이때, $\boldsymbol{U} \in \mathbb{R}^{m\times m}$ 는 column vectors $\boldsymbol{u}_i, i=1,\dotsc,m$ 의 orthogonal matrix 이며, $\boldsymbol{V}\in\mathbb{R}^{n\times n}$ 은 column vectors $\boldsymbol{v}_j, j = 1,\dotsc,n$ 의 orthogonal matrix 입니다. 또한, $\Sigma$ 는 $\Sigma_{ii} = \sigma_i \geq 0$ 이고 $\Sigma_{ij} = 0, i\neq j$ 인 $m \times n$ 행렬입니다.

$\Sigma$ 의 대각 요소 $\sigma_i$ 는 singular values 라 부르고, $\boldsymbol{u}_i$ 는 left-singular vectors, $\boldsymbol{v}_i$ 는 right-singular vectors 이라고 부릅니다. 그리고 관습적으로, singular value들은 크기 순으로 정렬하여 표기합니다 ($\sigma_1 \geq \sigma_2 \geq \sigma_r \geq 0$).

Singular value matrix $\Sigma$ 는 유일합니다. 다만, 몇 가지 주의할 점이 있습니다. $\Sigma$ 는 rectangular matrix이고 $\boldsymbol{A}$ 와 크기가 같습니다. 이는 diagonal submatrix가 singular values를 포함하면서 추가적인 zero-padding이 필요하다는 것을 의미합니다.

조금 더 구체적으로 $m > n$ 인 경우, 행렬 $\Sigma$ 는 대각 성분은 n행까지 존재하고, n+1부터 m행까지는 $\boldsymbol{0}^\top$ row vector로 구성됩니다.

\[\Sigma = \begin{bmatrix}\sigma_1&0&0\\0&\ddots&0\\0&0&\sigma_n\\0&\cdots&0\\\vdots&&\vdots\\0&\cdots&0\end{bmatrix} \tag{4.65}\]

반대로 $m < n$ 인 경우에는 m열까지만 대각 성분이 존재하고 m+1열부터 n열 까지는 $\boldsymbol{0}$ 으로 구성됩니다.

\[\Sigma = \begin{bmatrix}\sigma_1&0&0&0&\cdots&0\\0&\ddots&0&0&&0\\0&0&\sigma_m&0&\cdots&0\end{bmatrix} \tag{4.66}\]

Geometric Intuitions for the SVD

SVD는 transformation matrix $\boldsymbol{A}$ 를 기하학적으로 설명해줍니다. 지금부터 basis에 대해 수행되는 sequential linear transformation으로서 SVD를 살펴봅니다. Example 4.12에서는 SVD의 transformation matrices를 $\mathbb{R}^2$ 의 벡터 집합에 적용하여 각 변화의 효과를 시각화해보도록 하겠습니다.

행렬의 SVD는 linear mapping(2.7.1장) $\Phi: \mathbb{R}^n\rightarrow \mathbb{R}^m$ 의 분해를 아래 그림 Figure 3.8에서 보는 것과 같이 3개의 operations로 해석할 수 있습니다.

SVD의 기하학적 직관은 표면적으로 eigendecomposition(4.4장)과 유사한 구조를 갖고 있습니다. 대락적으로 말하자면, SVD는 $\boldsymbol{V}^\top$ 을 통해 basis change(2.7.2장)를 수행한 다음, singular value matrix $\Sigma$ 를 통해 차원의 scaling과 augmentation(or reduction)을 수행합니다. 그리고 마지막으로 $\boldsymbol{U}$ 를 통해 2번째 basis change를 수행합니다.

그렇다면 이제 조금 더 자세히 살펴보도록 하겠습니다.

$\mathbb{R}^n$ 과 $\mathbb{R}^m$ 의 standard basis $B, C$ 에 대한 linear mapping $\Phi: \mathbb{R}^n \rightarrow \mathbb{R}^m$ 의 transformation matrix가 주어졌다고 가정해보겠습니다. 또한, $\tilde{B}$ 는 $\mathbb{R}^n$ 의 second basis, $\tilde{C}$ 는 $\mathbb{R}^m$ 의 second basis라고 가정합니다.

1. 행렬 $\boldsymbol{V}$ 는 domain $\mathbb{R}^n$ 에서 $\tilde{B}$ (Figure 4.8의 왼쪽 위 그림 red/orange vectors) 로부터 $B$ 로의 basis change를 수행합니다. $\boldsymbol{V}^\top=\boldsymbol{V}^{-1}$ 은 $B$ 에서 $\tilde{B}$ 로의 basis change를 수행합니다. 이를 통해 Figure 4.8의 왼쪽 아래 그림에서 red/orange vectors가 canonical basis로 정렬됩니다.
2. 좌표계를 $\tilde{B}$ 로 변경한 뒤, $\Sigma$ 는 새로운 좌표를 singular values $\sigma_i$ 만큼 scaling 하고 차원을 더하거나 뺍니다. 즉, $\Sigma$ 는 $\tilde{B}$ 와 $\tilde{C}$ 에 대한 transformation matrix 입니다. 이를 Figure 4.8의 오른쪽 아래 그림에서 보여주고 있습니다. red/orange vectors가 scaling 되고, $\boldsymbol{e}_1-\boldsymbol{e}_2$ 평면에 놓여 있는 것을 볼 수 있으며, 2차원이 아닌 3차원으로 변경되었습니다.
3. $\boldsymbol{U}$ 는 codomain $\mathbb{R}^m$ 에서 $\tilde{C}$ 로부터 $\mathbb{R}^m$ 의 canonical basis 로의 basis change를 수행합니다. 이는 Figure 4.8의 오른쪽 위 그림에서 red/orange vectors가 $\boldsymbol{e}_1-\boldsymbol{e}_2$ 평면을 벗어나 회전한 것으로 표현하고 있습니다.

SVD는 domain과 codomain에서의 basis change를 표현합니다. 이는 동일한 vector space에서 수행되는, 즉, 동일한 basis change가 적용되었다가 다시 반대로 적용되는 eigendecomposition과 대조됩니다. SVD는 eigendecomposition과는 달리 조금 특별한데, 두 개의 다른 basis가 singular value matrix $\Sigma$ 에 동시에 연결되어 있기 때문입니다.

Example 4.12 (Vectors and the SVD)

위의 그림과 같이 원점이 중심이고 2x2 크기의 square grid vector $\chi \in \mathbb{R}^2$ 의 mapping을 살펴보도록 하겠습니다. Standard basis를 사용하여, 이 vector들을 $\boldsymbol{A}$ 를 사용하여 mapping 합니다.

\[\begin{align*} \boldsymbol{A} &= \begin{bmatrix}1&-0.8\\0&1\\1&0\end{bmatrix} = \boldsymbol{U\Sigma V}^\top \tag{4.67a} \\ &= \begin{bmatrix}-0.79&0&-0.62\\0.38&-0.78&-0.49\\-0.48&-0.62&0.62\end{bmatrix}\begin{bmatrix}1.62&0\\0&1.0\\0&0\end{bmatrix}\begin{bmatrix}-0.78&0.62\\-0.62&-0.78\end{bmatrix} \tag{4.67b} \end{align*}\]

Grid에 정렬된 벡터 $\chi$ (위 그림의 왼쪽 위 참조) 부터 시작합니다. 먼저 $\boldsymbol{V}^\top \in \mathbb{R}^{2\times2}$ 를 적용하면 $\chi$ 는 회전합니다. 이렇게 회전된 벡터는 위 그림의 왼쪽 아래 그림에 해당합니다. 그리고 이 회전된 벡터들에 singular value matrix $\boldsymbol{\Sigma}$ 를 적용하여 codomain($\mathbb{R}^3$) 으로 mapping 합니다 (그림의 오른쪽 아래 참조). 여기서 모든 벡터들이 $x_1 - x_2$ plane에 놓여 있다는 것에 주목합니다. 세 번째 좌표계($x_3$) 은 항상 0입니다. 그리고 $x_1 - x_2$ plane에 놓여있는 벡터들은 singular values 만큼 늘어나거나 줄어듭니다.

$\boldsymbol{A}$ 에 의한 Vector $\chi$ 로부터 codomain $\mathbb{R}^3$ 로의 mapping은 $\boldsymbol{U\Sigma V}^\top$ 에 의한 transformation과 동일하며, $\boldsymbol{U}$ 는 $x_1 - x_2$ plane 에 놓여있는 벡터들을 codomain $\mathbb{R}^3$ 내에서 회전시킵니다. $\boldsymbol{U}$ 에 의한 회전은 위 그림 오른쪽 위 그림에서 보여주고 있습니다.

Construction of the SVD

이번에는 SVD가 왜 존재하는지, 그리고 어떻게 계산할 수 있는지 자세히 살펴보도록 하겠습니다. General matrix의 SVD는 square matrix의 eigendecomposition과 몇 가지 공통점이 존재합니다.

이어서 theorem 4.22가 왜 성립하고, SVD를 어떻게 만드는지 살펴보겠습니다. $\boldsymbol{A}\in\mathbb{R}^{m\times n}$ 의 SVD를 계산하는 것은 codomain $\boldsymbol{R}^m$ 의 orthonomal basis $U = (\boldsymbol{u}_1, \dotsc, \boldsymbol{u}_m)$ 과 domain $\boldsymbol{R}^n$ 의 orthonomal basis $V = (\boldsymbol{v}_1,\dotsc,\boldsymbol{v}_n)$ 를 찾는 것과 같습니다. 이렇게 찾은 ordered bases로부터, 우리는 행렬 $\boldsymbol{U}, \boldsymbol{V}$ 를 구성할 수 있습니다.

먼저 right-singular vectors $\boldsymbol{v}_1,\dotsc,\boldsymbol{v}_n$ 의 orthonormal 집합을 구성하는 것부터 시작합니다. 그리고, left-singular vectors $\boldsymbol{u}_1,\dotsc,\boldsymbol{u}_m$ 의 orthonormal 집합을 구성합니다. 그 후, $\boldsymbol{A}$ 의 transformation 에서도 $\boldsymbol{v}_i$ 의 orthogonality(직교성)이 보존되도록 두 singular vectors를 연결합니다. 이는 images $\boldsymbol{Av}_i$ 가 orthogonal vectors 집합을 형성한다는 것을 알고 있기 때문에 중요합니다. 그런 다음 $\boldsymbol{Av}_i$ 를 scalar factors로 정규화(normalization) 하는데, 이 scalar factors는 singular values가 됩니다.

그럼 먼저 right-singular vectors를 구성해보는 것으로 시작해보도록 합시다. Spectral theorem(Theorem 4.15, 4.2장 참조)를 통해 우리는 symmetric matrix의 eigenvectors가 orthonormal basis를 형성한다는 것을 알고 있습니다. 따라서, symmetric matrix는 대각화가 가능합니다. 또한, Theorem 4.14(4.2장 참조)를 통해 항상 모든 rectangular matrix $\boldsymbol{A}\in\mathbb{R}^{m\times n}$ 로부터 symmetric, positive semidefinite matrix $\boldsymbol{A}^\top\boldsymbol{A} \in \mathbb{R}^{n\times n}$ 를 구성할 수 있습니다. 그러므로, 항상 $\boldsymbol{A}^\top\boldsymbol{A}$ 를 다음과 같이 대각화할 수 있습니다.

\[\boldsymbol{A}^\top\boldsymbol{A} = \boldsymbol{PDP}^\top = \boldsymbol{P}\begin{bmatrix}\lambda_1&\cdots&0\\\vdots&\ddots&\vdots\\0&\cdots&\lambda_n\end{bmatrix}\boldsymbol{P}^\top \tag{4.71}\]

위 식에서 $\boldsymbol{P}$ 는 orthogonal matrix이며, orthonormal eigenbasis로 구성되어 있습니다. $\lambda_i \geq 0$ 은 $\boldsymbol{A}^\top\boldsymbol{A}$ 의 eigenvalues 입니다.

이제 $\boldsymbol{A}$ 의 SVD가 존재한다고 가정하고, 식 (4.64)를 (4.71)에 대입하면 다음의 식을 얻을 수 있습니다.

\[\boldsymbol{A}^\top\boldsymbol{A} = (\boldsymbol{U\Sigma V}^\top)^\top(\boldsymbol{U\Sigma V}^\top) = \boldsymbol{V\Sigma}^\top\boldsymbol{U}^\top\boldsymbol{U\Sigma V}^\top \tag{4.72}\]

여기서 $\boldsymbol{U},\boldsymbol{V}$ 는 orthogonal matrix 이므로 $\boldsymbol{U}^\top\boldsymbol{U} = \boldsymbol{I}$ 이며, 다음과 같이 정리됩니다.

\[\boldsymbol{A}^\top\boldsymbol{A} = \boldsymbol{V\Sigma}^\top\boldsymbol{\Sigma V}^\top = \boldsymbol{V}\begin{bmatrix}\sigma_1^2&0&0\\0&\ddots&0\\0&0&\sigma_n^2\end{bmatrix}\boldsymbol{V}^\top \tag{4.73}\]

식 (4.71)과 (4.73)을 비교해보면, 다음과 같습니다.

\[\begin{align*} \boldsymbol{V}^\top &= \boldsymbol{P}^\top \tag{4.74} \\ \sigma_i^2 &= \lambda_i \tag{4.75} \end{align*}\]

그러므로, 식 (4.74)에 의해 $\boldsymbol{P}$ 를 구성하는 $\boldsymbol{A}^\top\boldsymbol{A}$ 의 eigenvectors는 $\boldsymbol{A}$ 의 right-singular vectors $\boldsymbol{V}$ 입니다. 그리고 식 (4.75)에 의해서 $\boldsymbol{A}^\top\boldsymbol{A}$ 의 eigenvalues는 $\boldsymbol{\Sigma}$ 의 singular values의 제곱이 됩니다.

Left-singular vectors $\boldsymbol{U}$ 를 구하기 위해서는 위와 비슷한 과정을 수행합니다. 이번에는 symmetric matrix $\boldsymbol{AA}^\top\in\mathbb{R}^{m\times m}$ 의 SVD를 구하는 것으로 시작을 합니다. $\boldsymbol{A}$ 의 SVD를 적용하면, 다음의 식을 얻을 수 있습니다.

\[\begin{align*} \boldsymbol{AA}^\top &= (\boldsymbol{U\Sigma V}^\top)(\boldsymbol{U\Sigma V}^\top)^\top = \boldsymbol{U\Sigma V}^\top\boldsymbol{V\Sigma}^\top\boldsymbol{U}^\top \tag{4.76a} \\ &= \boldsymbol{U}\begin{bmatrix}\sigma_1^2&0&0\\0&\ddots&0\\0&0&\sigma_m^2\end{bmatrix}\boldsymbol{U}^\top \tag{4.76b} \end{align*}\]

Spectral theorem에 의해 $\boldsymbol{AA}^\top = \boldsymbol{SDS}^\top$ 는 대각화가 가능하고 $\boldsymbol{AA}^\top$ 의 eigenvectors의 ONB를 찾을 수 있습니다. $\boldsymbol{AA}^\top$ 의 orthonormal eigenvectors는 left-sigular vectors $\boldsymbol{U}$ 이며 SVD의 codomain에서 orthonormal basis 집합을 형성합니다.

여기서 행렬 $\boldsymbol{\Sigma}$ 의 구조에 대해 의문이 생길 수 있습니다. $\boldsymbol{AA}^\top$ 과 $\boldsymbol{A}^\top\boldsymbol{A}$ 가 동일한 nonzero eigenvalues를 갖기 때문에 SVD에서 $\boldsymbol{\Sigma}$ 행렬의 nonzero 요소들은 두 경우에서 모두 동일해야 합니다.

마지막으로 지금까지 했던 두 과정(singular vectors 구하기)의 마지막 단계들을 연결합니다. $\boldsymbol{V}$ 에 right-singular vectors의 orthonormal 집합이 존재하며, 이 벡터 집합을 orthonormal vectors $\boldsymbol{U}$ 와 연결시킵니다. 그리고 $\boldsymbol{A}$ 에 의한 $\boldsymbol{v}_i$ 의 image 또한 orthogonal하다는 사실을 이용합니다 (3.4장 참조). 따라서, $i\neq j$ 에서 $\boldsymbol{Av}_i$ 와 $\boldsymbol{Av}_j$ 의 내적은 0이 되어야 합니다. 그래서 모든 두 orthogonal eigenvectors $\boldsymbol{v}_i, \boldsymbol{v}_j, i\neq j$ 에 대해 다음의 식이 성립합니다.

\[(\boldsymbol{Av}_i)^\top(\boldsymbol{Av}_j) = \boldsymbol{v}_i^\top(\boldsymbol{A}^\top\boldsymbol{A})\boldsymbol{v}_j = \boldsymbol{v}_i^\top(\lambda_j\boldsymbol{v}_j) = \lambda_j\boldsymbol{v}_i^\top\boldsymbol{v}_j = 0 \tag{4.77}\]

이때, 모든 $m \geq r$ 의 경우에 대해 $\lbrace\boldsymbol{Av}_1,\dotsc,\boldsymbol{Av}_r\rbrace$ 는 $\mathbb{R}^m$ 에서 r-차원 subspace의 basis 입니다.

다음으로 orthonormal한 left-singular vectors를 구해야 합니다. 이는 right-singular vectors의 images $\boldsymbol{Av}_i$ 를 정규화하면 다음의 식을 얻을 수 있습니다.

\[\boldsymbol{u}_i := \frac{\boldsymbol{Av}_i}{\|\boldsymbol{Av}_i\|} = \frac{1}{\sqrt{\lambda_i}}\boldsymbol{Av}_i = \frac{1}{\sigma_i}\boldsymbol{Av}_i \tag{4.78}\]

위 식에서 마지막 등식은 식 (4.75)와 (4.76b)로부터 얻을 수 있고, $\boldsymbol{AA}^\top$ 의 eigenvalues가 $\sigma_i^2 = \lambda_i$ 라는 것을 보여줍니다.

그러므로 우리가 right-singular vectors $\boldsymbol{v}_i$ 로 알고 있는 $\boldsymbol{AA}^\top$ 의 eigenvectors 와 left-singular vectors $\boldsymbol{u}_i$ 로 알고 있는 $\boldsymbol{A}$ 아래에서의 normalized images는 singular value matrix $\boldsymbol{\Sigma}$ 를 통해 연결된 두 개의 self-consistent ONBs를 형성합니다.

식 (4.78)을 정리하면, 다음의 singular value equation 을 얻을 수 있습니다.

\[\boldsymbol{Av}_i = \sigma_i\boldsymbol{u}_i, \quad i = 1,\dotsc,r \tag{4.79}\]

이 방정식은 eigenvalue equation인 식 (4.25)와 매우 유사합니다만, 좌항과 우항에 있는 벡터는 같지 않습니다.

모든 $n < m$ 에 대해, 식 (4.79)는 $i \leq n$ 인 경우에는 만족하지만 $i > n$ 인 경우에 대해서는 알 수 없습니다. 그러나 이들이 orthonormal 하다는 것은 알고 있습니다. 반대로 $m < n$ 인 경우에도 식 (4.79)는 $i \leq m$ 에 대해서만 만족합니다. $i > m$ 일 때, $\boldsymbol{Av}_i = \boldsymbol{0}$ 이고 $\boldsymbol{v}_i$ 는 여전히 orthonormal 집합을 형성합니다. 이는 SVD가 $\boldsymbol{A}$ 의 kernel(null space)의 orthonormal basis를 $\boldsymbol{Ax} = \boldsymbol{0}$ 인 vector $\boldsymbol{x}$ 집합으로 제공한다는 것을 알 수 있습니다 (2.7.3장 참조).

마지막으로 모든 행 $1, \dotsc, r$ 에 대해 $\boldsymbol{v}_i$ 를 $V$ 의 column으로 붙이고, $\boldsymbol{u}_i$ 를 $U$ 의 column으로 붙이면 다음의 식을 도출해낼 수 있습니다.

\[\boldsymbol{AV} = \boldsymbol{U\Sigma} \tag{4.80}\]

따라서, 양변의 오른쪽에 $\boldsymbol{V}^\top$ 을 곱하면 $\boldsymbol{A} = \boldsymbol{U\Sigma V}^\top$ 이 도출되며 이는 $\boldsymbol{A}$ 의 SVD 입니다.

Example 4.13 (Computing the SVD)
다음의 행렬 $\boldsymbol{A}$ 에 대해 SVD를 찾아보도록 하겠습니다.

\[\boldsymbol{A} = \begin{bmatrix}1&0&1\\-2&1&0\end{bmatrix} \tag{4.81}\]

SVD를 찾으려면 right-singular vectors $\boldsymbol{v}_j$ , singular values $\sigma_k$ , left-singular vectors $\boldsymbol{u}_i$ 를 계산해야 합니다.

• Step 1: Right-singular vectors as the eigenbasis of $\boldsymbol{A}^\top\boldsymbol{A}$ .
  

먼저 다음의 식을 계산합니다.

\[\boldsymbol{A}^\top\boldsymbol{A} = \begin{bmatrix}1&-2\\0&1\\1&0\end{bmatrix}\begin{bmatrix}1&0&1\\-2&1&0\end{bmatrix} = \begin{bmatrix}5&-2&1\\-2&1&0\\1&0&1\end{bmatrix} \tag{4.82}\]

그리고, 다음과 같이 $\boldsymbol{A}^\top\boldsymbol{A}$ 의 eigenvalue decomposition을 통해, singular values와 right-singular vectors $\boldsymbol{v}_j$ 를 계산합니다. Eigenvalue Decomposition 결과는 다음과 같으며, 자세한 방법은 4.4장을 참조하시길 바랍니다.

\[\boldsymbol{A}^\top\boldsymbol{A} = \begin{bmatrix}\frac{5}{\sqrt{30}}&0&\frac{-1}{\sqrt{6}}\\\frac{-2}{\sqrt{30}}&\frac{1}{\sqrt{5}}&\frac{-2}{\sqrt{6}}\\\frac{1}{\sqrt{30}}&\frac{2}{\sqrt{5}}&\frac{1}{\sqrt{6}}\end{bmatrix}\begin{bmatrix}6&0&0\\0&1&0\\0&0&0\end{bmatrix}\begin{bmatrix}\frac{5}{\sqrt{30}}&\frac{-2}{\sqrt{30}}&\frac{1}{\sqrt{30}}\\0&\frac{1}{\sqrt{5}}&\frac{2}{\sqrt{5}}\\\frac{-1}{\sqrt{6}}&\frac{-2}{\sqrt{6}}&\frac{1}{\sqrt{6}}\end{bmatrix} = \boldsymbol{PDP}^\top \tag{4.83}\]

그리고 right-singular vectors를 다음과 같이 $\boldsymbol{P}$ 의 columns로 얻을 수 있습니다.

\[\boldsymbol{V} = \boldsymbol{P} = \begin{bmatrix}\frac{5}{\sqrt{30}}&0&\frac{-1}{\sqrt{6}}\\\frac{-2}{\sqrt{30}}&\frac{1}{\sqrt{5}}&\frac{-2}{\sqrt{6}}\\\frac{1}{\sqrt{30}}&\frac{2}{\sqrt{5}}&\frac{1}{\sqrt{6}}\end{bmatrix} \tag{4.84}\]

• Step 2: Singular-value matrix.
  

Singular values $\sigma_i$ 는 $\boldsymbol{A}^\top\boldsymbol{A}$ 의 eigenvalues의 제곱근이기 때문에 $\boldsymbol{D}$ 로부터 바로 구할 수 있습니다. $\text{rk}(\boldsymbol{A}) = 2$ 이므로, 2개의 nonzero singular values: $\sigma_1 = \sqrt{6}, \sigma_2 = 1$ 을 얻을 수 있습니다. Singular matrix는 $\boldsymbol{A}$ 와 같은 크기이며, 따라서 다음의 singular matrix를 얻을 수 있습니다.

\[\boldsymbol{\Sigma} = \begin{bmatrix}\sqrt{6}&0&0\\0&1&0\end{bmatrix} \tag{4.85}\]

• Step 3: Left-singular vectors as the normalized image of the right-singular vectors.
  

Left-singular vectors는 $\boldsymbol{A}$ 아래서의 right-singular vectors의 image를 계산하고, 대응되는 singular value르 나누어 정규화함으로써 찾을 수 있습니다. 그 과정은 다음과 같습니다.

\[\begin{align*} \boldsymbol{u}_1 &= \frac{1}{\sigma_1}\boldsymbol{Av}_1 = \frac{1}{\sqrt{6}}\begin{bmatrix}1&0&1\\-2&1&0\end{bmatrix}\begin{bmatrix}\frac{5}{\sqrt{30}}\\\frac{-2}{\sqrt{30}}\\\frac{1}{\sqrt{30}}\end{bmatrix} = \begin{bmatrix}\frac{1}{\sqrt{5}}\\-\frac{2}{\sqrt{5}}\end{bmatrix} \tag{4.86} \\ \boldsymbol{u}_2 &= \frac{1}{\sigma_2}\boldsymbol{Av}_2 = \frac{1}{1}\begin{bmatrix}1&0&1\\-2&1&0\end{bmatrix}\begin{bmatrix}0\\\frac{1}{\sqrt{5}}\\\frac{2}{\sqrt{5}}\end{bmatrix} = \begin{bmatrix}\frac{2}{\sqrt{5}}\\\frac{1}{\sqrt{5}}\end{bmatrix} \tag{4.87} \\ \boldsymbol{U} &= \lbrack\boldsymbol{u}_1\boldsymbol{u}_2\rbrack = \frac{1}{\sqrt{5}}\begin{bmatrix}1&2\\-2&1\end{bmatrix} \tag{4.88} \end{align*}\]

컴퓨터에서 위의 접근 방법은 pool numerical behavior이며, $\boldsymbol{A}$ 의 SVD는 $\boldsymbol{A}^\top\boldsymbol{A}$ 의 eigenvalue decomposition의 resorting 없이 정상적으로 계산할 수 있습니다.

Eigenvalue Decomposition vs. Singular Value Decomposition

Eigendecomposition $\boldsymbol{A} = \boldsymbol{PDP}^{-1}$ 와 SVD $\boldsymbol{A} = \boldsymbol{U\Sigma V}^\top$ 을 비교해보도록 하겠습니다.

• SVD는 모든 행렬 $\mathbb{R}^{m \times n}$ 에 대해 존재합니다. Eigendecomposition은 오직 square matrix $\mathbb{R}^{n \times n}$ 에서만 정의되며, 오직 $\mathbb{R}^n$ 의 eigenvectors의 basis를 찾을 수 있을 때만 존재합니다.
• Eigendecomposition matrix $\boldsymbol{P}$ 에서의 vector는 반드시 orthogonal할 필요는 없습니다. 즉, change of basis가 단순 rotation이나 scaling이 아닙니다. 반면, SVD의 matrix $\boldsymbol{U}, \boldsymbol{V}$ 의 vector들은 orthonormal이고 따라서 rotation을 표현합니다.
• Eigendecomposition과 SVD는 모두 다음의 세 가지 linear mapping으로 구성됩니다.
  1. Change of basis in the domain
  2. 각각의 새로운 basis vector에 대한 independent scaling과 domain에서 codomain으로의 mapping
  3. Change of basis in the codomain
  한 가지 핵심적인 차이점은 SVD에서는 domain과 codomain이 다른 차원의 vector spaces일 수 있다는 것입니다.
• SVD에서 left/right-singular vector matrix $\boldsymbol{U}, \boldsymbol{V}$ 는 일반적으로 서로의 역행렬이 아닙니다 (다른 vector spaces에서 basis change를 수행함). Eigendecomposition에서는 basis change matrix인 $\boldsymbol{P},\boldsymbol{P}^{-1}$ 는 서로의 역행렬입니다.
• SVD에서 diagonal matrix $\boldsymbol{\Sigma}$ 의 요소들은 모두 음이 아닌 실수이지만, Eigendecomposition의 diagonal matrix는 일반적으로 그렇지 않습니다.
• SVD와 Eigendecomposition은 projections을 통해 밀접하게 연관되어 있습니다.
  - $\boldsymbol{A}$ 의 left-singular vectors는 $\boldsymbol{AA}^\top$ 의 eigenvectors 입니다.
  - $\boldsymbol{A}$ 의 right-singular vectors는 $\boldsymbol{A}^\top\boldsymbol{A}$ 의 eigenvectors 입니다.
  - $\boldsymbol{A}$ 의 nonzero singular values는 $\boldsymbol{AA}^\top$ 의 nonzero eigenvalues의 제곱근이고, $\boldsymbol{A}^\top\boldsymbol{A}$ 의 nonzero eigenvalues와 같습니다.
• Symmetric matrix $\boldsymbol{A}\in\mathbb{R}^{n\times n}$ 에 대해 Eigenvalue decomposition과 SVD는 Spectral Theorem 4.15(4.2장 참조)에 의해 동일합니다.

Example 4.14 (Finding Structure in Movie Ratings and Consumers)
사람들이 선호하는 영화에 대한 데이터를 SVD를 이용하여 해석해보도록 하겠습니다.

3명의 사람(Ali, Beatrix, Chandra)이 있고 그들이 평가한 4개의 영화에 대한 점수가 있습니다. Rating은 0(worst) 부터 5(best)까지이며, 이는 아래 그림처럼 행렬 $\boldsymbol{A}\in\mathbb{R}^{4\times3}$ 으로 인코딩됩니다.

각각의 row는 영화를 나타내고, 각 column은 user를 나타냅니다. 따라서, movie rating의 column vector는 user 중 한 명을 표현합니다 ($\boldsymbol{x}_\text{Ali}, \boldsymbol{x}_\text{Beartrix}, \boldsymbol{x}_\text{Chandra}$).

SVD를 사용하여 $\boldsymbol{A}$ 를 분해하는 것은 사람들이 영화를 어떻게 평가하는지, 특히 어떤 사람들이 어떤 영화를 좋아하는에 대한 구조가 있다면 그러한 관계들을 포착하는 방법을 제공합니다. SVD를 data matrix $\boldsymbol{A}$ 에 적용하는 것에는 다음의 몇 가지 가정이 있습니다.

1. 모든 viewer는 동일한 lienar mapping을 사용하여 일관되게 영화를 평가합니다.
2. Ratings에는 어떠한 에러나 노이즈도 없습니다.
3. Left-singular vectors $\boldsymbol{u}_i$ 를 stereotypical movies로 해석하고, right-singular vectors $\boldsymbol{v}_j$ 를 stereotypical viewers로 해석합니다.

그런 다음 우리는 어떤 viewer의 특정 영화 선호도가 $\boldsymbol{v}_j$ 의 linear combination으로 표현될 수 있다고 가정합니다. 비슷하게, 어떤 영화를 좋아할 ability는 $\boldsymbol{u}_i$ 의 linear combination으로 표현될 수 있다고 가정합니다. 따라서, SVD의 domain에서 vector는 stereotypical viewers의 “space”에서 viewer로 해석될 수 있고, SVD의 codomain에서의 vector는 stereotypical movies의 “space”에서 movie로 해석될 수 있습니다.

이제 위의 movie-user matrix의 SVD를 조사해보도록 합시다 (위 그림의 오른쪽 행렬들). 첫 번째 left-singular vector $\boldsymbol{u}_1$ 2개의 science fiction movies에 대해 큰 절댓값을 가지며, 이에 해당하는 singular value 도 큽니다 (행렬의 빨간색 영역). 따라서, 이는 science fiction theme 영화의 집합을 가진 users의 타입을 그룹화합니다. 유사하게, 첫 번째 right-singular $\boldsymbol{v}_1$ 은 Ali와 Beatrix에 대해 큰 절댓값을 가지고 있다는 것을 보여주는데, Ali와 Beatrix는 science fiction movies에 높은 점수를 주었습니다 (초록색 영역). 이는 $\boldsymbol{v}_1$ 이 sience fiction을 좋아하는 사람들의 개념을 반영한다는 것을 알 수 있습니다.

비슷한 방법으로 $\boldsymbol{u}_2$ 는 French art house film 테마를 포착하고 $\boldsymbol{v}_2$ 는 Chandra라는 사람이 이러한 영화를 좋아한다는 것을 나타냅니다. Science fiction을 좋아하는 그룹 $\boldsymbol{v}_1$ 은 sicence fiction을 제외한 나머지 영화에는 0점으로 평가합니다. 이러한 로직은 singular value matrix $\boldsymbol{\Sigma}$ 에서 대각 성분 구조에 의해 유도됩니다. 그러므로 특정 영화는 stereotypical movies 로 (linearly) 분해되는 방식으로 표현됩니다. 마찬가지로, 사람들은 linear combination을 통해 movie 테마로 분해되는 방식으로 표현됩니다.

참고로 문헌마다 SVD를 다르게 작성하는 경우가 있기 때문에 SVD의 용어나 컨벤션을 간단히 살펴보겠습니다.

• 표기 상 편의성 및 추상화를 위해 left/right-singular vector matrix를 정사각 행렬로 표기하고 singular value matrix는 non-square로 표기합니다. 위에서 정의한 (4.64)가 이와 같은 경우이며, full SVD 라 부르기도 합니다.
• 몇몇 저자들은 SVD를 조금 다르게 정의하는데, square singular matrix에 포커스를 둡니다. 따라서, 모든 $\boldsymbol{A}\in\mathbb{R}^{m\times n}$ 과 $m \geq n$ 에 대해
  $\underset{m \times n}{\boldsymbol{A}} = \underset{m\times n}{\boldsymbol{U}}\text{ }\underset{n\times n}{\boldsymbol{\Sigma}}\text{ }\underset{n\times n}{\boldsymbol{V}^\top}$
  로 표기합니다. 이러한 공식을 reduced SVD 라고도 부릅니다. 이 방식은 행렬이 구성되는 방식만 변경하며 SVD의 수학적 구조는 변경되지 않습니다. 이 공식을 사용하면 eigenvalue decomposition처럼 $\boldsymbol{\Sigma}$ 가 diagonal 하다는 측면에서 편리합니다.
• 4.6장에서는 SVD를 사용한 matrix approximation 기법에 대해 배우는데, 이를 truncated SVD 라고 부릅니다.
• Rank-$r$ matrkx $\boldsymbol{A}$ 의 SVD를 정의하는 것이 가능하고, 따라서 $\boldsymbol{U}$ 는 $m \times r$ 행렬, $\boldsymbol{\Sigma}$ 는 $r \times r$ diagonal matrix, $\boldsymbol{V}$ 는 $n \times r$ 행렬입니다. 이러한 구조는 우리가 정의한 것과 유사하고, diagonal matrix $\boldsymbol{\Sigma}$ 가 오직 nonzero의 대각 성분을 갖는다고 보장합니다. Reduced SVD와 같이 singular value matrix가 diagonal이라는 측면에서 편리합니다.
• $\boldsymbol{A}$ 에 대한 SVD가 오직 $m > n$ 인 $m \times n$ 행렬에만 적용된다는 제한은 실제로 필요하진 않습니다. $m < n$ 일 때, SVD decomposition 에서 $m+1$ 부터 $n$ 행의 singular values는 모두 0입니다.

SVD는 curve fitting의 least-square problems부터 systems of linear equations 풀이까지 머신러닝의 다양항 application에서 사용됩니다. 이러한 application은 SVD의 다양하면서 중요한 속성들을 활용하는데, matrix rank와의 관계 / 주어진 rank를 더 낮은 rank로 근사화 등이 있습니다. 또한 행렬을 SVD로 대체하면 반올림과 관련된 에러에 더 견고해지도록 하는 이점이 있습니다.