예전에 카메라 캘리브레이션에 관한 글([영상처리] - 카메라 캘리브레이션 (Camera Calibration))을 쓰면서 카메라의 초점거리(focal length)를 렌즈초점에서 이미지 센서까지의 거리라고 설명했는데 최근 이게 아님을 깨닫게 되었습니다.

새로 깨닫게 된 것은 카메라 초점거리(focal length)는 렌즈에서 이미지 센서까지의 거리라는 것입니다.

왜 그런지 간단히 설명해 보겠습니다.

먼저, 컴퓨터 비전에서 말하는 카메라의 기본모델은 아래 그림과 같은 핀홀(pinhole) 카메라 모델입니다.

<그림 1> pinhole 카메라 모델 (그림출처: 위키피디아)

핀홀 카메라 모델은 말 그대로 외부의 상이 하나의 바늘구멍을 직선으로 통과하여 반대편 벽(이미지 센서)에 맺힌다는 모델입니다. 그리고 여기서 카메라 초점거리(focal length)는 바늘구멍에서 뒷 벽면까지의 거리로 정의됩니다.

이제 핀홀 카메라 모델을 렌즈-이미지센서로 대응시켜 생각해 보겠습니다.

볼록렌즈의 기본 성질은 렌즈에 수평으로 들어온 빛은 모두 렌즈 초점(focus)을 통과한다는 것입니다. 또한 렌즈의 중심(center)을 통과하는 빛은 굴절없이 그대로 직진하게 되며 렌즈 중심에서 멀어질수록 굴절이 심해진다는 점입니다. 이러한 내용을 그림으로 나타내 보면 아래와 같습니다.

<그림 2> 렌즈-이미지센서 투영

그림을 잘 보면(특히 나무의 위 끝부분) 렌즈에 수평으로 들어온 빛은 렌즈의 초점을 통과하여 이미지 센서에 투영되고 렌즈의 중심을 지나는 빛은 그대로 투과하여 이미지 센서에 맺힙니다. 그런데 빛은 모든 방향으로 퍼져 나가기 때문이 이 두 방향뿐 아니라 그림의 빨간색 선들처럼 다양한 방향으로 렌즈를 투과하여 상이 맺히게 됩니다. 그런데, 중요한 점은 이들 빛들이 모두 한점 (렌즈 수평한 빛과 렌즈 중심 통과한 빛이 만나는 점)으로 모이게 되며 이 만나는 점에 이미지 센서가 위치하면 가장 선명한 상을 얻을 수 있다는 점입니다 (제가 물리쪽에는 자신이 없어서 확신은 못하지만 대략 이럴 것이라 추정하고 있습니다). 위 그림에서 이미지 센서를 좀더 앞으로 이동시키거나 뒤로 빼면 빛이 흩어지기 때문에 블러링(blurring)이 생김을 쉽게 상상할 수 있습니다.

우리가 보통 선명한 이미지를 얻기 위해 카메라의 초점거리를 조절하는 것이 이 원리라고 생각하면 됩니다.

원래 문제로 돌아가서,

<그림 1>의 핀홀 카메라 모델과 <그림 2>를 비교해 보면 핀홀 모델에서는 빛이 바늘구멍을 직선으로 투과하여 반대편에 상이 맺힙니다. 그런데, <그림 2>를 보면 빛이 렌즈초점을 직선으로 지나는 것이 아니라 렌즈중심을 직선으로 투과하여 이미지 센서에 맺히는 것을 알 수 있습니다. 따라서, 렌즈중심이 핀홀에 대응되기 때문에 카메라의 초점거리는 렌즈중심에서 이미지센서까지의 거리로 정의하는 것이 맞겠습니다.

by 다크 프로그래머

활용도 측면에서 선형대수학의 꽃이라 할 수 있는 특이값 분해(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는 AA^T를 고유값분해(eigendecomposition)해서 얻어진 직교행렬(orthogonal matrix)로 U의 열벡터들을 A의 left singular vector라 부른다. 또한 V는 A^TA를 고유값분해해서 얻어진 직교행렬로서 V 의 열벡터들을 A의 right singular vector라 부른다.  left, right가 상당히 햇갈리는데 그냥 Σ의 왼쪽에 있는 U가 left singular 벡터, 오른쪽에 있는 V가 right singular 벡터들이라고 생각하면 된다. 마지막으로, Σ는 AA^T, A^TA를 고유값분해해서 나오는 고유값(eigenvalue)들의 square root를 대각원소로 하는 m x n 직사각 대각행렬로 그 대각원소들을 A의 특이값(singular value)이라 부른다. U, V가 직교행렬(orthogonal matrix)이라 함은 UU^T = VV^T = E, U^-1=U^T, V^-1=V^T임도 기억하자.

U의 열벡터(ui): left singular vectors of A (AA^T의 eigenvector)

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

Σ의 대각원소(σi): singular values of A (A^TA, AA^T의 eigenvalue들의 square root)

 --- (2)

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

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

i) A^TA의 고유값을 λ, 고유벡터를 v (v≠0)라 했을 때, A^TAv = λv 이다. 양변에 v^T를 곱해보면 v^TA^TAv = λv^Tv 에서 (Av)^TAv = λv^Tv 즉, ∥Av∥² = λ∥v∥² 이므로 λ≥0 이다.

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

이와같이, AA^T와 A^TA의 공통의 고유값 σ₁²≥σ₂²≥ ... ≥σ_s²≥0 (단, s = min(m, n))들을 구한 후 이들의 square root를 취한 σ₁≥σ₂≥ ... ≥σ_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는 AA^T, A^TA의 고유값분해(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에 대해 항상 z^TAz>0을 만족할 때 이 행렬을 positive definite 행렬이라고 부르며 negative definite 등도 유사하게 정의된다. 그런데 이러한 행렬들의 중요한 성질은 고유값(eigenvalue)도 동일한 부호를 갖는다는 점이다. 즉, 어떤 대칭행렬 A가 positive definite하면 이 행렬의 모든 eigenvalue은 항상 양수이다. 만일 A가 positive semidefinite하면 eigenvalue들도 ≥0이고, negative definite면 모든 eigenvalue들이 음수이다. 앞서, SVD를 구하는 과정에서 나왔던 AA^T, A^TA는 positive semidefinite 행렬들로서 항상 0 이상의 eigenvalue들을 갖는다.

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

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

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

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

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

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

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

☞ 이 주제와 관련하여 조금 더 상상의 나래를 펴 보면, m x n 행렬 A는 n차원 공간에서 m 차원 공간으로의 선형변환이다. n차원 공간에 있는 원, 구 등과 같이 원형으로 된 도형을 A에 의해 변환시키면 먼저 V^T에 의해서는 회전만 일어나므로 도형의 형태는 변하지 않는다. 그런데 Σ에 의해서는 특이값의 크기에 따라서 원이 타원이 되거나 구가 럭비공이 되는 것과 같은 식의 형태변환이 일어난다 (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ΣV^T라면 A의 pseudo inverse는 VΣ⁺U^T로 계산되고 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만명이다.

(단위: 만명)

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

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

연도를 x = 1930, 1940, ..., 2010, 해당연도의 인구수를 y, 모델을 y = ax² + 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*x² - 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*x² - 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*x²).

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

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

그런데, 위 <그림 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 다크 프로그래머 

선형대수학에서 고유값(eigenvalue)과 고유벡터(eigenvector)가 중요하다고 하는데 왜 그런 것인지 개인적으로도 참 궁금합니다. 고유값, 고유벡터에 대한 수학적 정의 말고 이런 것들이 왜 나왔고 그 본질이 무엇인지에 대한 직관이 있으면 좋을텐데요..

아직은 딱히 이것 때문이다라고 결론지을 수는 없지만 고유값, 고유벡터 그 자체의 활용보다는 SVD(특이값분해), Pseudo-Inverse, 선형연립방정식의 풀이, PCA(주성분분석) 등의 주요 응용이 eigenvalue, eigenvector를 그 밑바탕에 깔고 있기 때문은 아닌가 생각하고 있습니다.

이 글에서는 먼저 고유값, 고유벡터 자체에 대한 개념만 살펴보고 SVD, 선형연립방정식, PCA 등에 대해서는 별도 글로 자세하게 다룰 예정입니다.

1. 고유값, 고유벡터란?

고유값(eigenvalue), 고유벡터(eigenvector)에 대한 수학적 정의는 비교적 간단하다.

행렬 A를 선형변환으로 봤을 때, 선형변환 A에 의한 변환 결과가 자기 자신의 상수배가 되는 0이 아닌 벡터를 고유벡터(eigenvector)라 하고 이 상수배 값을 고유값(eigenvalue)라 한다.

즉, n x n 정방행렬(고유값, 고유벡터는 정방행렬에 대해서만 정의된다) A에 대해 Av = λv를 만족하는 0이 아닌 열벡터 v를 고유벡터, 상수 λ를 고유값이라 정의한다.

 ---(1)

--- (2)

좀더 정확한 용어로는 λ는 '행렬 A의 고유값', v는 '행렬 A의 λ에 대한 고유벡터'이다.

즉, 고유값과 고유벡터는 행렬에 따라 정의되는 값으로서 어떤 행렬은 이러한 고유값-고유벡터가 아에 존재하지 않을수도 있고 어떤 행렬은 하나만 존재하거나 또는 최대 n개까지 존재할 수 있다.

2. 기하학적 의미

기하학적으로 봤을 때, 행렬(선형변환) A의 고유벡터는 선형변환 A에 의해 방향은 보존되고 스케일(scale)만 변화되는 방향 벡터를 나타내고 고유값은 그 고유벡터의 변화되는 스케일 정도를 나타내는 값이다.

예를 들어 지구의 자전운동과 같이 3차원 회전변환을 생각했을 때, 이 회전변환에 의해 변하지 않는 고유벡터는 회전축 벡터이고 그 고유값은 1이 될 것이다.

3. 고유값분해를 이용한 대각화 - eigendecomposition

고유값, 고유벡터는 정방행렬의 대각화와 밀접한 관련이 있다 (eigendecomposition은 정방행렬에 대해서만 가능함)

먼저 대각행렬과의 행렬곱에 대해 살펴보면, 대각행렬을 뒤에 곱하면 행렬의 열벡터들이 대각원소의 크기만큼 상수배가 된다(앞에 곱하면 행벡터들이 상수배가 된다). 예를 들어, 3 x 3 행렬의 경우를 보면 다음과 같다.

 --- (3)

행렬 A의 고유값, 고유벡터들을 λi, vi, i = 1, 2, ..., n이라 하자.

 --- (4)

이제 식 (4)를 한꺼번에 표현하여 정리하면

 --- (5)

가 성립함을 알 수 있다.

즉, 행렬 A의 고유벡터들을 열벡터로 하는 행렬을 P, 고유값들을 대각원소로 하는 대각행렬을 Λ라 하면 다음 식이 성립한다.

--- (6)

즉,  --- (7)

이와같이 행렬 A는 자신의 고유벡터들을 열벡터로 하는 행렬과 고유값을 대각원소로 하는 행렬의 곱으로 대각화 분해가 가능한데 이러한 대각화 분해를 eigendecomposition이라고 한다.

한 예로, A = [1 1 0; 0 2 1; 0 0 3]인 경우 A는 다음과 같이 대각화가 가능하다.

 --- (8)

모든 정방행렬이 이런 방식의 eigendecomposition이 가능한 것은 아니지만 대각화 가능한 경우는 뒤에 적기로 하고 일단은 대각화를 하면 어떤게 좋은지 알아보자.

행렬 A의 eigendecomposition을 알면 행렬식 값 det(A), A의 거듭제곱, 역행렬, 대각합(trace), 행렬의 다항식 등을 매우 손쉽게 계산할 수 있다.

 --- (9)

 --- (10)

--- (11)

 --- (12)

--- (13)

4. 고유값분해(eigendecomposition) 가능조건 - 일차독립

앞서 말했지만 모든 정방행렬이 고유값분해가 가능한 것은 아니다. n x n 정방행렬 A가 고유값분해가 가능하려면 행렬 A가 n개의 일차독립인 고유벡터를 가져야 한다.

선형대수학에서 말하는 일차독립(linearly independent)이란 무엇일까?

어떤 벡터들의 집합 {v1, ..., vn}이 있을 때, 이들 벡터들 중 어느 한 벡터도 다른 벡터들의 일차결합으로 표현될 수 없으면 이 벡터들은 서로 일차독립이라고 정의한다.

벡터들의 일차결합이란 a1v1 + a2v2 + ... + anvn (ai는 상수)와 같이 상수를 곱하여 합친 형태를 말한다.

예를 들어 3차원 공간의 좌표축 단위벡터들인 v1 = (1,0,0), v2=(0,1,0), v3=(0,0,1)를 생각해 보면 v2, v3에 어떤 상수를 곱하여 더해도 v1이 나올수 없음은 쉽게 확인할 수 있다. 이와 같이 어떤 벡터도 다른 벡터들의 상수배 합으로 표현될 수 없으면 이 벡터들은 서로 일차독립(linearly independent)이라고 한다.

참고로 n차원 공간은 최대 n개의 일차독립인 벡터들을 가질 수 있으며 n개의 일차독립인 벡터들은 이 공간을 생성하는 기저(basis) 역할을 수행한다.

위 예에서, 3차원 공간에서 좌표축 단위벡터들의 집합 {v1, v2, v3}는 일차독립이지만 여기에 v4 = (-1, 3, 4)를 추가한 {v1, v2, v3, v4}는 일차독립이 아니다 (∵ v4 = -v1+3*v2+4*v3). 즉, 3차원 공간에서 가능한 일차독립인 벡터들의 개수는 최대 3개이다.

또한 v1, v2, v3를 자세히 보면 이 벡터들을 이용하여 3차원 공간의 모든 (x, y, z) 좌표를 생성할 수 있음을 알 수 있다. 어떤 일차독립인 벡터들의 집합 {v1,...,vn}의 일차결합을 통해 어떤 공간의 모든 좌표를 생성할 수 있으면 이 벡터들을 이 공간의 기저(basis)라고 정의한다.

다시 원래 문제로 돌아가서, n차 정방행렬이 고유값분해가 가능하려면 n개의 일차독립인 고유벡터가 존재해야 한다고 했는데 이게 무슨 말인지 아직은 마음에 확 와닿지는 않을 것이다. 그건 고유값, 고유벡터가 어떻게 계산되는지 그 과정에 대한 이해가 필요하기 때문이다.

5. 고유값, 고유벡터의 계산

고유값과 고유벡터를 정의하는 식인 식 (1)으로 다시 돌아가서 이를 v에 대해 정리해보면 다음과 같다.

 --- (14)

우리가 구하고자 하는 고유값, 고유벡터는 식 (14)를 풀어서 나오는 λ와 v이다 (단, v≠0). 그런데, 식 (14)를 잘 보면 (A-λE)의 역행렬이 존재한다면 v는 항상 v = (A-λE)^-10 = 0 만을 해로 갖게 된다. 그런데, 고유벡터는 정의에 의해 영벡터가 아닌 백터여야 하므로 A-λE의 역행렬이 존재하지 않는 경우에만 존재할 수 있다. 따라서, 고유벡터가 존재하기 위해서는 일단은 det(A-λE) = 0 이어야 한다.

 --- (15)

이 때, 식 (15)를 행렬 A의 특성방정식(characteristic equation)이라고 부르며 식 (15)를 λ에 대해 풀면 A의 고유값을 구할 수 있다. 고유벡터는 이렇게 구한 λ를 다시 식 (14)에 대입하여 계산한다.

[예]

다음과 같은 행렬 A에 대한 고유값, 고유벡터를 계산해 보자.

 --- (16)

이 때, 행렬 A를 식 (14)에 대입하여 특성다항식을 구해보면

 --- (17)

이므로 특성방정식은 (2-λ)(1-λ)² = 0 이 된다.

 --- (18)

이제 특성방정식의 해는 λ = 1, 2인데 잘 보면 λ=2는 단일근임에 비해 λ=1은 이중근임을 알 수 있다. λ에 대응하는 고유벡터의 개수는 λ가 몇중근이냐와 밀접한 관계가 있는데 단일근에 대해서는 1개, 이중근에 대해서는 최대 2개, 삼중근에 대해서는 최대 3개, ... 의 고유벡터가 존재한다.

먼저 λ = 2를 다시 식 (14)에 대입하여 고유벡터를 구해보면,

 --- (19)

따라서, λ = 2에 대응하는 고유벡터는 v = [1, 1, 0]^T 로 잡을 수 있다.

마찬가지로, λ = 1에 대해서도 고유벡터를 구해보면

--- (20)

x좌표가 z좌표의 2배인 벡터들은 무수히 많은데 이들은 [2, 0, 1], [0, 1, 0]의 일차결합으로 표현할 수 있으므로 λ = 1에 대응하는 고유벡터를 [2, 0, 1]과 [0, 1, 0] 으로 잡을 수 있다.

☞ x좌표가 z좌표의 2배인 임의의 벡터는 [2t, s, t]로 표현할 수 있다 (단, t, s는 임의의 실수). 그런데, 이는 [2t, s, t] = t*[2, 0, 1] + s*[0, 1, 0]와 같이 [2, 0, 1]과 [0, 1, 0]의 일차결합으로 표현될 수 있다.

아마도 이 시점에서 고유값은 어떻게 구하는지 알겠는데 고유벡터는 뭔가 좀 애매하다고 느끼는 분들이 많을 것으로 예상한다. 그 이유는 어떤 행렬에 대해 고유값은 유일하게 결정되지만 고유벡터는 유일하지 않기 때문이다. 이는 다음 내용을 보면 알 수 있다.

식(1)의 양변에 상수 c를 곱해보면,

 --- (21)

가 되므로 v가 λ에 대한 고유벡터이면 0이 아닌 임의의 상수 c에 대해 cv도 또한 λ에 대한 고유벡터임을 알 수 있다.

또한, v1, v2가 모두 고유값 λ에 대응하는 고유벡터라고 하면 임의의 상수 c1, c2에 대해

 --- (22)

이므로 c1v1 + c2v2 또한 λ에 대한 고유벡터가 됨을 알 수 있다.

따라서 고유벡터는 식 (19), 식 (20) 등과 같은 제약조건을 만족하는 벡터들 중에서 어느 벡터를 사용해도 무방하나 보통은 벡터의 크기를 1로 정규화한(normalized) 단위벡터를 고유벡터로 잡는 것이 일반적이다. 단, 식 (20)의 경우에는 자유도(degree of freedom)가 2이기 때문에 일차독립인 2개의 고유벡터를 잡아야만 가능한 모든 고유벡터들을 대표할 수 있다.

이제 이렇게 구한 고유값, 고유벡터에 대해 아래와 같은 행렬 대각화가 정말로 성립함을 matlab 또는 손계산을 이용하면 쉽게 확인할 수 있다 (또한 고유벡터들의 스케일을 바꾸거나 순서를 바꾸어도 대각화가 성립함도 확인할 수 있다).

 --- (23)

6. 대칭행렬(symmetric matrix)과 고유값분해

정방행렬들 중에서 대각원소를 중심으로 원소값들이 대칭되는 행렬 즉, A^T = A (모든 i, j에 대해 aij = aji)인 행렬을 대칭행렬(symmetric matrix)이라 부른다.

그런데, 대칭행렬은 고유값 분해와 관련하여 매우 좋은 성질 2가지를 가지고 있다. 실원소(real-valued) 대칭행렬은 항상 고유값 대각화가 가능하며 더구나 직교행렬(orthogonal matrix)로 대각화가 가능하다는 매우 좋은 성질을 가지고 있다.

 --- (24)

단, 

즉, 모든 대칭행렬은 위 식 (24)와 같이 직교행렬을 이용한 고유값 대각화가 가능하다 (증명1, 증명2).

☞ 위 성질은 원소값이 실수(real number)인 경우에 항상 성립하는 성질이며 만일 원소값이 복소수(complex number)인 경우에는 유니터리(unitary) 행렬로 항상 대각화 가능하다. 그런데 사실 직교행렬을 복소수 공간에서 정의한 것이 유니터리 행렬이기 때문에 대칭행렬은 항상 대각화 가능하다고 생각하면 된다.

이렇게 따로 대칭행렬의 대각화에 대해 단락을 구분하여 적는 이유는 선형대수학에서 워낙 중요한 성질이기 때문이다. 대칭행렬(symmetric matrix)의 이러한 성질은 특이값분해(SVD), 주성분분석(PCA) 등에서 가장 기본이 되는 성질로 활용된다.

모든 정방행렬이 고유값 분해가 가능한 것은 아니지만 대칭행렬은 항상 고유값 분해가 가능하며 더구나 직교행렬로 대각화가 가능함을 기억하자.

※ 직교(orthogonal)와 정규직교(orthonormal), 그리고 직교행렬(orthogonal matrix)

orthogonal과 orthonormal이 서로 용어가 혼동되기 쉬운데 두 용어의 차이를 명확히 할 필요가 있다. 

먼저, 벡터에 대해 얘기를 해 보면 두 벡터 v1, v2가 서로 수직이면(즉, v1·v2 = 0) 두 벡터 v1, v2는 서로 orthogonal 하다고 한다. 그리고 v' = v/∥v∥와 같이 어떤 벡터를 크기가 1인 단위벡터로 만드는 것을 정규화(normalization)라고 한다. orthonormal이라는 말은 orthogonal과 normal이 합쳐진 말로서 두 벡터 v1, v2가 모두 단위벡터(unit vector)이면서 서로 수직이면 두 벡터 v1, v2는 orthonormal(정규직교)하다고 한다.

• orthogonal: v1·v2 = 0

• orthonormal: v1·v2 = 0  &  ∥v1∥ = 1, ∥v2∥ = 1

즉, orthogonal, orthonormal은 벡터들 사이의 관계를 나타내는 말인데, 이게 행렬로 넘어가면 조금 의미가 달라진다.

먼저, 행렬에서는 직교행렬(orthogonal matrix)이라는 말은 있어도 정규직교행렬(orthonomal matrix)이라는 말은 없다. 흔히 orthonomal matrix라는 표현을 쓰는데 이는 잘못된 것이며 orthogonal matrix (직교행렬)가 올바른 용어이다.

직교행렬(orthogonal matrix)의 수학적 정의는 자신의 전치행렬(transpose)를 역행렬로 갖는 정방행렬이다.

--- (25)

이와 같이 직교행렬(orthogonal matrix)은 transpose를 시키면(행렬의 열과 행 원소들을 서로 바꾸면) 자신의 역행렬이 되기 때문에 다양한 선형대수학 계산에서 매우 편리한 성질을 가진 행렬이다.

그런데, 직교행렬의 열벡터들은 서로 orthonomal(정규직교)한 성질을 가지고 있다. 즉, 직교 행렬를 구성하는 열벡터들을 v1, v2, ..., vn이라 했을 때 이들은 모두 단위벡터(unit vector)이면서 또한 서로 서로 수직인 성질을 갖는다. 이는 식 (25)로부터 쉽게 도출될 수 있다.

 --- (26)

이러한 성질은 열벡터가 아닌 행벡터들에 대해서도 동일하게 성립한다 (즉, 행벡터들도 서로 orthonormal 하다).

즉, 직교행렬(orthogonal matrix)은 그 행렬을 구성하는 열벡터(행벡터)들이 서로 수직(orthogonal)이면서 크기가 1인 (normal한) 행렬로도 정의될 수 있다.

이상의 내용을 정리하면 다음과 같다.

• 벡터들이 orthogonal하다: 서로 수직이다
• 벡터들이 orthonormal하다: 서로 수직이면서 크기가 1인 단위벡터이다
• 행렬이 orthogonal하다: AA^T=E 이다 (행렬을 구성하는 열벡터, 또는 행벡터들이 orthonomal하다)

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

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

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

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

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

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

by 다크 프로그래머