Search
Duplicate

수학/ 특이값 분해(singular value decomposition)

특이값 분해(singular value decomposition)

•
모든 행렬에 대해 특이값 분해가 가능하다.
◦
만일 행렬이 실수, 대칭, 양의 정부호이면 특잇값과 고윳값이 같고, 왼쪽 오른쪽 특이벡터는 고유벡터와 같다.
◦
정사각 행렬에만 정의가 되는 고유 분해와 달리 특이 분해는 정사각이 아닌 행렬에도 적용 가능하다. 이것은 행렬이 벡터의 선형 변환임을 고려할 때, 특이 분해는 벡터의 차원이 변하는 맥락에서도 가능하다는 의미이다. 고로 차원 축소(dimension reduction)와 같이 벡터의 차원이 변하는 맥락에서는 고유 분해가 아니라 특이 분해를 하게 된다.
•
m×nm \times n 크기의 행렬 A\bold{A}를 다음과 같은 3개의 행렬 곱으로 나타내는 것을 특잇값분해(singular value decomposition) 또는 특이분해(singular-decomposition)라고 한다.
A=UΣV⊤\bold{A} = \bold{U} \boldsymbol{\Sigma} \bold{V}^\top
•
여기서 U,Σ,V\bold{U}, \boldsymbol{\Sigma}, \bold{V}는 다음 조건을 만족해야 한다.
◦
Σ∈Rm×n\boldsymbol{\Sigma} \in \mathbb{R}^{m \times n}는 대각성분이 양수인 대각행렬이어야 한다. 큰 수부터 작은 수 순서로 배열한다.
◦
U∈Rm×m\bold{U} \in \mathbb{R}^{m \times m}는 nn차원 orthogonal 행렬이다.
◦
V∈Rn×n\bold{V} \in \mathbb{R}^{n \times n}는 mm차원 orthogonal 행렬이다.
◦
위 조건을 만족할 때 행렬 Σ\boldsymbol{\Sigma}의 대각성분들을 특잇값(singular value), 행렬 U\bold{U}의 열벡터들을 왼쪽 특이벡터(left singular vector), 행렬 V\bold{V}의 행벡터들을 오른쪽 특이벡터(right singular vector)라고 부른다.
•
특잇값 분해는 행렬 A\bold{A}를 직교 행렬 U\bold{U}와 V\bold{V}로 ‘회전’ 시키고, 대각 행렬 Σ\boldsymbol{\Sigma}로 ‘확장’ 또는 ‘압축’하는 과정으로 해석할 수 있다.
◦
왼쪽 특이벡터 U\bold{U}는 AA⊤\bold{AA}^\top의 고유벡터에 해당하며, A\bold{A}에 의해 변환된 공간에서의 방향을 나타낸다. 왼쪽 특이벡터는 A\bold{A}가 작용하는 ‘입력’ 공간(또는 열공간)의 기저를 형성한다.
◦
오른쪽 특이벡터 V\bold{V}는 A⊤A\bold{A}^\top\bold{A}의 고유벡터에 해당하며, A\bold{A}에 의해 변환되기 전의 원래 공간에서의 방향을 나타낸다. 오른쪽 특이벡터들은 A\bold{A}의 ‘출력’ 공간(또는 행공간)의 기저를 형성한다.
◦
특잇값 벡터 Σ\boldsymbol{\Sigma}의 특잇값들은 AA⊤\bold{AA}^\top나 A⊤A\bold{A}^\top\bold{A}의 고윳값의 제곱근에 해당하고, A\bold{A}에 의한 변환에서 각 방향의 확장 정도를 나타낸다.
•
특잇값 개수는 행렬의 열과 행 개수 중 작은 값과 같다. 특잇값 분해된 형태를 구체적으로 쓰면 다음과 같다.
◦
만약 m>nm > n이면 Σ\boldsymbol{\Sigma} 행렬이 nn개의 특잇값(대각성분)을 가지고 아랫 부분이 영행렬이 된다.
◦
반대로 m<nm < n이면 Σ\boldsymbol{\Sigma}행렬이 mm개의 특잇값(대각성분)을 가지고 오른쪽 부분이 영행렬이 된다.
•
특이 행렬과 특이 벡터 행렬의 모양은 아래 페이지 참조
◦
•
특잇값 대각행렬에서 0인 부분은 사실상 아무런 의미가 없기 때문에 대각행렬의 0 원소 부분과 이에 대응하는 왼쪽(혹은 오른쪽) 특이벡터들을 없애고 다음처럼 축소된 형태로 해도 마찬가지로 원래 행렬이 나온다.
◦
m>nm > n인 경우에는 왼쪽 특이벡터 중에서 un+1,...,um\bold{u}_{n+1}, ... , \bold{u}_{m}을 없앤다.
◦
m<nm < n인 경우에는 오른쪽 특이벡터 중에서 vm+1,...,vn\bold{v}_{m+1}, ... , \bold{v}_{n}을 없앤다.
•
왼쪽 특이 벡터는 Range에 대한 직교정규 기저(orthonormal basis)를 형성하고, 오른쪽 특이 벡터는 Null 공간에 대한 직교정규 기저를 형성한다.
•
특잇값 분해에서 특잇값 행렬에 역수를 취한 것을 이용하면 pseudo inverse를 구할 수 있다.
A†≜VΣ†U⊤\bold{A}^\dag \triangleq \bold{V} \boldsymbol{\Sigma}^\dag \bold{U}^\top
•
일반적으로 다음과 같은 선형 방정식의 least squares 해를 구하기 위해 SVD를 사용할 수 있다.
Af=0\bold{Af} = 0
•
A\bold{A}에 대한 SVD A=UΣV⊤\bold{A} = \bold{U}\boldsymbol{\Sigma}\bold{V}^\top에서 Σ\boldsymbol{\Sigma}가 특잇값을 크기 순서대로 갖는 대각행렬이므로, Σ\boldsymbol{\Sigma}에서 가장 작은 특잇값은 Σ\boldsymbol{\Sigma}의 가장 아래 행에 해당하며, 그 행과 곱해지는 V\bold{V}의 마지막 열이 Af=0\bold{Af} = 0의 최소 제곱 해에 해당한다. 이는 가장 작은 특잇값에 해당하는 특이벡터가 최소 제곱 오차를 최소화하기 때문이다.

특이 분해 절차

•
다음의 조건을 이용하여 특이 분해를 수행한다.
1.
모든 m×nm \times n 크기의 행렬 A\bold{A}에 대해 AA⊤=A⊤A\bold{AA}^\top = \bold{A}^\top \bold{A}는 정사각 대칭 행렬이 된다.
2.
모든 대칭 행렬은 고윳값과 고유벡터를 갖고 고유벡터가 직교한다.
3.
정의에 의해 좌측 특이 벡터 행렬과 우측 특이 벡터 행렬 U,V\bold{U, V}는 모두 orthogonal이다.
1.
A\bold{A}가 UΣV⊤\bold{U}\boldsymbol{\Sigma}\bold{V}^\top로 분해가 되므로 AA⊤\bold{AA}^\top을 계산한다.
•
AA⊤\bold{AA}^\top이 대칭행렬이기 때문에 AA⊤=VΛV−1=VΛV⊤\bold{AA}^\top = \bold{V}\boldsymbol{\Lambda}\bold{V}^{-1} = \bold{V}\boldsymbol{\Lambda}\bold{V}^\top이 성립한다.
AA⊤=UΣV⊤VΣ⊤U⊤=UΣΣ⊤U⊤=VΛV⊤\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
•
따라서 AA⊤\bold{AA}^\top의 고유벡터 행렬을 U\bold{U}로 두고 고윳값 행렬을 ΣΣ⊤=Λ\bold{\Sigma\Sigma}^\top = \boldsymbol{\Lambda}로 두어 특잇값을 구한다.
◦
고윳값의 제곱근이 특이값이 되는데, 이때 편의상 양수인 것만 사용한다. 특잇 행렬은 값이 큰 것부터 대각 방향으로 나열한다.
2.
이번에는 V\bold{V}를 구하기 위해 A⊤A\bold{A}^\top\bold{A}을 계산한다.
•
마찬가지로 A⊤A\bold{A}^\top\bold{A}가 대칭행렬이기 때문에 A⊤A=VΛV−1=VΛV⊤\bold{A}^\top\bold{A} = \bold{V}\boldsymbol{\Lambda}\bold{V}^{-1} = \bold{V}\boldsymbol{\Lambda}\bold{V}^\top이 성립한다.
A⊤A=VΣ⊤U⊤UΣV=VΣ⊤ΣV⊤=VΛV⊤\bold{A}^\top\bold{A} = \bold{V}\boldsymbol{\Sigma}^\top\bold{U}^\top \bold{U}\boldsymbol{\Sigma}\bold{V} = \bold{V}\boldsymbol{\Sigma}^\top\boldsymbol{\Sigma}\bold{V}^\top = \bold{V} \boldsymbol{\Lambda}\bold{V}^\top
•
따라서 A⊤A\bold{A}^\top\bold{A}의 고유벡터 행렬을 V\bold{V}로 두고 고윳값 행렬을 Σ⊤Σ=Λ\bold{\Sigma}^\top\boldsymbol{\Sigma} = \boldsymbol{\Lambda}로 두어 특잇값을 구한다.
◦
여기서 구한 특이 행렬은 1에서 구한 것과 행렬의 크기만 다를 뿐 특잇값 자체는 동일하다.
◦
행렬의 크기가 다르다는 것은 mm과 nn의 크기에 따라 행렬의 아래쪽이 0으로 채워지느냐 오른쪽이 0으로 채워지냐만 달라진다.
•
AA⊤\bold{AA}^\top와 A⊤A\bold{A}^\top\bold{A}의 고윳값이 같기 때문에 1과 2에서 구한 특잇값은 같지만 —행렬의 크기는 다르더라도—, A⊤A\bold{A}^\top\bold{A}과 A⊤A\bold{A}^\top\bold{A}의 크기가 다르기 때문에 고유벡터 또한 다르고 왼쪽 특이벡터 행렬 U\bold{U}와 오른쪽 특이벡터 행렬 V\bold{V}은 다르다.

특잇값과 특이벡터의 관계

•
행렬 V\bold{V}는 정규직교 행렬이므로 전치행렬이 역행렬이다.
V⊤=V−1\bold{V}^\top = \bold{V}^{-1}
•
특잇값분해된 등식에 양변에 V\bold{V}를 곱하면 다음과 같다.
AV=UΣV⊤V=UΣ\bold{AV} = \bold{U} \boldsymbol{\Sigma} \bold{V}^\top \bold{V} = \bold{U} \boldsymbol{\Sigma}
A[v1v2...vm]=[u1u2...un][σ10...0σ2............]\bold{A} \left[ \begin{matrix} \bold{v}_1 & \bold{v}_2 & ... & \bold{v}_m \end{matrix} \right] = \left[ \begin{matrix} \bold{u}_1 & \bold{u}_2 & ... & \bold{u}_n \end{matrix} \right] \left[ \begin{matrix} \sigma_1 & 0 & ... \\ 0 & \sigma_2 & ... \\ ... & ... & ... \end{matrix} \right]
•
m>nm > n이면 다음과 같다.
[Av1Av2...Avn]=[σ1u1σ2u2...σnun]\left[ \begin{matrix} \bold{Av}_1 & \bold{Av}_2 & ... & \bold{Av}_n \end{matrix} \right] = \left[ \begin{matrix} \sigma_1 \bold{u}_1 & \sigma_2 u_2 & ... & \sigma_n \bold{u}_n \end{matrix} \right]
•
m<nm < n이면 다음과 같다.
[Av1Av2...Avm]=[σ1u1σ2u2...σmum]\left[ \begin{matrix} \bold{Av}_1 & \bold{Av}_2 & ... & \bold{Av}_m \end{matrix} \right] = \left[ \begin{matrix} \sigma_1 \bold{u}_1 & \sigma_2 \bold{u}_2 & ... & \sigma_m \bold{u}_m \end{matrix} \right]
•
즉 ii번째 특잇값 σi\sigma_i와 특이벡터 ui,vi\bold{u}_i, \bold{v}_i는 다음과 같은 관계가 있다.
Avi=σiui (i=1,...,min⁡(m,n))\bold{Av}_i = \sigma_i \bold{u}_i \ (i = 1, ... , \min(m,n))

특잇값분해와 고유분해의 관계

•
행렬 A\bold{A}의 분산행렬 A⊤A\bold{A}^\top \bold{A}는 다음과 같이 쓸 수 있다.
A⊤A=(VΣ⊤U⊤)(UΣV⊤)=VΛV⊤\bold{A}^\top \bold{A} = (\bold{V} \boldsymbol{\Sigma}^\top \bold{U}^\top)(\bold{U} \boldsymbol{\Sigma} \bold{V}^\top) = \bold{V} \boldsymbol{\Lambda} \bold{V}^\top
•
이것은 행렬 A\bold{A}의 특잇값의 제곱(과 0)이 분산행렬 A⊤A\bold{A}^\top \bold{A}의 고윳값, 행렬 A\bold{A}의 오른쪽 특이벡터가 분산행렬 A⊤A\bold{A}^\top \bold{A}의 고유벡터가 된다는 의미이다.
◦
유니터리 행렬에 대해 U⊤U=I\bold{U}^\top \bold{U} = \bold{I}가 된다.
•
위 식을 뒤집으면 다음과 같다.
AA⊤=(UΣV⊤)(VΣ⊤U⊤)=U(ΣΣ⊤)U⊤\bold{AA}^\top = (\bold{U} \boldsymbol{\Sigma} \bold{V}^\top)(\bold{V} \boldsymbol{\Sigma}^\top \bold{U}^\top) = \bold{U}(\boldsymbol{\Sigma \Sigma}^\top)\bold{U}^\top
•
이렇게 되면 U\bold{U}는 AA⊤\bold{AA}^\top의 고유벡터가 된다.
◦
마찬가지로 V\bold{V}가 유니터리 행렬이므로 V⊤V=I\bold{V}^\top \bold{V} = \bold{I}가 된다.

참조

•
Made with