특이값 분해(singular value decomposition)

• 모든 행렬에 대해 특이값 분해가 가능하다.
  • 만일 행렬이 실수, 대칭, 양의 정부호이면 특잇값과 고윳값이 같고, 왼쪽 오른쪽 특이벡터는 고유벡터와 같다.
  • 정사각 행렬에만 정의가 되는 고유 분해와 달리 특이 분해는 정사각이 아닌 행렬에도 적용 가능하다. 이것은 행렬이 벡터의 선형 변환임을 고려할 때, 특이 분해는 벡터의 차원이 변하는 맥락에서도 가능하다는 의미이다. 고로 차원 축소(dimension reduction)와 같이 벡터의 차원이 변하는 맥락에서는 고유 분해가 아니라 특이 분해를 하게 된다.
• $m \times n$ 크기의 행렬 $\bold{A}$를 다음과 같은 3개의 행렬 곱으로 나타내는 것을 특잇값분해(singular value decomposition) 또는 특이분해(singular-decomposition)라고 한다.

$$ \bold{A} = \bold{U} \boldsymbol{\Sigma} \bold{V}^\top $$

• 여기서 $\bold{U}, \boldsymbol{\Sigma}, \bold{V}$는 다음 조건을 만족해야 한다.
  • $\boldsymbol{\Sigma} \in \mathbb{R}^{m \times n}$는 대각성분이 양수인 대각행렬이어야 한다. 큰 수부터 작은 수 순서로 배열한다.
  • $\bold{U} \in \mathbb{R}^{m \times m}$는 $n$차원 orthogonal 행렬이다.
  • $\bold{V} \in \mathbb{R}^{n \times n}$는 $m$차원 orthogonal 행렬이다.
  • 위 조건을 만족할 때 행렬 $\boldsymbol{\Sigma}$의 대각성분들을 특잇값(singular value), 행렬 $\bold{U}$의 열벡터들을 왼쪽 특이벡터(left singular vector), 행렬 $\bold{V}$의 행벡터들을 오른쪽 특이벡터(right singular vector)라고 부른다.
• 특잇값 분해는 행렬 $\bold{A}$를 직교 행렬 $\bold{U}$와 $\bold{V}$로 ‘회전’ 시키고, 대각 행렬 $\boldsymbol{\Sigma}$로 ‘확장’ 또는 ‘압축’하는 과정으로 해석할 수 있다.
  • 왼쪽 특이벡터 $\bold{U}$는 $\bold{AA}^\top$의 고유벡터에 해당하며, $\bold{A}$에 의해 변환된 공간에서의 방향을 나타낸다. 왼쪽 특이벡터는 $\bold{A}$가 작용하는 ‘입력’ 공간(또는 열공간)의 기저를 형성한다.
  • 오른쪽 특이벡터 $\bold{V}$는 $\bold{A}^\top\bold{A}$의 고유벡터에 해당하며, $\bold{A}$에 의해 변환되기 전의 원래 공간에서의 방향을 나타낸다. 오른쪽 특이벡터들은 $\bold{A}$의 ‘출력’ 공간(또는 행공간)의 기저를 형성한다.
  • 특잇값 벡터 $\boldsymbol{\Sigma}$의 특잇값들은 $\bold{AA}^\top$나 $\bold{A}^\top\bold{A}$의 고윳값의 제곱근에 해당하고, $\bold{A}$에 의한 변환에서 각 방향의 확장 정도를 나타낸다.
• 특잇값 개수는 행렬의 열과 행 개수 중 작은 값과 같다. 특잇값 분해된 형태를 구체적으로 쓰면 다음과 같다.
  • 만약 $m > n$이면 $\boldsymbol{\Sigma}$ 행렬이 $n$개의 특잇값(대각성분)을 가지고 아랫 부분이 영행렬이 된다.
  • 반대로 $m < n$이면 $\boldsymbol{\Sigma}$행렬이 $m$개의 특잇값(대각성분)을 가지고 오른쪽 부분이 영행렬이 된다.
• 특이 행렬과 특이 벡터 행렬의 모양은 아래 페이지 참조
  • ‣
• 특잇값 대각행렬에서 0인 부분은 사실상 아무런 의미가 없기 때문에 대각행렬의 0 원소 부분과 이에 대응하는 왼쪽(혹은 오른쪽) 특이벡터들을 없애고 다음처럼 축소된 형태로 해도 마찬가지로 원래 행렬이 나온다.
  • $m > n$인 경우에는 왼쪽 특이벡터 중에서 $\bold{u}{n+1}, ... , \bold{u}{m}$을 없앤다.
  • $m < n$인 경우에는 오른쪽 특이벡터 중에서 $\bold{v}{m+1}, ... , \bold{v}{n}$을 없앤다.
• 왼쪽 특이 벡터는 Range에 대한 직교정규 기저(orthonormal basis)를 형성하고, 오른쪽 특이 벡터는 Null 공간에 대한 직교정규 기저를 형성한다.
• 특잇값 분해에서 특잇값 행렬에 역수를 취한 것을 이용하면 pseudo inverse를 구할 수 있다.

$$ \bold{A}^\dag \triangleq \bold{V} \boldsymbol{\Sigma}^\dag \bold{U}^\top $$

• 일반적으로 다음과 같은 선형 방정식의 least squares 해를 구하기 위해 SVD를 사용할 수 있다.

$$ \bold{Af} = 0 $$

• $\bold{A}$에 대한 SVD $\bold{A} = \bold{U}\boldsymbol{\Sigma}\bold{V}^\top$에서 $\boldsymbol{\Sigma}$가 특잇값을 크기 순서대로 갖는 대각행렬이므로, $\boldsymbol{\Sigma}$에서 가장 작은 특잇값은 $\boldsymbol{\Sigma}$의 가장 아래 행에 해당하며, 그 행과 곱해지는 $\bold{V}$의 마지막 열이 $\bold{Af} = 0$의 최소 제곱 해에 해당한다. 이는 가장 작은 특잇값에 해당하는 특이벡터가 최소 제곱 오차를 최소화하기 때문이다.

특이 분해 절차

• 다음의 조건을 이용하여 특이 분해를 수행한다.
  1. 모든 $m \times n$ 크기의 행렬 $\bold{A}$에 대해 $\bold{AA}^\top = \bold{A}^\top \bold{A}$는 정사각 대칭 행렬이 된다.
  2. 모든 대칭 행렬은 고윳값과 고유벡터를 갖고 고유벡터가 직교한다.
  3. 정의에 의해 좌측 특이 벡터 행렬과 우측 특이 벡터 행렬 $\bold{U, V}$는 모두 orthogonal이다.

1. $\bold{A}$가 $\bold{U}\boldsymbol{\Sigma}\bold{V}^\top$로 분해가 되므로 $\bold{AA}^\top$을 계산한다.
   • $\bold{AA}^\top$이 대칭행렬이기 때문에 $\bold{AA}^\top = \bold{V}\boldsymbol{\Lambda}\bold{V}^{-1} = \bold{V}\boldsymbol{\Lambda}\bold{V}^\top$이 성립한다.

$$ \bold{AA}^\top = \bold{U}\boldsymbol{\Sigma}\bold{V}^\top \bold{V}\boldsymbol{\Sigma}^\top\bold{U}^\top = \bold{U}\boldsymbol{\Sigma}\boldsymbol{\Sigma}^\top\bold{U}^\top = \bold{V} \boldsymbol{\Lambda}\bold{V}^\top $$