기초 수학 - 특이값 분해(SVD)

특이값 분해

정방 행렬에만 적용이 가능했던 고유값 분해와 달리 특이값 분해는 정방 행렬이 아닌 대부분의 행렬에 적용이 가능한 특징을 가지고 있다. 행렬을 고유 벡터, 고유값과 유사하게 단일 벡터로 분해한다.

특이값 분해는 행렬을 단일 벡터로 분해하며 행렬 A는 $ A = UDV^T $로 구성되게 된다. 행과 열의 개수도 추가하여 더 자세하게 표현하면 $ A_{mn} = U_{mm} D_{mn} V^T_{nn} $로 표현된다. 또한 이러한 방식은 Full Matrix SVD라고 표현한다.

U: m x m 크기의 가진 직교 행렬(좌특이행렬)

D: m x n 크기의 대각 행렬(대각 원소들은 특이값으로 이루어짐)

$ V^T $: n x n 크기의 직교 행렬(우특이행렬)

import numpy as np

A = np.array([[-1, 2],
              [3, -2],
              [5, 7]])

U, D, VT = np.linalg.svd(A)

print("U: \\n", U, "\\n")
print("D: \\n", D, "\\n")
print("VT: \\n", VT, "\\n")

"""
U: 
 [[ 0.12708324  0.47409506  0.87125411]
 [ 0.00164602 -0.87847553  0.47778451]
 [ 0.99189069 -0.0592843  -0.11241989]] 

D: 
 [8.66918448 4.10429538] 

VT: 
 [[ 0.55798885  0.82984845]
 [-0.82984845  0.55798885]] 
"""

Numpy로 특이값 분해를 하려면 svd함수를 사용한다. 순서대로 U, D, VT값이 나온다. 이 결과값을 바탕으로 U, D, $ V^T $가 내적했을 때 A행렬이 나오는지 확인해보자.

먼저 D는 대각 행렬이기에 diag()함수로 대각 행렬로 만들어 준다. 그 후, $ V^T $와 내적하고 U와도 내적하기 위해선 3행으로 이뤄져야 한다. 대각 행렬이 된 D밑에 [ 0, 0] 을 추가한 후 내적하면 A 행렬 값이 나온다.

import numpy as np

A = np.array([[-1, 2],
              [3, -2],
              [5, 7]])

U, D, VT = np.linalg.svd(A)
D = np.concatenate((np.diag(D), [[0, 0]]), axis=0) # 대각 행렬로 변경 및 [0, 0] 추가

svd_value = np.dot(U, np.dot(D, VT))
print(svd_value)

"""
[[-1.  2.]
 [ 3. -2.]
 [ 5.  7.]]

"""

 

이번에는 svd메서드를 사용하지 않고 svd를 계산해보자

import numpy as np

A = np.array([[1, 4, 1], [-4, -7, 1]]) # 원본 행렬

eig_values_U, eig_vectors_U = np.linalg.eig(np.dot(A, A.T)) # U: 고유값, 고유 벡터 구하기
idx = np.argsort(eig_values_U)[::-1] # 고유값 크기에 따라 내림차순 정렬
eig_values_U = eig_values_U[idx] # 고유값 정렬
eig_vectors_U = eig_vectors_U[:, idx] # 고유 벡터 정렬
U = eig_vectors_U # U

S = np.concatenate((np.diag(eig_values_U), np.array([[0, 0]]).T), axis=1)
# np.diag()로 고유 값들을 대각 행렬로 만든다.
# 생성된 대각 행렬에 0으로 이뤄진 벡터를 추가하기 위해 concatenate를 사용한다.
# Sigma는 (3, 3)인 V와 계산을 하기 때문에 (2, 3) 형식으로 만들어야 한다. (내적을 하려면 앞, 뒤 행렬의 열과 행 값이 같아야 한다.)
# 이로 인해 0으로 이뤄진 열을 추가한다.(axis=1)
S = np.sqrt(S) # 생성된 대각 행렬의 제곱근이 Sigma다.

eig_values_V, eig_vectors_V = np.linalg.eig(np.dot(A.T, A)) # V: 고유값, 고유 벡터 구하기
idx = np.argsort(eig_values_V)[::-1] # 고유값 크기에 따라 내림차순 정렬
eig_values_V = eig_values_V[idx] # 고유값 정렬
eig_vectors_V = eig_vectors_V[:, idx] # 고유 벡터 정렬
V = eig_vectors_V # V

svd_res = np.dot(U, np.dot(S, V.T)) # 내적 계산
print(svd_res) # 결과값

"""
[[-1. -4. -1.]
 [ 4.  7. -1.]]
"""

np.linalg.svd()를 사용하지않고 고유 값, 고유 벡터도 SVD값을 계산할 때, 부호가 다르게 나와 꽤 오랜기간 이유를 찾아내는데 소비하였다. 결과적으로는 부호가 달라도 상관없다는 것이다. 행렬을 뒤집거나 뒤트는 등의 변환을 알고리즘에 따라 달리 주어지기에 값만 같으면 상관없다는 글을 보았다. 또한 궁극적으론 행렬의 부호가 달라도 분해된 행렬의 크기는 동일하다. 이 글을 따라 직접 파이썬 코드로 검증 하는 사람들이 이 부분에서 헤매지 않았으면 좋겠다.

 

Pytorch SVD

# Pytorch SVD
import torch

A = torch.tensor([[1, 4, 1], [-4, -7, 1]], dtype=torch.float64)
U, S, VT = torch.linalg.svd(A, full_matrices=True)

S = torch.cat((torch.diag(S), torch.tensor([[0, 0]]).T), axis=1) # 열 추가 및 대각 행렬화

res = torch.mm(U, torch.mm(S, VT)) # 내적
print(res)

"""
tensor([[ 1.0000,  4.0000,  1.0000],
        [-4.0000, -7.0000,  1.0000]], dtype=torch.float64)
"""

Pytorch는 torch.linalg.svd()로 svd를 진행할 수 있다.

cat()으로 열을 추가하고 diag()로 대각 행렬화 하여 S를 완성할 수 있다.

 

Tensorflow SVD

# Tensorflow SVD
import tensorflow as tf

A = tf.Variable([[1, 4, 1], [-4, -7, 1]], dtype=tf.float64)
S, U, VT = tf.linalg.svd(A)
res = tf.matmul(U, tf.matmul(tf.linalg.diag(S), VT, adjoint_b=True)) # adjoin_b로 두 번째 행렬 전치

print(res)

"""
tf.Tensor(
[[ 1.  4.  1.]
 [-4. -7.  1.]], shape=(2, 3), dtype=float64)
"""

Tensorflow는 svd를 하면 나오는 값의 순서가 다르다. 먼저 대각 행렬 느낌의 시그마, 좌특이벡터, 그리고 우특이벡터 순으로 출력된다. tensorflow의 svd는 VT값이 (2, 3)으로 나오기에 내적하기 전에 전치를 해야한다. adjoin_b로 뒤 파라미터를 전치한 후 내적을 진행해야 한다.

adjoint_a: 내적 앞 파라미터의 전치 여부

adjoint_b: 내적 뒤 파라미터의 전치 여부

 

Reduced SVD

Reduced SVD는 행렬의 계수만큼 행 또는 열을 제외한 후 특이값 분해를 진행하는 과정을 의미한다. 행렬 계수가 r이라면 $ A_{mn} = U_{mr}S_{rr}V^T_{rn} $ 식으로 특이값 분해가 진행된다.

# Reduced SVD
import numpy as np

A = np.array([[1, 4, 1], [-4, -7, 1]])

A_rank = np.linalg.matrix_rank(A)
print("A Rank: ", A_rank) # 계수

U, S, VT = np.linalg.svd(A, full_matrices=False)
print("U: \\n", U, "\\n")
print("S: \\n", S, "\\n")
print("VT: \\n", VT, "\\n")

print(U @ np.diag(S) @ VT)

"""
A Rank:  2
U: 
 [[-0.440356    0.89782325]
 [ 0.89782325  0.440356  ]] 

S: 
 [9.01135903 1.6719475 ] 

VT: 
 [[-0.44739634 -0.89289382  0.05076562]
 [-0.51652383  0.3043164   0.80037157]] 

[[ 1.  4.  1.]
 [-4. -7.  1.]]
"""

A 행렬의 계수가 2이므로 U는 m x r 인 (2, 2)크기로 구해지고, S는 대각행렬하여 r x r인 (2, 2)크기가 된다. 마지막으로 VT는 r x n인 (2, 3) 크기로 구해진다. diag()메서드로 S를 대각행렬로 만든 후 검증하면 원래 행렬인 A가 나오는 것을 확인할 수 있다.

 

Truncated SVD

Truncated SVd는 Reduced SVD에서 차원을 더 축소한 특이값 분해이다. 범위로 보면 0< k < r 로 표현할 수 있으며 계수보다 작으면서 0보다 큰 값을 k로 임의 지정한 후 그만큼 축소를 한다.

# Truncated SVD
import numpy as np

A = np.array([[1, 1, 1], [3, 3, 3]])
A_rank = np.linalg.matrix_rank(A)
print(A_rank) # 1

계수가 1인 A 행렬에서 K를 2로 지정하여 특이값 분해를 진행해보자

# Truncated SVD
import numpy as np
from scipy.sparse.linalg import svds
from scipy.linalg import svd

k = 1
A = np.array([[1, 1, 1], [3, 3, 3]], dtype=np.float64)

U, S, V = svds(A, k)

print(np.dot(U @ np.diag(S), V))

"""
array([[1., 1., 1.],
       [3., 3., 3.]])
"""

기존과는 다르게 Scipy를 사용하였다. numpy에는 truncated svd옵션이 없기 때문이다. 두번째 파라미터에 k값을 지정하여 쉽게 truncated svd를 계산할 수 있다.

 

SVD를 사용하는 이유

SVD를 사용하는 이유는 데이터 차원을 줄여 중요한 정보를 추출하기 위함이다. 데이터 차원을 줄인다는 의미는 위에서 봤던 Reduced SVD, Truncated SVD를 통해 차원을 축소한다는 의미이다. 차원을 축소시켜 불필요한 데이터를 제외하여 데이터를 효율적으로 표현할 수 있다.

간단한 예로 이미지를 예시로 들 수 있다. 만약 4000 x 4000 픽셀로 이루어진 이미지의 픽셀을 줄여 200 x 200 픽셀에서도 동일한 이미지라고 자각할 수 있게 할 수 있다. 이를 통해 직관적인 계산 비용이 4000에서 200으로 확 줄어드는 효과를 얻을 수 있다. 다음 포스팅에서 데이터 차원을 줄인다는 의미를 다뤄볼 예정이다.

 

---

참고 사이트:

https://stackoverflow.com/questions/49453600/numpy-svd-giving-wrong-values

numpy SVD giving wrong values?

 

https://stackoverflow.com/questions/52486435/why-is-my-svd-calculation-different-than-numpys-svd-calculation-of-this-matrix

Why is my SVD calculation different than numpy's SVD calculation of this matrix?

 

https://stackoverflow.com/questions/68399324/why-does-my-own-simple-implemantion-of-the-svd-algorithm-in-python-not-work

Why does my own simple Implemantion of the svd algorithm in python not work?

 

https://medium.com/geekculture/singular-value-decomposition-calculation-using-eigenvalues-and-eigenvectors-in-python-dde785559174

Singular Value Decomposition: Calculation using EigenValues and EigenVectors in Python

 

https://stackoverflow.com/questions/76097333/svd-with-matlab-numpy-and-pytorch

SVD with matlab, numpy and pytorch

 

https://math.stackexchange.com/questions/2627005/are-reduced-svd-and-truncated-svd-the-same-thing

Are reduced SVD and truncated SVD the same thing?

 

https://colab.research.google.com/drive/10jj2QPnmGSA8jLiLcMxLrdWflVErALGw?usp=sharing

특이값 분해.ipynb