Singular value decomposition (1)

1. 특이값 분해(Singular value decomposition, SVD)

■ 행렬 $A$가 대각화 가능하지 않은 $m \times m$ 정방행렬이거나, 심지어는 $m \times n$ 비정방행렬인 경우에도 다음과 같이 크기가 다른 두 개의 직교행렬 $U$와 $V^T$ 그리고 대각행렬 $\Sigma$로 분해하는 것을 특이값 분해라고 부른다. 

$A = U \Sigma V^T$

- 이렇게 특이값 분해를 하기 위한 행렬 $A$는 어떤 행렬이든 될 수 있다. 

- 고윳값 분해(EVD)는 정방행렬에서만 가능한 행렬 대각화 방법이다. 

■ SVD는 고윳값 분해와 비슷하게 보일 수 있다. (실제로 고윳값 분해에 대한 내용은 특이값 분해(SVD)에도 대부분 적용 가능) 

■ 새로운 점은 특이값 분해를 위해서 두 개의 직교행렬이 필요하다는 것이다. 어떤 행렬이든 특이값 분해를 가지고 있으며, 가운데에 대각 행렬이 있다. 

■ 행렬의 특이값 분해는 이미지 압축이나 보정과 같은 이미지 처리 기법, 데이터를 추출하는 통계 기법 등 다양한 분야에서 응용되고 있다.

---

1.1 SVD의 구조

■ 특이값 분해는 $m \times n$크기를 갖는 비정방행렬 $A$를 $A = U \Sigma V^T$로 나타낸다.

■ $A$를 $A = U \Sigma V^T$로 나타냈을 때, 각 행렬에 대한 구조는 다음과 같다.

■ 이렇게 SVD는 고윳값 분해(EVD)와 달리, 정방행렬이 아니어도 분해가 가능하다.

■ 여기서 $U$는 왼쪽 특이벡터(left singular vector) 행렬, $\Sigma$는 특이값 행렬, $V$는 오른쪽 특이벡터(right singular vector) 행렬이라고 부르며, 행렬 $A$는 $U$와 $\Sigma$ 그리고 $V$의 전치행렬인 $V^T$의 곱으로 분해된다.

■ 이때, 행렬 $A$가 정방이 아니어도 $U$와 $V$는 모두 정방행렬이다. 

■ 그리고 $U$와 $V$는 직교행렬이므로 $U^T U = I, \; V^T V = I$이다.

■  $A$의 rank가 $r$이라면, 특이값 행렬 $\Sigma$는 $r$개의 비영(non-zero) 특이값을 가진다.

(= 0이 아닌 특이값의 개수는 행렬의 계수(rank)와 같다.)

이때,  $\Sigma$의 대각 원소에 나타나는 $r$개의 특이값들은 항상 가장 큰 값(왼쪽 위)부터 가장 작은 값(오른쪽 아래) 순서대로 정렬된다. 그리고 $r + 1$부터 나머지 대각 원소들은 모두 0이다. 

■ 또한, 모든 특이값은 음수가 아닌 실수이다. 행렬에 복소숫값이 포함되어 있더라도 특이값이 복소수나 음수가 될 수 없다.

■ $U$의 처음 $r$개의 열은 행렬 $A$의 열공간 $C(A)$에 대한 정규직교기저(벡터), 나머지 $m - r$개의 열은 $A$의 left nullspace(즉, $A^T$의 nullspace)에 대한 정규직교기저이다.

그러므로 $U$의 열벡터들이 $m$차원 공간 전체 $\mathbb{R}^m$을 생성한다고 할 수 있다. 즉, $A$의 열공간과 left nullspace가 만드는 전체 공간 $\mathbb{R}^m$에서 열공간의 차원이 $m$이므로 left nullspace의 차원은 0. 즉, left nullspace $N(A^T) = \{ 0 \}$. 즉, left nullspace는 비어 있다.

■ $V^T$의 처음 $r$개의 행(= $V$의 $r$개의 열)은 행공간 $C(A^T)$에 대한 정규직교기저, 나머지 $n - r$개의 행(= $V$는 열에 해당)은 $A$의 영공간(nullspace)에 대한 정규직교기저이다.

그러므로 $V^T$의 행벡터들이 $n$차원 공간 전체 $\mathbb{R}^n$을 생성한다고 할 수 있다.

이 영공간 기저벡터들은 $\Sigma$ 행렬의 0인 특이값에 대응된다.

$A$가 비정방행렬일 때, $A$의 계수가 $r = m$이면, left nullspace의 공간은 $\{ 0 \}$이다. 동일한 논리로 $A$가 비정방행렬일 때, $A$의 계수가 $r = n$이면 영공간은 $N(A) = \{ 0 \}$. 즉, 영공간(nullspace)는 비어 있다.

■ 특이값 분해(SVD)의 가장 중요한 특징은 행렬의 4개의 부분공간(row space, column space, nullspace, left nullspace)을 모두 나타낸다는 점이다.  

[출처] Gilbert Strang - Introduction   to Linear  Algebra

- $A$의 열공간은 $U$의 처음 $r$개의 열벡터로 생성되며 , $A$의  left nullspace는 $U$의 나머지 $m - r$개의 열벡터에 의해 생성된다.

- $A$의 행공간은 $V^T$의 처음 $r$개의 행벡터로 생성되며, $A$의 영공간(nullspace)는 $V^T$으 나머지 $n - r$개의 행벡터에 의해 생성된다. 

- 그리고 $A$가 비정방행렬일 때, $r = m$이면 left nullspace의 공간인 $N(A^T) = \{ 0 \}$

-  $A$가 비정방행렬일 때, $r = n$이면 영공간(nullspace)의 공간인 $N(A) = \{ 0 \}$  

■ 이는 $\Sigma$ 행렬에서 0이 아닌 특이값의 개수인 행렬 $A$의 계수 $r$이 영공간과 left nullspace의 차원을 결정하는 것으로 볼 수 있으며,  행렬의 계수 $r$은 $\Sigma$ 행렬에서 0이 아닌 특이값의 수로 결정되는 것으로 볼 수 있다.

■ 그리고 영공간들(nullspace, left nullspace)은 특이값 분해에서 대각 원소로 특이값을 갖는 $\Sigma$ 행렬의 대각 원소에 0으로 나타난다.

- 특이값 분해에서 행렬 $A$는 $A = U \Sigma V^T$로 분해된다. 

- 여기서 1.1에 명시한 것처럼, $A$의 계수(rank)가 $r$이라면, 시그마 행렬은 $r$개의 비영(non-zero) 특이값을 가진다. 그리고 $r+1$부터 나머지 대각 원소들은 모두 0이다.

- 이때, $V^T$의 마지막 $n - r$개의 행(= $V$는 열에 해당)은 $A$의 영공간(nullspace)에 대한 정규직교기저이며, 

- $U$의 마지막 $m - r$개의 열은 $A$의 left nullspace(즉, $A^T$의 nullspace)에 대한 정규직교기저이다.

- 특이값 분해에서 영공간(nullspace)와 left nullspace는 대각행렬인 $\Sigma$ 행렬의 대각선에(특이값을 나타내는 위치에) 0으로 나타난다.  

- 그 이유는 1.2의 두 번째 설명에 명시한 SVD의 성질 $A v_i = \sigma_i u_i$와 영공간의 정의, left nullspace의 정의를 통해 확인할 수 있다. 

--  $A v_i = \sigma_i u_i$에서 $v_i$는 $V$의 $i$ 번째 열(= $V^T$의 $i$ 번째 행)벡터 

-- $u_i$는 $U$의$i$ 번째 열벡터, $\sigma_i$는 $\Sigma$행려에서 $i$번째 특이값이다.

- 영공간의 정의는 $A \mathbf{x} = 0$을 만족하는 벡터 $\mathbf{x}$들의 집합이다. 

- 만약, $\sigma_i = 0$이라면, $A v_i = \sigma_i u_i \Leftrightarrow A v_i = 0 \times u_i = 0$이 된다. 즉, $v_i$는 영공간에 속한다.

- 다시 말해, 특이값이 0인 경우, 이에 대응하는 오른쪽 특이벡터 $v_i$는 행렬 $A$의 영공간에 속한다.

- 즉, 특이값이 0일 때, 행렬 $V$ 내의 $i$ 번째 영공간의 정규직교벡터 $v_i$가 존재하는 것으로 볼 수 있다. 그러므로 영공간(nullspace)은 특이값 분해에서 $\Sigma$라는 대각행렬의 대각선에 0으로 나타나는 것이다.

- left nullspace에 대해서도 유사한 논리가 적용된다. $A^T u_i = \sigma_i v_i$에서 $\sigma_i = 0$이면, $u_i$는 left nullspace에 속한다.

- 그러므로 특이값이 0인 경우, 이에 대응하는 왼쪽 특이벡터 $u_i$는 행렬 $A$의 left nullspace에 속한다. 

- 즉, 특이값이 0일 때, 행렬 $U$ 내의 $i$ 번째 left nullspace의 정규직교벡터 $u_i$가 존재하는 것으로 볼 수 있다. 그러므로 left nullspace는 특이값 분해에서 $\Sigma$라는 대각행렬의 대각선에 0으로 나타나는 것이다.

---

1.2.  $U \Sigma V^T$ '직교행렬 $\cdot$ 대각행렬 $\cdot$ 직교행렬'의 형태

■ 벡터공간의 표준기저에 대한 선형사상의 행렬표현이 $A$일 때, $Av_i = \lambda_i v_i$을 만족하도록 벡터공간의 정규직교기저 $\{ v_1, \cdots, v_n \}$를 잘 선택하는 것이 행렬의 직교대각화라고 생각할 수 있다.

■ 행렬의 대각화가 가능하지 않은 경우나 두 벡터공간의 차원이 다른 경우, 선형사상(선형변환)의 정의역의 정규직교기저 $\{ v_i \}$와 공역의 정규직교기저 $\{ u_i \}$를 다르게 잡아서 $Av_i = \sigma_i u_i$가 성립하도록 할 수 있다. 이것이 특이값 분해이며, 특이값 분해를 통해 얻을 수 있는 결과이다.

■ 예를 들어, 다음 그림처럼 어떤 선형변환을 통해 행공간에 있는 벡터 $v_1$이 어떤 연산을 통해서 열공간에 있는 어떤 벡터 $u_1$으로 이동한다고 하자. 즉,  $A$를 선형변환의 행렬표현이라고 했을 때 $u_1 = A v_1$이다.

- 이렇게 행공간에서 열공간으로 선형변환하면 행공간에 있는 다른 벡터들도 열공간으로 이동하게 된다.

■ 이 특이값 분해에서 찾아야 하는 것은 행공간의 직교 기저이다. 1.1.1의 두 번째 설명에 언급한 것처럼, 행공간의 직교기저가 이동하여 열공간의 직교기저로 변환되기 때문이다.

■ 행공간에서 $v_1$과 직각인 벡터를 $v_2$라고 하자. 그렇다면 $v_1$과 $v_2$는 직교기저이다. 이 직교기저들이 선형변환에 의해 다음과 같이 열공간으로 이동하여 $u_1, \; u_2$라는 열공간의 직교 기저로 이동하게끔 만드는 것이 목표이다. 즉, 열공간의 직교 기저로 이동하는 행공간의 직교 기저를 찾는 것이 목표이다.

■ 즉 특이값 분해는 정의역에 있는 직교 벡터들에 대해, 선형변환했을 때, 벡터의 크기는 변하지만 변환된 공간에서 여전히 직교하는 직교 벡터들이 무엇인지 알려주는 역할을 한다고 생각할 수 있다.

■ 이 행공간에 대한 직교 기저는 행공간의 어떠한 (일반) 기저 하나로 시작해서 그람-슈미트 과정을 통해 찾을 수 있다.

■ 하지만, 아무 직교 기저를 사용한다면, 즉 행공간의 아무 직교 기저를 선형변환의 행렬표현 $A$에 곱한다고 해서 이것이 열공간에서 직교 기저가 되어야 할 이유는 없다. 

■ 그래서 행공간에 있는 기저 벡터를 사용하여 $A$와 곱했을 때, 열공간에서 직교 벡터가 되는 특별한 설정을 찾아야 한다.

■ 위의 그림에서 영공간(nullspace)과 left nullspace가 포함되지 않은 것을 볼 수 있다. 왜냐하면 해당 공간들은 아무런 영향을 미치지 않는다. 1.1에 명시한 것처럼, 영공간들(nullspace, left nullspace)은 특이값 분해에서 $\Sigma$라는 대각행렬의 대각선에 0으로 나타난다.

■ $A$의 행공간의 차원은 $A$의 계수(rank)이므로 행공간의 기저벡터는 $v_1, v_2,  \cdots , v_r$이다. 

■ $A$의 행공간에 있는 기저벡터를 정규직교기저(벡터)로 만들어서 $A$와 곱하면, $A [ v_1, v_2, \cdots,  v_r \quad ]$이며, $A v_1$이 첫 번째 열이 될 것이다.

■ 그리고 $v_1, v_2, \cdots, v_r$은 정규직교기저이므로 단위벡터이다. 벡터에 행렬을 곱하는 것은 벡터에 선형변환을 하는 것과 동일하다. 행렬은 선형변환처럼 벡터를 변환시켜 크기도 방향도 모두 다를 수 있는 벡터를 만들기 때문이다.

■ 그러므로 $A v_1 = \sigma_1 u_1$을 선형변환의 관점에서 보면, 선형변환의 역할을 수행하는 행렬 $A$와 단위벡터 $v_1$의 곱은 $u_1$에 $\sigma_1$을 곱한. 즉, 다음 그림에서 표현된 것과 같은 배수 관계를 갖는다.

- 현재 고윳값 분해가 아니므로 이 배수는 $\lambda$가 아니다. 여기서 이 배수는 sigma라고 부른다. (특이값 분해에서는 이 시그마를 특이값이라고 부른다.) 

■ 특이값 분해는 위의 그림과 같이 $A v_1 = \sigma_1 u_1$에서 $v_1$이 정규직교기저일 때, 선형변환을 통해서(= $v_1$에 행렬 $A$를 곱해서) $u_1$이 열공간 내의 정규직교기저가 되게 하는 행공간의 기저를 찾는 것이 목표이다.

■ $A v_1 = \sigma_1 u_1, \; A v_2 = \sigma_2 u_2, \cdots$이므로 $A [ v_1, v_2, \cdots,  v_r, \quad ]$는 다음과 같이 나타낼 수 있다. 

$A \begin{bmatrix} v_1 & v_2 & \cdots & v_r  & \quad \end{bmatrix} = \begin{bmatrix} u_1 & u_2 & \cdots & u_r & \quad \end{bmatrix} \begin{bmatrix} \sigma_1 & 0 & \cdots & 0 \\ 0 & \sigma_2 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & \sigma_r & \quad \end{bmatrix} \Leftrightarrow AV = U \Sigma$ 

- 다시 정리하면,

- 행렬 $V$의 열벡터 $v_1, v_2, \cdots, v_r$은 행렬 $A$의 행공간의 정규직교기저(벡터)이고

- 행렬 $U$의 열벡터 $u_1, u_2, \cdots, u_r$은 행렬 $A$의 열공간의 정규직교기저이며

- $\Sigma$에 있는 $\sigma_1, sigma_2 \cdots, \sigma_r$은 $u_1, u_2, \cdots, u_r$에 곱해지는 요소들이다.

- 곱해지는 배수 인자인 $\sigma$들이 대각 원소에 있으므로 대각선을 제외한 나머지 위치에 존재하는 원소들은 항상 0이 된다. 그러므로 $\Sigma$는 대각행렬이 된다. 

■ $AV = U \Sigma$에서 $V$는 행공간에 있는 정규직교기저들로 구성된 행렬, $U$는 열공간에 있는 정규직교기저들로 구성된 행렬이므로, $A$는 대각행렬 $\Sigma$로 변환되는 것으로 볼 수 있다.

■ 여기서 $V$와 $U$는 각각 행공간과 열공간의 정규직교기저들로 구성된 행렬이므로 직교행렬이다. $AV = U \Sigma$ 식의 양변에 $V$의 역행렬을 곱하면 $A = U \Sigma V^{-1}$이며, $V$는 직교행렬이므로 $A = U \Sigma V^T$로 나타낼 수 있다. 

■ $A = U \Sigma V^T$에는 두 개의 직교 행렬 $U$와 $V$가 있다. $U, \; V$를 한 번에 찾을 수는 없고, 별도로 찾아야 한다.

■ 그 방법은 바로 $A^T A$, $AA^T$ 표현을 이용하는 것이다.

■ $A^T A$를 이용해 $U$를 사라지게 만들어 $V$를 구할 수 있고, $AA^T$를 이용해 $V$를 사라지게 만들어 $U$를 구할 수 있다.

■ 일반적인 직사각형 행렬 $A$가 있을 때, $A^TA$는 대칭 행렬이고, 양의 정부호 또는 적어도 양의 준정부호이다. 이것은 좋은 특성을 가진 행렬이다.

■ $A = U \Sigma V^T$일 때, $A^T = V \Sigma^T U^T$이므로 $A^TA = ( V \Sigma^T U^T ) (U \Sigma V^T)$가 된다.

■ 이때, $U$는 직교행렬이므로 $U^TU = I$가 된다. 그러므로 $A^TA = ( V \Sigma^T U^T ) (U \Sigma V^T) = V \Sigma^T \Sigma V^T$가 된다. 

■ $A^T A = V \Sigma^T \Sigma V^T$에서 $\Sigma$행렬은 대각행렬이다. 그러므로 $\Sigma^T \Sigma$는 단지 대각선 위에 $\sigma$값의 제곱을 가지게 된다.

$A^T A = V \Sigma^T \Sigma V^T = V \begin{bmatrix} \sigma_1^2 & 0 & 0 & \cdots & 0 \\ 0 & \sigma_2^2 & 0 & \cdots & 0 \\ 0 & 0 & \sigma_3^2 & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \cdots &  \end{bmatrix} V^T$

■ 정리된 $A^T A$ 식을 보면, 이는 고윳값 분해의 $Q \Lambda Q^T$와 동일한 것을 볼 수 있다.

- 즉 $A^T A$에 대해 $V$는 $A^T A$의 고유벡터로 구성된 행렬,

- $\Sigma^T \Sigma$는 대각 원소가 $A^T A$의 고윳값으로 구성된 행렬

■ 행렬 $A$는 그 자체로 특별하지 않지만, $A^T A$는 대칭 양의 정부호(symmetric positive definite)이므로, $V$는 $A^T A$의 고유벡터로 구성된 직교행렬, $\Sigma^T \Sigma = \Sigma^2$은 $A^T A$의 고윳값으로 구성된 대각행렬이다.

■ 그리고 이 고윳값들은 양수가 된다. 왜냐하면 $A^T A$는 양의 정부호이기 때문이다. 

■ $A^T A$ 표현을 통해 $V$는 $A^T A$의 고유벡터로 구성된 직교행렬임을 확인하였다. 이제 $AA^T$표현을 통해 $U$가 무엇인지 찾으면 된다. 

■ $AA^T$ 표현을 이용하면 $V$를 제거하고 $U$만 남게 된다. $AA^T = U \Sigma^T \Sigma U^T = U \Sigma^2 U^T$

■ $V$를 찾기 위한 과정과 $U$를 찾기 위한 과정은 동일하다. $A^TA$를 이용하느냐 $AA^T$를 이용하느냐의 차이이다.

■ 즉, $U$는 $AA^T$의 고유벡터로 구성된 직교행렬이다. 그리고 이 경우에도 $\Sigma^2$이므로 $\Sigma^2$행렬은 대각 원소에 양의 $\sigma$값을 가진다.

■ 예를 들어, $A^TA = \begin{bmatrix} 4 & -3 \\ 4 & 3 \end{bmatrix} \begin{bmatrix} 4 & 4 \\ -3 & 3 \end{bmatrix} = \begin{bmatrix} 25 & 7 \\ 7 & 25 \end{bmatrix}$라고 하자.

■ 그러면 정방행렬 $A^T A$ 고유벡터들은 행렬 $V$가 될 것이고, $A^T A$의 고윳값은 $\sigma$의 제곱이 될 것이다.

■ 이 $A^T A$ 예시의 고유벡터는 $\begin{bmatrix} 1 \\ 1 \end{bmatrix}$와 $\begin{bmatrix} 1 \\ -1 \end{bmatrix}$이다.

■ $A^T A = \begin{bmatrix} 25 & 7 \\7 & 25 \end{bmatrix}$에 고유벡터 $\begin{bmatrix} 1 \\ 1 \end{bmatrix}$를 곱하면 $32 \begin{bmatrix} 1 \\ 1 \end{bmatrix}$이 된다. 즉, $A^T A$의 고유벡터 중 하나는 $\begin{bmatrix} 1 \\ 1 \end{bmatrix}$이고 이 고유벡터에 대응되는 고윳값은 32이다.

■ $A^T A = \begin{bmatrix} 25 & 7 \\7 & 25 \end{bmatrix}$에 고유벡터 $\begin{bmatrix} 1 \\ -1 \end{bmatrix}$를 곱하면  $18 \begin{bmatrix} 1 \\ 1 \end{bmatrix}$이 된다. 즉, $A^T A$의 고유벡터 중 하나는 $\begin{bmatrix} 1 \\ -1 \end{bmatrix}$이고 이 고유벡터에 대응되는 고윳값은 18이다.

■ $A^T A = V \Sigma^2 V^T$에서 $V$는 $A^T A$의 고유벡터로 구성된 직교행렬이었다. 즉, $V$에는 $A^T A$의 고유벡터에 정규직교를 가한 벡터로 구성된다.

■ 그러므로 위의 $A^T A$에서 얻은 고유벡터들에 대해 정규화를 해야 한다. 그러면 정규화한 $A^T A$의 고유벡터들은 $\begin{bmatrix} 1 / \sqrt{2} \\ 1 / \sqrt{2} \end{bmatrix}$와 $\begin{bmatrix} 1 / \sqrt{2} \\ -1 / \sqrt{2} \end{bmatrix}$이며, 

■ $\begin{bmatrix} 1 / \sqrt{2} \\ 1 / \sqrt{2} \end{bmatrix}$와 $\begin{bmatrix} 1 / \sqrt{2} \\ -1 / \sqrt{2} \end{bmatrix}$로 구성된 행렬이 바로 $V$이다.

■ 그리고 $A^T A = V \Sigma^2 V^T$에서 $\Sigma^2$의 대각 원소 $\sigma^2$은 고윳값이었다. 즉, 특이값인 $\sigma$값은 고윳값의 제곱근이다. 그러므로 특이값 행렬 $\Sigma$의 대각 원소는 $\sqrt{32}$와 $\sqrt{18}$이다.

■ 그러므로 이 예시에서 행렬 $A = \begin{bmatrix} 4 & 4 \\ -3 & 3 \end{bmatrix}$은 특이값 분해 $A = U \Sigma V^T$로 나타낸다면, $\Sigma$와 $V$를 알고 있으므로 

$\begin{bmatrix} 4 & 4 \\ -3 & 3 \end{bmatrix} = U \begin{bmatrix} \sqrt{32} & 0 \\ 0 & \sqrt{18} \end{bmatrix} \begin{bmatrix} 1 / \sqrt{2} & 1 / \sqrt{2} \\ 1 / \sqrt{2} & - 1 / \sqrt{2} \end{bmatrix}$ 로 나타낼 수 있다.

■ 이제 마지막으로, $U$를 찾아야 한다.

- 사실, 위의 상태에서 $U$를 제외한 나머지 행렬들을 알고 있으므로, 나머지 행렬들( $A, \; \Sigma, \; V^T$ )를 이용해서 $U$를 도출할 수 있다.

■ $AA^T = U \Sigma^2 U^T$이며, $AA^T$는 symmetric positive definite이거나 최소한 semi-definite matrix이므로 $U$는 $AA^T$의 고유벡터들로 구성된 직교행렬이며 $\Sigma^2$은 $AA^T$의 고윳값으로 구성된 고윳값 대각행렬이며, 대각 원소들은 양수가 된다.

■ $U$는 $AA^T$의 고유벡터들로 구성된 직교행렬이므로 $AA^T$를 계산할 필요가 있다.

■ $AA^T = \begin{bmatrix}  4 & 4 \\  -3 & 3  \end{bmatrix} \begin{bmatrix}  4 & -3 \\  4 & 3  \end{bmatrix} = \begin{bmatrix}  32 & 0 \\  0 & 18  \end{bmatrix}$이므로 $AA^T$의 고윳값은 32, 18이며, $\lambda = 32$에 대응되는 고유벡터는 $\begin{bmatrix} 1 \\ 0 \end{bmatrix}$, $\lambda = 18$에 대응되는 고유벡터는 $\begin{bmatrix} 0 \\ -1 \end{bmatrix}$이다. 

■ 위에서 계산한 $A^T A$의 고윳값과 $AA^T$의 고윳값이 동일한 것을 확인할 수 있다.

- $A \mathbf{x} = \lambda \mathbf{x}$에서 $A$ 대신 $A^T A$를 놓으면

- $A^T A \mathbf{x} = \lambda \mathbf{x}$이며, 양변에 $A$를 곱하면 $(AA^T) (A \mathbf{x}) = \lambda (A \mathbf{x})$가 된다.

- 이때, $A^T A$의 고윳값과 $AA^T$의 고윳값은 $\lambda$로 동일한 것을 볼 수 있다.

■ 이 예시에서 $AA^T$의 고유벡터들이 직교행렬 $U$를 구성하는 벡터들이 되기 위해선, 마찬가지로 정규화가 필요하지만, 이미 $AA^T$의 고유벡터들은 $\begin{bmatrix} 1 \\ 0 \end{bmatrix}$, $\begin{bmatrix} 0 \\ -1 \end{bmatrix}$이다. 

■ $U$를 구했으므로, $A$에 대한 특이값 분해는 다음과 같다. 

$\begin{bmatrix} 4 & 4 \\ -3 & 3 \end{bmatrix} = \begin{bmatrix} 1 & 0 \\ 0 & -1 \end{bmatrix} \begin{bmatrix} \sqrt{32} & 0 \\ 0 & \sqrt{18} \end{bmatrix} \begin{bmatrix} 1 / \sqrt{2} & 1 / \sqrt{2} \\ 1 / \sqrt{2} & - 1 / \sqrt{2} \end{bmatrix}$ 

■ 또 다른 예로, $A = \begin{bmatrix} 4 & 3 \\ 8 & 6 \end{bmatrix}$이다. 이 행렬은 특이(singular) 행렬이다.

■ 즉, 이 행렬의 계수(rank)는 1이므로 행공간과 열공간의 차원은 1차원이며, 퇴화차수(영공간의 차원)은 $n - \text{rank} = 2 - 1 = 1$이다.

■ 그러므로 이 행렬의 행공간은 행벡터 (4, 3)에 의해 생성되며(행벡터 (4, 3)에 스칼라배한 벡터들로 행공간이 생성되며), 열공간은 열벡터 (1, 2)에 의해 생성된다. (열벡터 (1, 2)에 스칼라배한 벡터들로 열공간이 생성된다.) 

그러므로 행공간과 열공간은 다음과 같이 2차원 공간 상에서 직선(1차원)이 된다.

■ 이 예시에서 전체 공간은 행렬 $A$가 $2 \times 2$이므로 $\mathbb{R}^n = \mathbb{R}^2$이며, $\mathbb{R}^m = \mathbb{R}^2$이다.

■ 행공간과 수직인 공간은 영공간(nullspace)이다. 이 예에서 $\mathbb{R}^n = \mathbb{R}^2$이며, 행공간은 1차원이므로 영공간은 1차원이다.

그리고 열공간과 수직인 공간은 left nullspace이다. 이 예에서 $\mathbb{R}^m = \mathbb{R}^2$이며, 열공간은 1차원이므로 left nullspace은 1차원이다.

그러므로 이 예시 행렬의 4개의 부분공간은 다음과 같다.

■ 즉, 직교 기저를 선택할 때 행공간에 직교하는 영공간의 기저를, 영공간과 직교하는 left nullspace의 기저를 선택할 수 있다. 

■ 이 예시에서 행렬 $A$는 $2 \times 2$이므로 $V$행렬은 $v_1$과 $v_2$ 두 개의 정규직교가저로 구성된다. 이때, $v_1$은 행공간에 있는 기저 벡터를, $v_2$는 행공간의 기저 벡터와 직교하는 영공간의 기저 벡터를 선택할 수 있다는 얘기이다. 이는 $U$행렬에 대해서도 마찬가지이다.

■ 이 예시에서 행공간의 기저 벡터는 (4, 3)이다. 이 기저 벡터를 $V$행렬의 $v_1$벡터로 사용하기 위해서는 이 기저 벡터를 정규직교기저로 만들어야 한다. 정규직교기저로 만들면 (4/5, 3/5) = (0.8, 0.6)이 된다.

그리고 $v_2$는 $v_1$과 수직이므로 $v_1$과의 내적 결과가 0이 되는 정규직교기저를 $v_2$로 사용하면 된다.

■ 영공간의 기저 벡터는 (1, 2)이다. 이 기저 벡터를 $U$행렬의 $u_1$벡터로 사용하기 위해서는, 마찬가지로 정규직교기저로 만들어야 한다. 정규직교기저로 만들면 (1/sqrt(5), 2/sqrt(5))이다. $u_1$과 $u_2$는 수직이므로 $u_1$과의 내적 결과가 0이 되는 정규직교기저를 $u_2$로 사용하면 된다.

■ $\Sigma$ 행렬을 찾기 위해 $A^TA$ 표현을 이용하면, $A^T A = \begin{bmatrix} 4 & 8 \\ 3 & 6 \end{bmatrix} \begin{bmatrix} 4 & 3 \\ 8 & 6 \end{bmatrix} = \begin{bmatrix} 80 & 60 \\ 60 & 45 \end{bmatrix}$이며, $A$는 rank가 1인 행렬이므로 $A^T A$도 rank가 1인 행렬이 된다.

■ rank가 1이므로 이 행렬의 고윳값 중 하나는 0이 된다. 대각합은 고윳값의 합이므로 다른 하나의 고윳값은 125이다.

■ $\Sigma$ 행렬의 대각 원소는 $A^T A$의 고윳값의 제곱근이므로, 이 예시의 $\Sigma = \begin{bmatrix} \sqrt{125} & 0 \\ 0 & 0 \end{bmatrix}$가 된다.

■ 여기서 행렬 $A$의 계수(rank)는 0이 아닌 특이값의 개수라는 것을 알 수 있다. 이 예에서 행렬 $A$의 rank는 1이며, $\Sigma$ 행렬에서 0이 아닌 특이값 $\sigma$의 개수는 1개이다.

■ $U, \;, V, \; \Sigma$ 행렬을 찾았으므로 행렬 $A$에 대한 특이값 분해를 나타낼 수 있다. 

$A = \begin{bmatrix}  4 & 3 \\  8 & 6  \end{bmatrix} = \frac{1}{\sqrt{5}} \begin{bmatrix}  1 & 2 \\  2 & -1  \end{bmatrix} \begin{bmatrix}  \sqrt{125} & 0 \\  0 & 0  \end{bmatrix} \begin{bmatrix}  0.8 & 0.6 \\  0.6 & -0.8  \end{bmatrix}$

■ 여기서 행렬 $U = \frac{1}{\sqrt{5}} \begin{bmatrix} 1 & 2 \\ 2 & -1 \end{bmatrix}$를 보면, 1열인 $\begin{bmatrix} 1 \\ 2 \end{bmatrix}$는 열공간의 정규직교기저이며, 2열은 열공간의 정규직교기저와 직교하는 left nullspace의 정규직교기저임을 알 수 있다. 

■ 그리고 행렬 $V^T = \begin{bmatrix} 0.8 & 0.6 \\ 0.6 & -0.8 \end{bmatrix}$를 보면, 1행은 행공간의 정규직교기저이며, 2행은 행공간의 정규직교기저와 직교하는 영공간(nullspace)의 정규직교기저임을 알 수 있다.

■ 행렬 $U$와 $V$에 들어가는 행공간, 열공간, 영공간, left nullspace의 정규직교기저는 행렬 $A$의 rank와 관련이 있는 것을 알 수 있다.

■ 행렬 $A$의 rank를 $r$이라고 했을 때, $r = 1$이다. 여기서 $r$은 행공간의 차원이므로 행공간의 차원은 1이며, 행공간과 직교하는 영공간의 차원은 $n - r = 2- 1 = 1$이다.

- $V^T$의 1행은 행공간의 정규직교기저로 행공간을 생성하는 벡터이다. 2행은 영공간의 정규직교기저로 영공간을 생성하는 벡터이다.

- 그리고 $V^T$에서 행공간의 정규직교기저의 위치와 영공간의 정규직교기저의 위치는 행렬 $A$의 계수(rank) $r = 1$을 기준으로 나뉘는 것을 볼 수 있다.

- $U$에도 동일한 논리가 적용된다.

- 열공간의 차원은 행렬 $A$의 rank인 $r$이므로 열공간의 차원은 1이다. 그리고 열공간과 직교하는 left nullspace의 차원은 $m - r = 2 - 1 = 1$이다. 

- $U$의 1열은 열공간을 생성하는 열공간의 정규직교기저, 2열은 left nullspace를 생성하는 left nullspace의 정규직교기저이다. 

- 즉, $U$ 역시 $A$의 계수 $r$을 기준으로 나뉘어지는 것을 볼 수 있다.

■ 그러므로, 행렬 $A$의 계수(rank)를 $r$이라고 했을 때,

- 정방행렬인 직교행렬 $V$를 구성하는 행벡터 $v$에 대해,  $v_1, v_2, \cdots, v_r$은 행공간에 대한 정규직교기저이며, $v_{r+1}$부터 나머지 벡터는 영공간에 대한 정규직교기저이다.

- 정방행렬인 직교행렬 $U$를 구성하는 열벡터 $u$에 대해, $u_1, u_2, \cdots, u_r$은 열공간에 대한 정규직교기저이며, $u_{r+1}$부터 나머지 벡터는 left nullspace에 대한 정규직교기저이다.

■ 그리고 특이값 분해에서는 이 기저들이 행렬을 대각화하기 위해 특이값 $\sigma$가 필요했다. 행렬 $A$에 대하여 $\sigma$의 관계는 $A v_i = \sigma_i u_i$. 즉, $A v_i$는 벡터 $u_i$의 $\sigma_i$만큼의 배수가 된다.

■ 이 $\sigma_i$가 왼쪽 특이벡터와 오른쪽 특이벡터를 연결하는 역할을 수행한다.

---

정리

■ 행렬 $A$가 정방이 아닌 $m \times n$ 비정방에 대해서도 특이값 분해를 통해 고윳값 분해처럼 대각화를 할 수 있다.

■ 특이값 분해는 보통 행렬의 대각화가 가능하지 않은 경우나 두 벡터공간의 차원이 다른 경우, 선형변환의 정의역의 정규직교기저 $v_i$와 공역의 정규직교기저 $u_i$를 다르게 잡아서 선형변환을 표현할 수 있도록 하기 위해 사용된다. 

즉, $A v_i = \sigma_i u_i$라는 선형변환이 성립하도록 만드는 것이다.

■ 이는 선형변환의 역할을 수행하는 행렬 $A$를 정의역의 정규직교기저 $v_i$에 작용했을 때(곱했을 때), 변환되는 벡터가 공역의 정규직교기저 $u_i$의 배수 $\sigma_i u_i$가 되도록 하는 과정으로 이해할 수 있다.

■ 그러므로 $A$에 대해 특이값 분해를 하면 $A = U \Sigma V^T$로 분해되며, 이때 $U$와 $V^T$는 각각 정규직교기저 $u_i$와 $v_i$로 구성된 직교행렬($B^TB = I$)이다. 

- 여기서 $U$의 열벡터를 행렬 $A$의 왼쪽 특이벡터, $V$의 열벡터를 행렬 $A$의 오른쪽 특이벡터라고 부른다.
- 이 특이벡터들은 마치 고윳값 분해에서 $A$를 대각화하기 위해 사용된 $Q$ 행렬의 벡터들과 동일한 역할(=대각화하는 역할)을 수행한다. 

■ 그리고 행렬 $A$의 계수(rank)가 $r$이라면, 

- 대각행렬인 특이값 행렬 $\Sigma$의 대각 원소에 있는 0이 아닌 특이값의 개수는 $A$의 계수 $r$이다.
- $U$의 처음 $r$개의 열은 행렬 $A$의 열공간을 생성하는 열공간의 정규직교기저이며, 나머지 열은 left nullspace을 생성하는 left nullspace의 정규직교기저이다. 

- $V^T$의 처음 $r$개의 행은 행렬 $A$의 행공간을 생성하는 행공간의 정규직교기저이며, 나머지 행은 영공간(nullspace)을 생성하는 영공간의에 정규직교기저이다.
- 그러므로 행렬 $A$가 $m \times n$크기를 갖는 비정방행렬일 때, $r = m$이면 left nullspace는 $\{ 0 \}$이므로 전체 공간의 차원은 $A$의 열공간의 차원이 된다.
- $r = n$이면 영공간은 $\{ 0 \}$이므로 전체 공간의 차원은 $A$의 행공간의 차원이 된다.

■ 이렇게 특이값 분해(SVD)는 행렬의 4개의 부분공간인 행공간, 열공간, 영공간, 왼쪽 영공간을 모두 나타낸다는 특징이 있다.

■ $A = U \Sigma V^T$에서 직교행렬인 $U$와 $V$를 구하기 위하여 $A^T A$ 표현과 $AA^T$ 표현을 이용한다.

- $A^T A$는 행렬 $A$의 오른쪽 특이벡터를 구하기 위해 사용된다. 즉, $A^TA$를 통해 행렬 $V$를 도출할 수 있다.
- $AA^T$는 행렬 $A$의 왼쪽 특이벡터를 구하기 위해 사용된다. 즉, $AA^T$를 통해 행렬 $U$를 도출할 수 있다.
- 이 방법들은 $U$와 $V$가 직교행렬임을 이용하는 방법이다.

■ 먼저, $A^TA = V \Sigma^T U^T U \Sigma V^T = V \Sigma^2 V^T$가 된다.

- $U$는 직교행렬이므로 $U^T U = I$
- $\Sigma$는 대각행렬이므로 $\Sigma^T \Sigma = \Sigma^2$. 
- $AA^T = U \Sigma V^T V \Sigma^T U^T = U \Sigma^2 U^T$가 된다.

■ 이때, 대칭행렬 $A^T A$와 $AA^T$를 전개한 식을 보면, 고윳값 분해의 $Q \Lambda Q^T$와 동일한 형태임을 확인할 수 있다. 

■ 즉, 대칭행렬에 대해서 특이값 분해(SVD)는 고윳값 분해와 같은 개념이라고 생각할 수 있다.

■ $A^T A$와 $AA^T$는 (대칭) 양의 정부호 행렬이거나 최소한 양의 준정부호 행렬이다. 그러므로 $V$나 $U$는 $A^T A$의 고유벡터로 구성된 직교행렬, $AA^T$의 고유벡터로 구성된 직교행렬이며, $\Sigma^2$ 행렬은 $A^TA$ 또는 $AA^T$의 고윳값으로 구성된 대각행렬이다. 

■ 또한, $A^T A$와 $AA^T$는 (대칭) 양의 정부호 행렬이거나 최소한 양의 준정부호 행렬이라는 것은 대각행렬인 $\Sigma^2$의 대각 원소가 적어도 양수라는 것 의미한다.

■ 이때, 대각 $Sigma^2$의 원소는 $A^TA$ 또는 $AA^T$의 고윳값으로 구성되었으므로 고윳값들은 양수라고 할 수 있다. 

■ $\Sigma^2$의 대각 원소인 $\sigma^2$가 $A^T A$ 또는 $AA^T$의 고윳값이라면 특이값 $\sigma$은 고윳값의 제곱근이며, 이때 고윳값이 양수였으므로 모든 특이값은 음수가 아닌 실수라고 할 수 있다.

■ $A^T A$나 $AA^T$는 대칭행렬이 된다. 대칭행렬의 고윳값은 실수이므로 특이값은 실수이다. 

■ 또한, 대칭행렬의 고유벡터는 직교이므로 특이벡터는 직교벡터가 되어야 한다. 즉, $A^T A$의 고유벡터는 오른쪽 특이벡터가 되기 위해서는 직교벡터가 되어야 한다. 

- $U$와 $V$의 벡터를 정규직교기저로 가정했으면, 대칭행렬 $A^T A$와 $AA^T$의 고유벡터를 정규화하여 정규직교기저로 만들면 된다.

■ 이러한 특이값 행렬의 특징을 정리하면 ① 특이값은 음수가 될 수 없다 ② 특이값은 실수이다 ③ 특이벡터는 (정규)직교벡터이다. 

■ 이렇게 $U, \; V, \; \Sigma$ 행렬을 찾았으면 $A$에 대해 특이값 분해를 수행할 수 있다. 

■ 특이값 분해를 나타냈을 때, $U$를 보면 $m \times n$행렬 $A$의 계수(rank)가 $r$일 때, $m \times m$행렬 $U$의 1열부터 $r$열까지는 열공간의 (정규)직교기저, $r+1$열부터 $m$열까지는 left nullspace의 (정규)직교기저임을 확인할 수 있다.

■ $n \times n$ 행렬 $V^T$를 보면 $V^T$의 1행부터 $r$행까지는 행공간의 (정규)직교기저, $r+1$행부터 $n$행까지는 영공간의 (정규)직교기저임을 확인할 수 있다.

■ 그리고 특이값 행렬에서 대각 원소에 있는 특이값은 항상 가장 큰 값(왼쪽 위)부터 가장 작은 값(오른쪽 아래) 순서대로 정렬된다. 또한, 특이벡터는 동일한 특이값과 쌍을 이루는 것을 확인할 수 있다.

■ 특이벡터는 동일한 특이값과 쌍을 이룬다는 것은 $i$번째 왼쪽 특이벡터를 $u_i$, $i$번째 특이값을 $\sigma_i$, $i$번째 오른쪽 특이벡터 $v^T_i$라고 하자.

■ 예를 들어, 가장 큰 특이값은 특이행렬의 맨 왼쪽 위에 위치한다. 즉, $\sigma_1$이다. 

- $\sigma_1 \geq \sigma_2 \geq \cdots \geq \sigma_r > 0$이기 때문

■ 그리고 특이벡터 $u_1$은 $U$의 1열에 $v_1$은 $V^T$의 1행에 위치한다. 이를 그림으로 나타내면 다음과 같으며, 특이벡터는 동일한 특이값과 쌍을 이루는 것을 볼 수 있다.  

■ 이때, $u_i$, $\sigma_i$, $v^T_i$를 곱하면, $\sigma_i$는 실수이므로 열벡터 $\times$ 행벡터이다.

■ 이렇게 열벡터 $\times$ 행벡터. 벡터의 곱셈을 계산하면 행렬 $A$와 동일한 크기를 갖는 계수(rank)가 1인 행렬이 만들어진다.

■ 예를 들어,  $u_1$ $\sigma_1$ $v^T_1$을 곱하면 행렬 $A$와 동일한 크기를 갖는 계수가 1인 행렬이 만들어진다. 그리고 이 행렬은 가장 큰 특이값 $\sigma_1$을 가지고 있는 행렬이 된다.

$u_2$ $\sigma_2$ $v^T_2$을 곱했다면, 두 번째로 큰 특이값을 가지고 있는 행렬 $A$와 동일한 크기를 갖는 계수가 1인 행렬이 된다.

■ 즉, 행렬 $A$의 계수가 $r$이라면, 위와 같이 만들어진 행렬 $A$와 동일한 크기를 가지지만 계수가 1인 행렬들을 모두 더한 결과는 원래 행렬로 복원된다. 이를 식으로 나타내면 다음과 같다. 

$A = \displaystyle \sum^{r}_{i = 1} u_i \sigma_i v^T_i$, $\sigma_1 \geq \sigma_2 \geq \cdots \geq \sigma_r > 0$

cf) $A = \displaystyle \sum^{r}_{i = 1} u_i \sigma_i v^T_i$, $\sigma_1 \geq \sigma_2 \geq \cdots \geq \sigma_r > 0$의 원리는 데이터 정제에서 사용된다.

- 위의 식은 $i = 1$부터 $A$의 계수인 $r$까지 행렬 $A$와 동일한 크기를 가지며 계수가 1인 행렬을 더하여 원래 행렬 $A$를 복원한다. 특이값과 관련된 정보까지 모두 복원되는 것이다.

- 이때, 이렇게 모두 더하는 것이 아니라 작은 특이값을 담고 있는 계수-1 행렬은 제외하고 어느 정도 값이 큰 특이값을 가지는 $k$개의 계수-1행렬을 더하여 행렬 $A$를 근사 시킬 수 있다. (여기서 $k$는 $1 \leq k \leq r$)

- 이를 행렬 $A$의 낮은 계수 근사치(low rank approximation)이라고 하며, 이것이 데이터 정제에서 사용하는 아이디어이다.

- 데이터 정제에서는 작은 특이값과 관련된 정보는 데이터의 전체 분산에 기여하는 정도가 매우 작으므로 작은 특이값을 갖는 정보는 제외시킨다.즉, 상위의 특이값 몇 개만 선택하여 원래 정보와 최대한 가깝게 근사시키는 것이다. 

- 이렇게 $\Sigma$ 행렬의 대각 원소인 특이값 중에서 상위 몇 개만 선택하는 것을 truncated SVD라고 부른다.

---

이어서 Singular value decomposition (2) - 특이값 분해 응용 (1)