[선형대수학] 직사각형 행렬의 대각화: 특이값 분해(Singular value decomposition, SVD)

선형대수학에서 고유값과 고유벡터를 구하는 것은 매우 중요한 일이다. 그런데 고유값과 고유벡터는 정방행렬일때만 가능하다. 행렬이 직사각형 모양일 때는 고유값을 구하는 것이 불가능하다. 그래서 나온 것이 바로 특이값 분해이다. 특이값분해로 논문을 검색해보면 셀수없을 만큼 많은 논문이 검색될 정도로 다양한 분야에서 활용되고 있는 친구이므로 잘 이해하도록 하자. 

▶ 고유값 분해(eigendecomposition) 복습

우선 고유값 분해에 대해 잠시 복습하자. 고유값 분해는 정방행렬을 대각화하는 방법이다. 고유값 분해를 통해서 정방행렬은 고유벡터행렬과 고유값행렬로 분해된다. 

...(공식1: 고유값 분해)

여기서 S는 고유벡터행렬이고 는 고유값행렬로 행렬 A의 고유값들을 대각요소로 갖고 있다. 만약 행렬 A가 대칭행렬(symmetric matrix)이라면, 공식1은 아래와 같이 다시 쓰일 수 있다:

...(공식1-1: 대칭행렬의 고유값 분해) 

Q 역시 고유벡터행렬인데 고유벡터들이 정규직교(orthonormal)인 직교행렬(orthogonal matrix)이기 때문에 S 대신 Q로 표현된다. 그리고 직교행렬의 역행렬은 그 자신의 전치행렬(transpose)이므로 대신에 로 표현된다. 이기 때문이다. 

▶ 특이값 분해(Singular value decomposition, SVD)란? 

특이값 분해 역시 고유값분해처럼 행렬을 대각화하는 방법이다. 고유값 분해는 정방행렬에만 사용가능했다면, 특이값 분해는 직사각형 행렬일 때도 사용가능하다. 그러다보니 고유값 분해보다 활용도가 훨씬 더 크다. 일단 m x n 행렬의 특이값 분해 공식은 아래와 같다. 

...(공식2: 특이값 분해)

여기서 U(m x m 행렬), V(n x n 행렬)는 각각 서로 다른 직교행렬로써 특이벡터행렬들이고, 는 특이값()들을 대각요소로 갖고 있는 대각행렬로서 특이값 행렬이라고 불린다. 참고로 r은 행렬A의 rank이다. 그런데 고유값 행렬과 다르게 특이값 행렬은 직사각형행렬(m x n)이다. 만약 m > n인 직사각형 행렬이라면, 

이 되고, m < n이라면,

이 된다. 그러면 , U, V는 각각 어떤 방법으로 구할 수 있을까? 우선 행렬 A의 특이값들은 또는 의 0이 아닌 고유값들에 루트를 씌운 것이다. 와 는 동일한 고유값들을 갖는다. U는 의 고유벡터 행렬이고, V는 의 고유벡터 행렬이다. U와 V는 정규직교벡터들을 열벡터로 갖는 직교행렬인데, 처음 r개의 열벡터는 0이 아닌 고유값들에 해당하는 고유벡터들로 채우면 되고 나머지는 그것들에 직교인 정규직교벡터를 자유롭게 찾아서 채워넣으면 된다. 

예제1>> 

그러면 하나의 직사각형 행렬을 특이값 분해해보자.

 

행렬 A의 특이값들을 찾기 위해 먼저 또는 의 고유값을 구한다. 부터 시작해보자. 

의 고유값이 이라고 하면, 의 고유값들의 합 은 의 대각요소들의 합과 같고, 고유값들의 곱 은 행렬식의 값과 같으므로 아래와 같이 된다.  

따라서, 의 고유값들은 3, 1이다. 이것들에 루트를 씌운 것이 행렬A의 특이값이다. 따라서 이 특이값이다. 특이값 행렬 은 특이값들을 대각요소로 갖고 있는 m x n 행렬로(여기서는 2 x 3) 아래와 같다. 

  

의 고유값을 구해도 동일하게 3,1이 나올 것이다. 정말 그런지 한번 해보자. 

아래와 같이 고유값을 구하면,

3, 1, 0이 의 고유값으로 계산된다. 이 중에서 0이 아닌 고유값들은 3과 1이므로 의 고유값들과 동일함을 확인할 수 있다. 특이값행렬을 구했으니 이번에는 특이벡터행렬들 U와 V를 구해보자. U는 의 고유벡터들을 열로 가진 행렬이므로, 의 고유벡터를 구해야한다. 의 고유값이 3일때, 

를 만족시키는 정규직교인 고유벡터를 구하면

이다.  의 고유값이 1일때, 

를 만족시키는 정규직교인 고유벡터를 구하면

이다. 따라서 왼쪽 특이벡터행렬은 

이 된다. 이번에는 의 고유벡터들로 이뤄진 오른쪽 특이벡터행렬 V를 구해보자. 의 0이 아닌 고유값 3, 1에 대해서 고유벡터들을 각각 구하면(과정생략), 

이 되고, 마지막 남은 한 열은 이들과 직교인 정규직교벡터를 하나 채워넣으면 된다. 

V의 세번째 열벡터를 찾았다. 따라서, 오른쪽 특이벡터행렬은 

 

이다. , U, V를 모두 구했으므로 행렬A는 아래와 같이 특이값분해된다. 

예제1 끝! 

일반적인 직사각형 행렬에 특이값 분해를 시행해보았다. 만약에 행렬 A가 양의 정부호라면 로 고유값 분해와 특이값 분해가 같아진다. 

예제2>>

아래와 같은 양의 정부호 행렬은 고유값 분해와 특이값 분해가 같은지 확인해보자. 

먼저 고유값 분해부터 시작하자. 고유값을 먼저 구하면 이므로 3과 1임을 알 수 있다. 고유값 3과 1에 대해서 정규직교인 고유벡터들을 각각 암산으로 구하면,

이다. 즉 행렬 A는 고유값분해를 통해 아래와 같이 분해된다. 

이번에는 특이값분해를 실시해보자. 먼저 또는 의 고유값을 구하자. 

행렬A가 양의 정부호인 경우에 과 이 동일함을 알 수 있다. 이므로 와 의 고유값은 9와 1이다. 여기에 루트를 씌우면 행렬A의 특이값이 3과 1임을 알 수 있다. 따라서 특이값행렬 는 

이다. 이제 U와 V를 구할것인데, U와 V는 동일하다. 왜냐하면 과 이 같기 때문이다.  또는 에서 고유값 9와 1에 대응하는 정규직교인 고유벡터들을 구하면, 

이 나온다. 따라서,

이다. 특이값분해 결과 

위에서 살펴본 고유값분해의 결과와 동일함을 알 수 있다.

특이값분해 공식2는 아래와 같이 표현할 수도 있다. 

...(공식2-1: 특이값분해)

즉 각 특이값에 해당하는 좌우특이벡터들을 곱해서 만든어진 행렬들을 모두 더하는 것이다. 열벡터(m x 1) * 상수 * 행벡터(1 x n) = m x n 행렬임을 기억하자. 특이값 중에서 가장 큰 것부터 순서대로 이므로 행렬 A에 있어서 이 가장 큰 비중을 차지하고, 는 그 다음으로 큰 비중을 차지할 것이다. 이것을 이용해서 데이터를 압축할 수 있다. 

▶ 특이값 분해 활용 예: 이미지 압축

특이값 분해를 이용해서 이미지를 압축해보자. 압축 전 원본 이미지는 그림1과 같다. 

그림1. 압축 전 원본 이미지.

318 x 480의 직사각형 행렬이다. 즉 이 이미지를 표현하려면 총 318 * 480 = 152640개의 값이 필요하다. 이 이미지를 SVD를 이용해서 압축해보자. 공식 2-1을 활용할 것이다. 위에서 설명한대로 특이값의 크기가 큰 항일수록 데이터를 표현하는데 큰 비중을 차지한다. 318개의 항 중에서 특이값이 큰 순서대로 100개의 항만 사용해서 이미지를 표현한다면 어떻게 될까? 즉, 와 같이 표현해보자는 말이다. 그 결과 이미지는 그림2에 있다. 

그림2. SVD를 통해 압축된 이미지. 318개 항 중에 100개만 사용했을 때.

보기에 원본 이미지와 큰 차이가 없다. 약간 디테일함이 떨어지는 것이 보이기도 하지만. 이때 필요한 데이터의 양을 계산해보면 왼쪽 특이벡터행렬에서 318*100, 오른쪽 특이벡터행렬에서 480*100, 그리고 100개의 특이값을 모두 더하면 318*100 + 480*100 + 100 = 79900으로 원본 이미지에 비해 필요한 데이터의 양이 거의 절반으로 줄어들었다. 압축률은 79900/152640 * 100 = 52.35%이다. 

이번에는 318개의 항중에서 25개만 사용해보자(그림3). 

그림3. SVD를 통해 압축된 이미지. 318개 항 중에 25개만 사용했을 때.

이번에는 너무 과하게 압축된 것 같다. 그래도 대강 어떤 이미지인지는 알 수 있다. 이때 필요한 데이터의 양은 318*25 + 480*25 + 25 = 19975로, 압축률은 19975/152640 * 100 = 13.09%이다. 상당히 데이터량이 줄어들었다. 

원본(152640): 100% -> 100개항 활용시(79900): 52.35% -> 25개항 활용시(19975): 13.09%

만약 와 같이 처음 25개 항을 제외하고 26번째 항부터 마지막 항까지 더했을 때는 어떻게 될까? (그림4 참고) 

  

그림4. 큰 특이값을 가지고 있는 항들은 이미지의 전체적 구조를 나타내는 반면, 상대적으로 작은 특이값을 가지고 있는 항들은 이미지의 디테일한 부분들을 담당한다.

이것을 통해 알 수 있는 것은 이미지에 대한 전반적인 정보는 큰 특이값이 곱해져있는 항들에서 얻을 수 있고, 좀 더 디테일한 부분들은 작은 특이값들이 곱해져 있는 항들에서 얻을 수 있다는 것이다. 그러니까 사람들 눈에 비교적 덜 띄는 고주파 신호를 어느 정도 무시하는 것은 JPEG과 같은 압축방식에서도 사용되는 것처럼 매우 합리적인 것이다. 너무 많이 무시하면 안되겠지만. 

▶ 정리

오늘은 너무나도 중요한 특이값분해에 대해서 정리해보았다. 특이값분해는 고유값 분해와 함께 행렬을 대각화하는 방법인데, 고유값분해는 정방행렬에만 사용할 수 있는 반면, 특이값분해는 좀 더 확장되어 직사각형행렬에도 사용가능하다. 고유값 분해와 특이값 분해는 행렬이 양의 정부호일때만 동일하고, 나머지 경우에는 다르다. 특이값 분해는 데이터 압축 등 많은 분야에서 활용되고 있다. 

U: 의 고유벡터들을 열벡터로 갖는 m x m 직교행렬

V: 의 고유벡터들을 열벡터로 갖는 n x n 직교행렬  

: 또는 의 0이 아닌 고유값들을 대각요소로 갖는 m x n 대각행렬

<참고자료>

[1] Gilbert Strang, Linear algebra and its applications, 4판, p. 331-334.