[선형대수학 #4] 특이값 분해(Singular Value Decomposition, SVD)의 활용

수학 이야기 2013.10.23 09:43

활용도 측면에서 선형대수학의 꽃이라 할 수 있는 특이값 분해(Singular Value Decomposition, SVD)에 대한 내용입니다. 보통은 복소수 공간을 포함하여 정의하는 것이 일반적이지만 이 글에서는 실수(real) 공간에 한정하여 내용을 적겠습니다.



1. 특이값분해(Singular Value Decomposition, SVD)


특이값 분해(SVD)는 고유값 분해(eigendecomposition)처럼 행렬을 대각화하는 한 방법이다. 그런데, 특이값 분해가 유용한 이유는 행렬이 정방행렬이든 아니든 관계없이 모든 m x n 행렬에 대해 적용 가능하기 때문이다. [선형대수학 #3] 고유값과 고유벡터 (eigenvalue & eigenvector)에서 다루었던 고유값 분해(EVD)는 정방행렬에 대해서만 적용 가능하며 또한 정방행렬 중에서도 일부 행렬에 대해서만 적용 가능한 대각화 방법임을 상기하자.


실수공간에서 임의의 m x n 행렬에 대한 특이값분해(SVD)는 다음과 같이 정의된다.


 --- (1)



U는 AAT를 고유값분해(eigendecomposition)해서 얻어진 직교행렬(orthogonal matrix)로 U의 열벡터들을 A의 left singular vector라 부른다. 또한 V는 ATA를 고유값분해해서 얻어진 직교행렬로서 V 의 열벡터들을 A의 right singular vector라 부른다.  left, right가 상당히 햇갈리는데 그냥 Σ의 왼쪽에 있는 U가 left singular 벡터, 오른쪽에 있는 V가 right 특이벡터들이라고 생각하면 된다. 마지막으로, Σ는 AAT, ATA를 고유값분해해서 나오는 고유값(eigenvalue)들의 square root를 대각원소로 하는 m x n 직사각 대각행렬로 그 대각원소들을 A의 특이값(singular value)이라 부른다. U, V가 직교행렬(orthogonal matrix)이라 함은 UUT = VVT = E, U-1=UT, V-1=VT임도 기억하자.


U의 열벡터(ui): left singular vectors of A (AAT의 eigenvector)

V의 열벡터(vi): right singular vectors of A (ATA의 eigenvector)

Σ의 대각원소(σi): singular values of A (ATA, AAT의 eigenvalue들의 square root)

 --- (2)


이전 글인 [선형대수학 #3] 고유값과 고유벡터 (eigenvalue & eigenvector)에서 설명했듯이 대칭행렬(symmetric matrix)은 항상 고유값 분해(eigendecomposition)가 가능하며 더구나 직교행렬(orthogonal matrix)로 대각화할 수 있다. 그런데, AAT와 ATA는 모두 대칭행렬(symmetric matrix)이므로 위와 같은 고유값 분해가 항상 가능하다.


여기서 재미있는 사실은 AAT와 ATA의 고유값들은 모두 0 이상(nonnegative)이며 0이 아닌 고유값들은 서로 동일하다는 점이다. 고유값들이 0 이상이어야 square root를 씌울수 있으며 또한 서로 동일해야만 하나의 행렬 Σ로 표현할 수 있을 것이다.


i) ATA의 고유값을 λ, 고유벡터를 v (v≠0)라 했을 때, ATAv = λv 이다. 양변에 vT를 곱해보면 vTATAv = λvTv 에서 (Av)TAv = λvTv 즉, ∥Av∥2 = λ∥v∥2 이므로 λ≥0 이다.


ii) ATA의 0이 아닌 고유값을 λ, 고유벡터를 v (v≠0)라 했을 때, 정의에 의해 (ATA)v=λv 이다. 양변에 A를 곱해보면 A(ATA)v = λAv 즉, AAT(Av) = λ(Av)이므로 Av≠0라면 λ는 또한 AAT의 고유값임을 알 수 있다. 그런데, 만일 Av=0라 하면 (ATA)v=λv에서 λ=0이어야 하므로 Av≠0이다. 동일한 방식으로 AAT의 0이 아닌 모든 고유값도 또한 ATA의 고유값이 됨을 쉽게 보일 수 있다.


이와같이, AAT와 ATA의 공통의 고유값 σ12≥σ22≥ ... ≥σs2≥0 (단, s = min(m, n))들을 구한 후 이들의 square root를 취한 σ1≥σ2≥ ... ≥σs≥0 이 A의 특이값(singular value)들이고 이들을 대각원소로 하는 m x n 직사각 대각행렬이 Σ이다 (식 (2)). 여기서 행렬의 특이값(singular value)은 모두 0 이상임을 기억하자.


참고로 행렬 A의 특이값(singular value)을 σi, left singular vector를 ui, right singular vector를 vi라 했을 때 다음 식이 성립한다.


 --- (3)


※ 어떤 행렬 A가 singular하다는 말은 특이값 분해와는 조금 다른 말이다. 행렬 A가 singular하다는 말은 정방행렬(square matrix)에 대해서만 해당되는 말로 A의 역행렬이 존재하지 않는다는 말이다. 즉, det(A) = 0인 정방행렬을 특이행렬(singular matrix)이라고 부른다. 단, 정방행렬에 대해서도 특이값 분해를 하게 되면 그 행렬이 singular한지 안한지를 바로 알 수 있다. 정방행렬 A의 특이값들이 모두 0이 아니면 이 행렬은 nonsingular 즉, 역행렬이 존재하고 특이값중 0이 포함되면 singular 즉, 역행렬이 존재하지 않는다.


※ 특이값의 부호가 양수인 이유

앞서 singular value는 AAT, ATA의 고유값분해(EVD)에서 나온 고유값의 square root를 취한 것이라고 했다. 그런데, 고유값의 square root는 +, - 2개의 값이 나오는데 왜 +값만 singular value로 잡은 것일까? 사실 원래는 singular value를 +로 잡을수도, -로 잡을수도 있다. 하지만 +를 singular value로 잡는 것은 일종의 수학적 약속이다. 만일 식 (1)에서 i번째 singular value의 부호를 바꿨을 때 U의 i번째 열벡터의 부호를 같이 바꾸면 식 (1)은 여전히 성립함을 알 수 있다. 또한 U가 직교행렬(orthogonal matrix)란 점도 변하지 않는다. 어쨌든, 특이값(singular value)은 항상 0 이상(nonnegative)임을 기억하자.


※ positive definite, negative definite

선형대수학에서 보면 가끔 어떤 행렬 A가 positive definite다, positive semidefinite다 하는 용어들이 나오는데 이는 대칭행렬(symmetric matrix)에 대해서만 정의되는 용어들로서 이 용어들의 정의는 다음과 같다.


 


즉, 어떤 대칭행렬 A가 영벡터가 아닌 모든 열벡터 z에 대해 항상 zTAz>0을 만족할 때 이 행렬을 positive definite 행렬이라고 부르며 negative definite 등도 유사하게 정의된다. 그런데 이러한 행렬들의 중요한 성질은 고유값(eigenvalue)도 동일한 부호를 갖는다는 점이다. 즉, 어떤 대칭행렬 A가 positive definite하면 이 행렬의 모든 eigenvalue은 항상 양수이다. 만일 A가 positive semidefinite하면 eigenvalue들도 ≥0이고, negative definite면 모든 eigenvalue들이 음수이다. 앞서, SVD를 구하는 과정에서 나왔던 AAT, ATA는 positive semidefinite 행렬들로서 항상 0 이상의 eigenvalue들을 갖는다.



2. 특이값분해(SVD)의 기하학적 의미


행렬을 x' = Ax와 같이 좌표공간에서의 선형변환으로 봤을 때 직교행렬(orthogonal matrix)의 기하학적 의미는 회전변환(rotation transformation) 또는 반전된(reflected) 회전변환, 대각행렬(diagonal maxtrix)의 기하학적 의미는 각 좌표성분으로의 스케일변환(scale transformation)이다.


행렬 R이 직교행렬(orthogonal matrix)이라면 RRT = E이다. 따라서 det(RRT) = det(R)det(RT) = det(R)2 = 1이므로 det(R)는 항상 +1, 또는 -1이다. 만일 det(R)=1라면 이 직교행렬은 회전변환을 나타내고 det(R)=-1라면 뒤집혀진(reflected) 회전변환을 나타낸다.


따라서 식 (1), A = UΣVT에서 U, V는 직교행렬, Σ는 대각행렬이므로 Ax는 x를 먼저 VT에 의해 회전시킨 후 Σ로 스케일을 변화시키고 다시 U로 회전시키는 것임을 알 수 있다.


<그림1> 출처: 위키피디아


즉, 행렬의 특이값(singular value)이란 이 행렬로 표현되는 선형변환의 스케일 변환을 나타내는 값으로 해석할 수 있다. 


고유값분해(eigendecomposition)에서 나오는 고유값(eigenvalue)과 비교해 보면 고유값은 변환에 의해 불변인 방향벡터(-> 고유벡터)에 대한 스케일 factor이고, 특이값은 변환 자체의 스케일 factor로 볼 수 있다.


☞ 이 주제와 관련하여 조금 더 상상의 나래를 펴 보면, m x n 행렬 A는 n차원 공간에서 m 차원 공간으로의 선형변환이다. n차원 공간에 있는 원, 구 등과 같이 원형으로 된 도형을 A에 의해 변환시키면 먼저 VT에 의해서는 회전만 일어나므로 도형의 형태는 변하지 않는다. 그런데 Σ에 의해서는 특이값의 크기에 따라서 원이 타원이 되거나 구가 럭비공이 되는 것과 같은 식의 형태변환이 일어난다 (n이 2차원인 원의 경우 첫번째 특이값 σ1은 변환된 타원의 주축의 길이, 두번째 특이값 σ2는 단축의 길이에 대응된다). 이후 U에 의한 변환도 회전변환이므로 도형의 형태에는 영향을 미치지 못한다. 만일 m>n이라면  0을 덧붙여서 차원을 확장한 후에 U로 회전을 시키는 것이고 m<n이라면 일부 차원을 없애버리고(일종의 투영) 회전을 시키는 셈이다. 결국 선형변환 A에 의한 도형의 변환결과는 형태적으로 보면 오로지 A의 특이값(singular value)들에 의해서만 결정된다는 것을 알 수 있다.



3. Reduced SVD와 행렬근사, 데이터 압축


아래와 같이 행렬 m×n 행렬 A를 SVD로 분해하는 것을 full SVD라 부른다 (단, m>n)


<그림 2> full SVD


그런데,  실제로 이와같이 full SVD를 하는 경우는 드물며 아래 그림들과 같이 reduced SVD를 하는게 일반적이다 (s=n개의 singular value들 중 0이 아닌 것들의 개수가 r개, t<r라고 가정).


<그림 3> thin SVD


<그림 4> Compact SVD


<그림 5> Truncated SVD


<그림 3>은 Σ에서 대각파트가 아닌 0으로 구성된 부분을 없애고 U에서는 이에 대응되는 열벡터들를 제거한 형태이고(thin SVD라 부른다) <그림 4>는 비대각 원소들뿐만 아니라 0인 singular value들까지 모두 제거한 형태이다(compact SVD). 이 때, 이렇게 계산된 A가 원래의 A와 동일한 행렬이 나옴은 쉽게 확인할 수 있다. 그러나, <그림 5>의 경우는 0이 아닌 singular value까지 제거한 형태로서(truncated SVD) 이 경우에는 원래의 A가 보존되지 않고 A에 대한 근사행렬 A'이 나온다.


그런데, 이렇게 truncated SVD로 근사한 행렬 A'은 matrix norm ∥A-A'∥을 최소화시키는 rank t 행렬로서 데이터압축, 노이즈제거 등에 활용될 수 있다.


데이터 압축의 한 예로 아래와 같은 600 × 367 이미지를 SVD로 압축해 보자.


<그림 6> Wallis의 "dressed to kill" 광고 이미지들중 하나


이 이미지의 픽셀값을 원소값으로 하는 600 × 367 행렬 A를 잡고 SVD를 한 후, truncated SVD를 이용하여 근사행렬 A'을 구한 후 이를 다시 이미지로 표시해 보면 다음과 같다 (통상적인 m>n 형태로 만들기 위해 원래 이미지를 90도 회전시킨 후 SVD를 적용).


<그림 7> 100개의 singular value로 근사 (t = 100)


<그림 8> 50개의 singular value로 근사 (t = 50)


<그림 9> 20개의 singular value로 근사 (t = 20)


위 그림들 중 t=20인 경우의 데이터 압축율은 8.8%이다. 원래 이미지를 표현하기 위해서는 367*600 = 220,200의 메모리가 필요하다. 그런데, <그림 9> t = 20인 경우에는 600*20(U) + 20(Σ) + 20*367(V) = 19,360이므로 압축률은 19,360/220,200*100 = 8.8% 이다. 화질을 보면 좋은 압축 방법은 아님을 알 수 있지만 truncated SVD를 통한 데이터 근사가 원래의 데이터 핵심을 잘 잡아내고 있음을 알 수 있다.



4. 특이값 분해(SVD)와 pseudo inverse, 최소자승법(least square method)


pseudo inverse, 수도우 인버~스 (한글로 발음을 적고 보니 참 낯서네요).. 어쨌든 굳이 번역하자면 의사역행렬 정도이다.


선형시스템 Ax = b가 있을 때, 만일 A의 역행렬이 존재한다면 이 시스템의 해는 x = A-1b 로 손쉽게 구할 수 있다. 그러나 대부분의 실제 문제들에 있어서 역행렬이 존재하는 경우는 거의 없다고 봐도 무방하며 이런 경우 사용할 수 있는 것이 pseudo inverse이다. A의 pseudo inverse를 A+라면 A의 역행렬이 없는 경우 Ax = b의 해는 x = A+b와 같이 계산하고 이렇게 구한 x는 ∥Ax-b∥를 최소화하는 해가 된다. 이렇게 pseudo inverse를 이용하여 해를 구하는 것은 최소자승법, least square method와 같은 의미가 된다.


원래 역행렬(inverse matrix)은 정방행렬(square matrix)에 대해서만 정의된다. 하지만 pseudo inverse는 임의의 m x n 행렬에 대해서 정의될 수 있으며 특이값분해(SVD)는 pseudo inverse를 계산하는 가장 강력한(안정적인) 방법 중 하나이다.


행렬 A의 특이값분해(SVD)가 A = UΣVT라면 A의 pseudo inverse는 VΣ+UT로 계산되고 A+로 표기한다 (단, Σ+는 원래의 Σ에서 0이 아닌 singular value들의 역수를 취한 후 transpose를 시킨 행렬).




 --- (4)


U, V의 순서가 바뀌고 Σ도 m x n에서 n x m 행렬로 바뀜에 주의하자. 그리고 만일 특이값(singular value)들 중 0이 포함된 경우에는 0이 아닌 특이값들만 역수를 취하고 원래의 0은 Σ+에도 그대로 0으로 놔둔다 (즉, 0이 아닌 경우만 역수).


[참고사항1]

만일 모든 singular value들이 양수이고 m≥n이면 A+A는 n x n 단위행렬(identity matrix)이 된다. 만일 m≤n인 경우에는 AA+가 단위행렬(m x m)이 된다. 그리고 만일 0인 singular value가 포함되면 어떤 순서로 곱해도 단위행렬은 나오지 않는다.


--- (5)


 --- (6)


보통 우리가 선형연립방정식에서 pseudo inverse를 적용하는 경우는 m≥n인 즉, 식(데이터)의 개수가 미지수의 개수보다 많은 경우로서 Ax = b의 양변의 앞쪽에 A+를 곱하여 A+Ax = A+b => x = A+b의 형태로 x를 구하는 것이다.


m × n 행렬 A에 대해 SVD를 할 경우에는 보통 m>n인 행렬을 대상으로 하는 것이 일반적이다. m<n인 경우는 선형연립방정식으로 보면 미지수의 개수가 식의 개수가 많은 경우로서 해가 유일하게 결정되지 않는다. 이는 마치 점 2개를 가지고 평면을 결정하라는 문제와 같다. 따라서 특이값분해(SVD)를 통해 pseudo inverse를 구하는 것은 m>n인 행렬을 대상으로 한다고 생각하는게 좋다. m<n인 경우에도 pseudo inverse를 구할 수는 있지만 식 (6)과 같이 A의 뒤에 곱하는 형태로 사용해야 하므로 Ax=b 꼴 문제에는 유효하지 않다.


[참고사항2]

특이값이 0이 아니더라도 0에 매우 가까운 경우에는 노이즈로 치고 0으로 바꾼 후에 pseudo inverse를 구하는 것이 일반적이다. 즉, 어떤 행렬 A의 pseudo inverse를 SVD로 구하기 위해서는 먼저 특이값들을 구한 후에, 0에 매우 가까운 특이값들은 0으로 바꾸고 임계치 이상의 특이값들만 역수를 취해서 pseudo inverse를 구한다. 이 임계치를 SVD의 tolerance라고 부르는데, matlab에서 사용하는 tolerance 기본값은 1e-10 이다. 이는 앞서 설명한 truncated SVD와도 밀접한 관련이 있으며 어느 정도의 값을 노이즈로 볼 것인가에 따라서 즉, tolerance 값을 어떻게 줄 것인가에 따라서 결과 pseudo inverse 및 선형시스템의 해가 달라질 수 있다. 아래 예를 통해 tolerance 값에 따라서 선형시스템의 해가 어떻게 달라질 수 있는지 살펴보도록 하자.



SVD를 이용한 선형시스템 풀이 예제


예를 들어 우리나라의 1930년 ~ 2010년 사이의 10년 단위의 연도별 인구추이를 보고 2020년도 총인구수를 예측하는 문제를 생각해 보자 (자료출처: KOSIS 국가통계포털). 참고로 2012년 기준 현재 우리나라 총 인구수는 5,095만명이다.


(단위: 만명)

연도

1930

1940

1949

1960

1970

1980

1990

2000

2010

2020

인구

2,044

2,355

2,017

2,499

3,144

3,741

4,339

4,599

4,799

?


<그림 10> 우리나라 연도별 인구추이 그래프


우리나라 인구수 추이를 보면 계속 인구가 증가하다가 2000년 경부터 증가추세가 둔화되는 경향을 보이고 있다. 따라서, 우리나라 인구수 추이 모델을 2차 포물선으로 잡고 2020년도 국내 인구를 추정해 보자.


연도를 x = 1930, 1940, ..., 2010, 해당연도의 인구수를 y, 모델을 y = ax2 + bx + c로 잡자.


 --- (7)


 


--- (8)


위와 같이 선형 연립방정식을 세우고 이를 행렬식 AX = B 형태로 표현했을 때, A의 역행렬이 존재한다면 a, b, c를 바로 결정할 수 있을 것이다. 하지만 위 <그림 10> 그래프의 모든 점을 지나는 포물선은 존재하지 않을 것이므로 선형연립방정식 (7)의 해는 당연히 존재하지 않고 A의 역행렬 또한 존재하지 않는다.


이런 경우 A의 pseudo inverse A+를 구하여 X = A+B로 X를 구하면 인구추이 데이터를 least square(최소자승)로 근사하는 포물선을 구할 수 있다.


실제로 행렬 A에 대해 특이값분해(SVD)를 해 보면 다음과 같은 3개의 singular value들을 얻을 수 있다 (A가 9 × 3 행렬이므로 singular value의 개수는 총 3개 = min(3, 9)).


 --- (9)


i) σ1, σ2, σ3를 모두 사용한 full SVD 경우

full SVD를 이용하여 pseudo inverse를 구했을 경우 계산된 포물선 그래프는 아래 그림과 같다. 구해진 포물선을 이용하여 2020년도 인구를 추정해 보면 약 5,645만명 정도가 나온다 (추정된 포물선 방정식: y = 0.21*x2 - 802.59*x + 754923)

<그림 11> full SVD 근사


ii) σ1, σ2 만을 이용한 truncated SVD 경우

σ3=0으로 놓고, σ1, σ2 만을 이용해 pseudo inverse를 구했을 경우는 아래와 같은 포물선을 얻는다. full SVD에 비해 좀더 단순화된 모델로 데이터를 근사함을 볼 수 있다. 이 때, 이 포물선을 이용한 2020년도 추정 인구수는 5290만명이다 (추정된 포물선 방정식: y = 0.02*x2 - 36.07*x - 0.04).

<그림 12> truncated SVD 근사 (t=2)


iii) σ1 만을 이용한 truncated SVD 경우

σ2=σ3=0으로 모두 날려버리고 σ1만을 이용해 pseudo inverse를 구해 포물선을 구한 결과는 아래 그림과 같다. ii) 경우보다도 훨씬 더 단순화된 모델링을 하는 것을 볼 수 있다 (너무 단순화가 심해서 데이터의 미세한 변화 특성을 대부분 잃어버림). 이 경우 예측된 2020년도 인구수는 3476만명이다 (추정된 포물선 방정식: y = 0.00085*x2).

<그림 13> truncated SVD 근사 (t=1)


위 SVD 선형근사 예제에 대한 matlab 코드는 다음과 같다.

%% SVD population estimation


yr = [1930, 1940, 1949, 1960, 1970, 1980, 1990, 2000, 2010]';

pop = [2044, 2355, 2017, 2499, 3144, 3741, 4339, 4599, 4799]';


A = [yr.^2 yr ones(length(yr),1)];

B = pop;


[U D V] = svd(A);


% pseudo inverse with full SVD

D_inv = D;

D_inv(1,1) = 1/D(1,1);

D_inv(2,2) = 1/D(2,2);

D_inv(3,3) = 1/D(3,3);

A_pinv = V*D_inv'*U';

X = A_pinv*B;

pop_approx = A*X;

plot(yr, pop, '*', yr, pop_approx);


% pseudo inverse with truncated SVD (t=2)

D_inv = D;

D_inv(1,1) = 1/D(1,1);

D_inv(2,2) = 1/D(2,2);

D_inv(3,3) = 0;

A_pinv = V*D_inv'*U';

X = A_pinv*B;

pop_approx = A*X;

figure; plot(yr, pop, '*', yr, pop_approx);


% pseudo inverse with truncated SVD (t=1)

D_inv = D;

D_inv(1,1) = 1/D(1,1);

D_inv(2,2) = 0;

D_inv(3,3) = 0;

A_pinv = V*D_inv'*U';

X = A_pinv*B;

pop_approx = A*X;

figure; plot(yr, pop, '*', yr, pop_approx);


return



그런데, 위 <그림 11>의 full SVD로 근사한 결과 그래프를 보면 2000년 경부터 우리나라 인구증가 속도가 조금씩 감소하고 있는 실제 경향이 제대로 반영되지 못함을 알 수 있다. 그 이유는 1950년대 6.25 전쟁으로 인해 인구수가 급격히 감소한 부분이 전체 포물선 근사에 영향을 미쳤기 때문이다. 즉, pseudo inverse를 이용해 데이터를 근사하는 것은 전체 데이터의 근사오차를 최소화시키는 최소자승법(least square method) 근사이기 때문에 이런 문제점이 발생한다 (이와 같이 outlier가 포함된 데이터는 최소자승법으로는 잘 근사할 수 없다).


만일 1930, 1940년도 데이터는 버리고 1950년도 데이터부터만 사용하여 다시 인구수 변화를 근사하면 아래 그림과 같은 결과가 나온다. 훨씬 그럴듯한 근사결과가 나옴을 확인할 수 있으며 이 근사 결과를 이용하여 2020년도 우리나라 인구수를 예측해 보면 약 5,116만명이 나온다.


<그림 14> outlier를 제거한 full SVD 근사


그런데 정말 2020년도 우리나라 인구수가 5,116만명이 될까요?? ^^



[선형대수학 #1] 주요용어 및 기본공식

[선형대수학 #2] 역행렬과 행렬식(determinant)

[선형대수학 #3] 고유값과 고유벡터 (eigenvalue & eigenvector)

[선형대수학 #4] 특이값 분해(Singular Value Decomposition, SVD)의 활용

[선형대수학 #5] 선형연립방정식 풀이

[선형대수학 #6] 주성분분석(PCA)의 이해와 활용


by 다크 프로그래머 


저작자 표시 비영리 변경 금지
신고
  • 이전 댓글 더보기
  • 흐흐흐켱 2015.04.20 21:29 신고 ADDR 수정/삭제 답글

    svd가 뭔지 계속 궁금해하다가 블로그 보고 약간이나마 이해가 되어 너무 감사드립니다. 지금 제가 연구중인 논문에 svd와 eigenvector 내용이 나와서 계속 헷갈리네요. 질문드리고싶은 것이 하나 있습니다. 만일 분해하고 싶은 행렬을 E라고 했을 때, SVD(E)를 시도하였을 경우 나오는 U행렬과, Eigenvalue decomposition을 E*E'행렬에 대해 시도하였을 경우 나오는 행렬은 값이 동일한가요?

    • BlogIcon 다크pgmr 2015.04.21 08:02 신고 수정/삭제

      matlab 등으로 직접 확인해 보진 않았지만 같은 결과가 나올 것이라 생각합니다 (단, 열의 순서는 다를 수 있을 것 같습니다)

    • 흐흐흐켱 2015.04.21 08:35 신고 수정/삭제

      제가지금 matlab으로 코딩 중인데 [f0, v, fx] = svd(E)의 f0행렬과
      [eve eva] = eig(E*E')의 eve 행렬이 결과가 다르게 나옵니다..
      값 하나하나가 전부 달라서 지금 혼란스럽습니다.
      분명히 위키피디아도(물론 믿을만한 사이트는 아니지만) 같은 맥락으로 특이값 분해와 고유값 분해 행렬은 같다고 하였는데.. 음..

    • BlogIcon 다크pgmr 2015.04.21 09:16 신고 수정/삭제

      저도 방금 matlab으로 확인해 봤는데, 제 경우에는 결과가 같게 나옵니다 (열벡터 단위로 비교를 해야 하며 벡터의 순서 및 부호는 서로 다를 수 있음). matlab 버전의 차이일지는 모르겠지만 기본적으로는 같게 나오는게 맞는 것 같습니다.

    • 흐흐흐켱 2015.04.27 09:58 신고 수정/삭제

      아하.. 구조는 다르지만 값이 같을 수도 있는 거군요.. 열벡터 단위로 한번 확인해보겠습니다. 정말 감사합니다 ㅠㅠ

  • 김윤섭 2015.08.06 20:23 신고 ADDR 수정/삭제 답글

    다크님 질문있습니다. icp 알고리즘을 공부하는도중 오차함수를 최소화하는 부분에서 좀 궁금한게 있습니다. 덕분에 이론적인 배경을 열심히 공부하고 갑니다.
    m과 d는 모델과 데이터 행렬이구요. 현재 제가 알고있습니다. R은 회전행렬인데 제가 구할려고하는것이 최적의 R을 구하려고합니다

    ∑m*R*d 를 최대로 만들어주기 위해서 trace(RH)를 해줬습니다.
    H = ∑m*d 이구요 trace(RH)를 최대로 해주는 최적의R을 찾기위해서 논문에서는
    H를 특이값 분해(SVD) 취하여 H= U∑V^t 해주었고 R = VU^t 로 설정해 주었습니다
    그러면 trace(RH) = V∑V^t 가 되었습니다. trace(RH) = trace(∑) 인데요

    제가 궁금한것은 왜 저 R이라는 것이 trace 를 가장 크게 해주는건지 궁금합니다!
    또한 행렬을 특이값분해하면 UV는 방향을 나타내고 ∑(특이값)은 행렬의 크기를 나타내주는것이 맞나요?

    석사생활하면서 정말 많이 블로그를 통해 배워갑니다 갑사합니다

    • BlogIcon 다크pgmr 2015.08.06 21:47 신고 수정/삭제

      블로그 내용이 도움이 되었다니 다행입니다. 하지만 질문하신 내용은 저도 잘 모르는 내용입니다.

    • 김윤섭 2015.08.07 10:02 신고 수정/삭제

      읽어 주셔서 감사드립니다^^ 앞으로 좋은내용 많이 부탁드릴께요 화이팅!!

  • jade 2015.10.23 14:04 신고 ADDR 수정/삭제 답글

    좋은 글 잘 보았습니다. 참고로 full SVD 예제 결과 추정식이
    추정된 포물선 방정식: y = 0.21*x2 - 802.59*x + 754923
    이라고 쓰여 있는데 정확하게 쓰면
    0.21369*x2-802.59*x+754923
    로서 a값에 민감하군요.

    • BlogIcon 다크pgmr 2015.10.24 18:42 신고 수정/삭제

      네.. 감사합니다 ^^

    • 초짜 2017.04.06 05:09 신고 수정/삭제

      초짜가 여쭙니다. full SVD 경우에 사용된 (full SVD 근사) 2020년도 추정된 plot 코드 올려주실수 있으신가요?

    • BlogIcon 다크pgmr 2017.04.06 11:13 신고 수정/삭제

      /초짜 그림 13밑의 matlab 코드에 이미 있지 않나요?

  • astriker 2015.12.04 11:02 신고 ADDR 수정/삭제 답글

    좋은 글 잘 보았습니다. 정말 많은 도움이 됐습니다.
    혹시 python으로 구현을 하시고자 하는 분들을 위해 소스 첨부합니다.
    참고 하시기 바랍니다.


    from scipy import linalg
    import numpy as np
    #svd wrapper function
    def svd_a_inv(a , b, full_matrices=True):
    # from scipy import linalg
    # import numpy as np
    U, s, Vh = linalg.svd(a, full_matrices)
    # print U.shape, s.shape, Vh.shape
    S = linalg.diagsvd(s, a.shape[1], a.shape[1])
    if full_matrices == True:
    S_inv = linalg.diagsvd(np.linalg.inv(S).diagonal(), a.shape[1], a.shape[0])
    else:
    S_inv = np.linalg.inv(S)

    ah = np.dot(Vh.transpose(), np.dot(S_inv, U.transpose()))
    s = np.dot(ah, b)
    return ah, s

    #SVD population estimation
    a = np.array([
    [3724900, 1930, 1]
    , [3763600, 1940, 1]
    , [3798601, 1949, 1]
    , [3841600, 1960, 1]
    , [3880900, 1970, 1]
    , [3920400, 1980, 1]
    , [3960100, 1990, 1]
    , [4000000, 2000, 1]
    , [4040100, 2010, 1]
    ])
    b = np.array([2044, 2355, 2017, 2499, 3144, 3741, 4339, 4599, 4799])

    #use svd
    ah, s = svd_a_inv(a, b, full_matrices=False)
    f = lambda x: s[0] * x**2 + s[1] * x + s[2]
    print f(2020)

  • 2016.01.04 18:44 ADDR 수정/삭제 답글

    비밀댓글입니다

    • BlogIcon 다크pgmr 2016.01.05 15:53 신고 수정/삭제

      블로그에 있는 대부분의 글들은 출판된 논문은 아니지만 그동안의 나름의 지식과 해석, 경험, 실험과 정리가 들어간 고유의 저작물들입니다. 기존의 내용을 단순히 옮긴 것이 아니기 때문에 따로 정해진 출처나 원문이 없습니다. 다만 정리과정에서 위키피디아를 종종 참조하는 편이며 필요하다면 그때 그때 관련 서적들, 논문들을 읽어보고 또 직접 실험을 해 보면서 글을 작성하고 있습니다. 만일 인용을 하신다면 블로그 내용을 참조하시는게 맞습니다. 단순히 SVD에 대한 기본적인 수식 부분만을 인용하신다면 SVD는 선형대수학에 기본적으로 포함되는 내용이기 때문에 선형대수학 관련 서적들을 인용하시면 될 것 같습니다.

  • 김도현 2016.01.19 23:33 신고 ADDR 수정/삭제 답글

    안녕하세요.
    다크님 글 보고 많은 도움을 받고 있습니다.
    먼저 자세한 내용 포스팅 해주신거에 감사하다는 말씀 드립니다.

    제가 요즘 SVD를 이용한 영상압축을 진행하고 있는데요..궁금한점이 있어서 리플 올립니다.
    원본 영상은 IR카메라로 촬영되고 데이터는 raw 로 나옵니다. (320*240 pixel)
    c코드로 원본 영상을 U,S,V로 분할한 후 fully svd 했을 때(데이터들은 double형태로 계산합니다) 원본 데이터값이 그대로 나오는것 까지 확인했습니다.


    궁금한점은 압축률입니다.
    Singular value 수를 1/3정도만 사용해서(Truncated SVD) A`구한 후에 A` 데이터를 매틀랩에서 imshow로 뽑아봤습니다. 많이는 아니지만 원본 데이터보다 조금 구리구리해진 느낌이 들긴 했는데요, 두장 모두 bmp로 저장해서 보면 용량이 동일합니다. 아무래도 둘다 320*240 *8byte(double) 이라 그런것이라 생각하고 있는데요... 실질적으로 용량 압축은 어떻게 되는건가요??

    • BlogIcon 다크pgmr 2016.01.20 09:07 신고 수정/삭제

      안녕하세요. 이미지를 저장하는 것이 아니라 singular vector, singular value들을 저장해서 압축을 합니다. 윗 글 본문의 "3. Reduced SVD와 행렬근사, 데이터 압축"에서 마지막 설명 부분을 보시면 좋을 것 같습니다.

    • 김도현 2016.01.20 11:43 신고 수정/삭제

      답변 감사합니다. 많이 배우고 갑니다.

  • 혀니 2016.02.29 21:33 신고 ADDR 수정/삭제 답글

    다크님 덕분에
    SVD에 대한 개념이 명쾌하게 잡힌거 같아서
    감사하다는 말씀을 드리고 싶습니다.

    하나의 질문을 드리고 싶은것은
    "
    이렇게 truncated SVD로 근사한 행렬 A'은 matrix norm ∥A-A'∥을 최소화시키는 rank t 행렬로서 데이터압축, 노이즈제거 등에 활용될 수 있다. "

    라고 말씀 해주셨는데, norm ∥A-A'∥을 최소화는 t가 커질 수록 norm ∥A-A'∥최소화 되는 것이고, t 값의 선택은 사용자가 필요한 상황에 맞게 선택하는 것 아닌가용?

  • CVer 2016.03.29 20:50 신고 ADDR 수정/삭제 답글

    trucated SVD 그림 좀 사용하겠습니다. ^^

  • 2016.05.26 07:15 ADDR 수정/삭제 답글

    비밀댓글입니다

  • 오렌지 2016.08.16 22:23 신고 ADDR 수정/삭제 답글

    SVD, PCA 다 위키를 찾아봐도 잘 이해가 안 되서 전전긍긍했는데 많은 도움이 됐습니다! 감사합니다. :)

  • 질문이 2016.08.17 15:11 신고 ADDR 수정/삭제 답글

    이미지에 SVD 적용할 때 어떻게 하셨나요? 저는 250x250 이미지를 벡터로 만들어 SVD를 적용하려고 하는데 행렬 크기가 너무 큽니다. 벡터는 (62500, 1) 크기고 AA'는 (62500, 62500)의 크기가 되어서 메모리를 엄청나게 사용하게 되더라구요.

    • BlogIcon 다크pgmr 2016.08.17 20:58 신고 수정/삭제

      이미지를 벡터로 만들 필요가 없습니다.. 이미지 자체를 A로 잡으면 됩니다. 즉, A는 250x250 행렬로 잡고 SVD를 적용하면 됩니다.

    • 질문이 2016.08.18 12:21 신고 수정/삭제

      감사합니다! SVD를 사용해서 PCA 구하려 했는데 이 때는 어쩔 수 없이 1차원 벡터로 변환을 해야하는 것 같네요 ㅠㅠ 이미지와 PCA는 궁합이 안맞나 봅니다.

  • 궁금이 2016.09.20 20:44 신고 ADDR 수정/삭제 답글

    정말 잘 봤습니다 감사합니다 그런데 질문이 있어서 댓글을 남기게 되었습니다
    제가 하는 분야에서 응용을 하려고하는데 U와 시그마 그리고 VT의 의미를 정하는게 너무어렵습니다 ㅠㅠ 예시를 혹시 하나 들어봐주실수있을까요 제가 하는 내용은 m x 2 행렬에서 SVD를 이용해 U1과 U2의 그래프를 통해서 전체를 통제할 수 있는 위치를 찾아 내는 내용입니다 ㅠ
    위에서 설명하실때는 시그마에 중점을 두고 얘기를 하신거 같은데 제가 보는 내용에서는 U1과 U2를 구하는 내용에 중점을 두더라구요...

    • BlogIcon 다크pgmr 2016.09.21 11:52 신고 수정/삭제

      글쎄요.. 그 문제가 어떤 걸지는 저도 잘 모르겠습니다만 SVD의 가장 큰 응용이라면 선형시스템의 최적해를 구하는 것입니다.즉, A = UΣVT 라면 AX = 0인 시스템의 해(또는 ||AX||를 최소화시키는)는 V의 가장 오른쪽 열벡터가 됩니다. 그리고 A의 특이값, 특이벡터들에 대해 Avi = σi*ui가 항상 성립합니다. 이러한 성질들이 푸시고자 하는 문제에 적용이 될지는 모르겠네요.. http://darkpgmr.tistory.com/108 글도 참고해 보시면 좋을 것 같습니다.

  • 2016.12.05 19:58 ADDR 수정/삭제 답글

    비밀댓글입니다

  • Kimdaniel 2017.02.08 17:36 신고 ADDR 수정/삭제 답글

    2017년 1월 현재 약 51,704,332명 이네요!! ㅋㅋ

  • 물과나무 2017.03.14 18:41 신고 ADDR 수정/삭제 답글

    안녕하세요,좋은 글 감사드립니다! 작은 궁금증이 있어서 문의드립니다.
    "이렇게 truncated SVD로 근사한 행렬 A'은 matrix norm ∥A-A'∥을 최소화시키는 rank t 행렬로서 데이터압축, 노이즈제거 등에 활용될 수 있다."
    이 말에 대해서인데요, 만약 100*50을 데이터 압축을 위해 truncated SVD를 진행한다면, 다른 모든 같은 조건의 분해보다 더 A에 근사한 분해인가요? 어느 논문에서는 SVD를 통해 목표 matrix A의 근사인 A'를 찾더라구요, 단순히 생각하면 가장 '주요한(singular value가 가장 큰)' singular vector들을 우선 배치하여 분해하는 것이니 오차가 적어질 것 같기는합니다만 정말'최적'의 분해가 맞나요?

    • BlogIcon 다크pgmr 2017.03.15 12:24 신고 수정/삭제

      최적의 의미는 달라질 수 있겠지만 matrix norm을 최소화하는 행렬임은 맞습니다. 수학적으로 증명할 수 있는 내용으로 알고 있습니다..

  • image 2017.04.19 00:48 신고 ADDR 수정/삭제 답글

    안녕하세요. 영상처리를 공부하다가 SVD라는 개념이 나와 공부하고 있는 중 좋은 글을 보면서 많이 배웠습니다. 먼저 감사드립니다.
    글을 읽으면서 matrix의 svd를 구하는 것을 알겠고, matrix를 통해 rotation되고 stretching, 또다시 rotation된다는 의미는 알겠는데. 이게 영상처리에 관련해서는 왜 사용하는지가 아직도 의문입니다..
    혹시, 간단하게 설명해주실 수 있으신가요?
    감사합니다.

    • BlogIcon 다크pgmr 2017.04.19 09:12 신고 수정/삭제

      직접적인 관계가 있다기보다는 기본이 되는 내용으로 볼 수 있습니다. 모든 분야가 다 그렇지만 영상처리도 조금만 깊게 들어가도 수학적 내용이 주를 이루고 SVD는 수학적 접근에 있어서 가장 중요한 개념 중 하나입니다. SVD는 선형시스템의 풀이, 모델링 및 파라미터 추정, 최적화에 사용되는 가장 중요한 수학적 도구입니다. 약간 극단적인 비유를 들면, 우리가 덧셈 뺄셈을 배우지만 덧셈 뺄셈이 어떻게 영상처리에 사용되는지 묻는 것과 유사합니다.

  • 옵티머스 2017.08.12 11:53 신고 ADDR 수정/삭제 답글

    안녕하세요. 좋은 글 감사드립니다. 저는 CAD 분야에서 free-form deformation에 필요한 pseudoinverse matrix 계산시에 SVD를 활용하고 있습니다. 주로 matlab의 pinv 함수나 fortran IMSL의 DLSGRR 함수를 이용하고 있는데요, 간혹 convergence 가 되지 않는다는 에러메세지가 나오면서 SVD가 수행이 되지 않는 경우가 있습니다. 혹시 이러한 경우에 SVD를 수행할 다른 방안이 있는지 궁금합니다.

    • BlogIcon 다크pgmr 2017.08.12 12:31 신고 수정/삭제

      저는 아직 경험하지 못했지만 svd의 convergence 이슈는 꽤 알려져 있는 것 같습니다. 제가 잠깐 검색해본 바로는 여러 가지 해결책들이 논의되고 있는데요, linux 대신에 windows에서 돌리면 잘 돌아간다는 말도 있고, 데이터 자체에 문제가 있는 경우(NaN 등)의 확인, matlab에서는 svd 대신에 svdecon을 사용하면 해결된다는 말, linux에서는 svd 루틴의 일부를 XXX와 같이 수정하면 된다는 말도 있고, 또 원 행렬 대신에 ATA와 같이 제곱한 행렬에 대해 svd를 적용하는 방법 등 다양한 방법들이 나옵니다. 어떤 것이 해결이 될지 인터넷에서 해법을 찾아보시면 좋을 것 같습니다.

  • 너무좋아요 2017.08.25 15:37 신고 ADDR 수정/삭제 답글

    머신 러닝 공부라고 있어서 선형대수 독학중인데
    다크님 블로그 매일 들어오고 있습니다 진짜
    내용이 너무 좋네요!! 감사합니다

  • 옵티머스 2017.08.31 22:27 신고 ADDR 수정/삭제 답글

    안녕하세요, 항상 좋은 글 감사드립니다. 말씀해주신대로 인터넷에서 해결책을 찾아보고자 했지만, 제 검색 능력 부족 때문인지, 아직 헤매고 있습니다. 혹시 답변해주신 내용들을 어떤 검색어 혹은 경로로 찾으셨는지 알려주시면 많은 도움이 될 것 같습니다. 다시한번 감사드립니다.

    • BlogIcon 다크pgmr 2017.08.31 22:55 신고 수정/삭제

      구글에서 "svd fails to converge", "svd did not converge" 등으로 검색해 보시기 바랍니다. 거기에 나오는 글들을 하나씩 읽다가 보면 이런 저런 얘기들이 나왔던 것 같습니다.

  • 캘리브 2017.10.09 13:33 신고 ADDR 수정/삭제 답글

    글 잘보았습니다
    궁금한점이 생겼습니다.
    예를들면 x = PX (image plane2*100) = (projection matrix 3*4) (world 3*100) 이렇게
    100개의 대응되는 좌표가 주어졌을떄 P matrix를 구할 수 있을꺼 같아 SVD를 이용하면 될거같은데,
    어떤식으로 접근을 해야 저 projection matrix를 구할수 있을까요? 감사합니다

    • BlogIcon 다크pgmr 2017.10.09 15:33 신고 수정/삭제

      그렇게는 풀수 없을 것 같습니다. P가 3x4라면 x도 3x1이 되어야 하고 즉, x가 호모지니어스(homogeneous) 좌표로 표현된다는 의미입니다. 그런데, 호모지니어스 좌표에서는 스케일(scale) 텀이 무시되기 때문에 방정식 풀듯이 SVD로 풀 수는 없을 것 같습니다.