[혁펜하임: 보이는 선대] 5강: 고윳값

5-1강: Eigen Value & Eigen Vector

 

5. 1. 1. 개념

 

행렬 A에 벡터 v를 곱하면 방향은 그대로이고 크기만 람다만큼 변한다고 하자. 이를 만족하는 람다가 eigen value, 만족하는 벡터 v가 eigen vector이다. 여기서 행렬 A는 항상 정사각행렬이다. 만약 행렬 A가 m x n이라고 하면 벡터 v는 n x 1일 것이고, 이 곱셈의 해는 m x 1이 된다. 이때 스칼라인 람다와 벡터 v가 곱해지면 n x 1일 것이고, 이는 m x 1과 같아야 하므로 m = n이다. 따라서 행렬 A는 항상 정사각행렬이다. 

 

$$A \underline{v} = \lambda \underline{v}$$

 

5. 1. 2. 선형 변환의 관점

 

위 수식을 쉽게 벡터 v를 행렬 A에 통과시킨다고 생각해 보자. 즉, 행렬 A를 함수라고 생각하자는 것이다. 이렇게 함수를 통과하는 것을 선형변환이라고 한다. 선형은 scaling과 additivity를 만족해야 한다. 먼저 행렬 A와 벡터 v의 곱을 아래 수식처럼 함수라고 생각해 보자. 

 

$$A(\underline{v}) = A\underline{v}$$

 

아래의 수식과 같이 입력이 상수배 되면, 출력도 상수배 되는 것을 scaling이라고 한다. 

 

$$A(\alpha \underline{v}) = \alpha(A \underline{v})$$

 

또, 아래의 수식과 같이 v_1과 v_2의 출력의 합이, v_1 + v_2의 출력과 같은 경우를 additivity라고 한다. 

 

$$A(\underline{v_1}) = A\underline{v_1}$$

$$A(\underline{v_2}) = A\underline{v_2}$$

$$A(\underline{v_1} + \underline{v_2}) = A\underline{v_1} + A\underline{v_2}$$

 

그리고 v라는 벡터가 Av라는 또 다른 벡터로 변하는 것이기 때문에, 선형변환이라고 해석할 수 있다. 또 선형 변환의 관점에서 invertible한지를 알아볼 수 있다. 두 개의 서로 다른 입력이 들어갔을 때, 각각 다른 출력이 나와야 invertible하다. 다른 입력에 대해 같은 출력이 되도록 선형 변환을 했다면 이는 invertible하지 않은 행렬이 된다. 왜냐하면 다른 입력이 들어가서 같은 출력이 나오면, 여러 입력의 가능성을 가지고 있어서 다시 입력으로 되돌아갈 수가 없기 때문이다. 

 

5. 1. 3. 구하는 방법

 

λ와 v를 구하는 법을 배워보자. 일단 아래의 수식처럼 λv를 이항 한다. λ와 항등행렬 I를 곱하여 행렬 A와 뺄셈을 계산할 수 있도록 만들어주고, 결합법칙을 적용한다. 

 

$$A\underline{v} - \lambda \underline{v} = (A - \lambda I) = 0$$

 

위 수식에서 A - λI가 0이거나 벡터 v가 0이 되면 만족하는 수식이 된다. 여기서 벡터 v가 0이 되는 것은 trivial solution이기 때문에 될 수 없다. 벡터 v가 0이 될 수 없다면 A - λI의 determinant가 0이 되어야 한다. 왜냐하면 A - λI가 역행렬을 가질 경우, 역행렬을 양변에 곱하면 벡터 v가 무조건 0이 되는 수식이 되기 때문이다. 따라서 아래의 수식을 만족하는 λ를 찾아야 한다. 

 

$$det(A - \lambda I) = 0$$

 

λ를 구했다면 벡터 v를 구하는 방법은 쉽다. 행렬 A - λI와 벡터가 곱해서 0이 되어야 하므로, 행렬 A - λI의 null space에 존재하는 벡터가 벡터 v가 된다. 따라서 벡터 v는 무한하거나 아예 없는 경우가 된다. 해가 무한한 경우에는 벡터 v를 모두 정의할 수 없기 때문에, 보통 null space의 basis를 벡터 v로 정의한다. 

 

5-2강: Eigen Decomposition

 

5. 2. 1. 개념

 

A가 2 x 2 행렬이고, eigen value 2개, eigen vector 2개를 가지는 행렬이라고 하자. eigen value를 각각 λ_1, λ_2, 그리고 이에 따른 eigen vector를 v_1, v_2라고 하자. 그렇다면 아래의 수식으로 표현할 수 있을 것이다. 

 

$$A \underline{v_1} = \lambda_1 \underline{v_1}$$

$$A \underline{v_2} = \lambda_2 \underline{v_2}$$

 

위의 두 수식을 합치면 아래와 같이 나타낼 수 있다. 아래 수식에서 벡터 v_1, v_2를 합친 행렬을 V, 람다를 행렬로 만든 것을 Λ라고 정의한다. 

 

$$A\begin{bmatrix} \underline{v_1} & \underline{v_2} \end{bmatrix} = \begin{bmatrix} \lambda_1 \underline{v_1} & \lambda_2 \underline{v_2} \end{bmatrix} = \begin{bmatrix} \underline{v_1} & \underline{v_2} \end{bmatrix} \begin{bmatrix} \lambda_1 & 0 \\ 0 & \lambda_2 \end{bmatrix} = V \Lambda$$

 

행렬 V는 independent한 벡터 2개를 모은 것이기 때문에, full rank이고, 이는 invertible함을 의미한다. 따라서 행렬 V의 inverse를 양변에 곱하면 아래의 수식으로 나타낼 수 있다. 

 

$$A = V \Lambda V^{-1}$$

 

이처럼 행렬 A를 VΛV^-1로 분해하는 것을 eigen decomposition이라고 한다. 또 아래의 수식과 같이 변형하게 되면 행렬 A를 diagonal matrix인 Λ로 변형한 것이기 때문에, diagonalize라고 한다. 

 

$$V^{-1} A V = \Lambda$$

 

이는 행렬 A의 eigen vector가 있는 경우에만 가능하기 때문에, eigen vector로 full rank 행렬을 만들 수 있는 경우 행렬 A를 diagonalizable한 matrix라고 한다. 따라서 [행렬이 diagonalizable matrix이다]는 [행렬 A는 egien decomposition이 가능하다]와 동치인 것이다. 또, [n x n 행렬의 independent eigen vector가 n개 존재한다]와 같은 말인 것이다. 

 

5. 2. 2. 특징

 

첫 번째, A의 k 거듭제곱을 계산하기 쉬워진다. 왜냐하면 A의 k승은 아래의 수식과 같이 나타낼 수 있기 때문이다. Λ의 k 거듭제곱은, Λ가 대각행렬이기 때문에 계산하기 어렵지 않고, V와 V inverse는 이미 알고 있기 때문에 계산하기 쉽다. 

 

$$A^k = V \Lambda V^{-1}  V \Lambda V^{-1}  V \Lambda V^{-1} \dots =  V \Lambda^k V^{-1}$$

 

두 번째, A의 inverse를 계산하기 쉬워진다. Λ 행렬의 inverse는 각 대각 성분인 eigen value에 역수를 취하기만 하면 되기 때문이다. 따라서 A의 inverse는 다음과 같이 구할 수 있다. 

 

$$A^{-1} = (V \Lambda V^{-1})^{-1} = V \Lambda ^{-1} V ^{-1}$$

 

세 번째, A의 determinant를 계산하기 쉬워진다. det는 곱셈으로 이루어진 항을 따로 계산해도 된다. 또, 어떤 행렬의 det와 어떤 행렬의 역행렬의 det는 역수이기 때문에 Λ의 det만 구하면 된다. Λ의 det는 대각 성분인 eigen value의 곱이다. 

 

$$det(A) = det(V \Lambda V^{-1}) = det(V) det(\Lambda) det(V^{-1}) = \lambda_1 \lambda_2 \dots = \prod^n_{i=1}\lambda_i$$

 

네 번째, A의 trace를 계산하기 쉬워진다. trace는 cyclic property이 가능하기 때문에 아래의 수식과 같이 Λ의 trace만 계산하면 된다. Λ의 trace는 대각 성분인 eigen value의 합이다. 

 

$$tr(A) = tr(V \Lambda V^{-1}) = tr(\Lambda V^{-1} V) = tr(\Lambda) = \lambda_1 +  \lambda_2 + \dots = \sum^n_{i=1}\lambda_i $$

 

다섯 번째, rank-dificient는 det(A) = 0과 동치이다. 근데 eigen decomposition이 가능한 경우, A의 determinant는 eigen value의 곱이기 때문에, 0인 eigen value가 적어도 하나 이상 존재한다는 것이다. 

 

여섯 번째, A transpose의 eigen value = A의 eigen value이다. 왜냐하면 det(A - λI) = det((A - λI)^T) = det(A^T - λI)이다. 결국 A와 A^T의 eigen value의 곱이 같다는 것이기 때문이다. 

 

일곱 번째, A가 orthogonal matrix이면 아래의 수식을 만족한다. orthogonal matrix라고 하자. Qv = λv일 때, Qv를 스스로 내적 하게 되면 이는 2 norm 제곱이 된다. 

 

$$\lambda_i = \pm 1$

 

아래의 수식으로 위의 수식을 증명할 수 있다. 

 

$$Q\underline{v} = \lambda \underline{v}$$

$$(Q\underline{v})^T Q\underline{v} = \underline{v}^T Q^T Q \underline{v} = ||\underline{v}||^2_2 = \lambda^2 ||\underline{v}||^2_2$$

 

여덟 번째, diagonalizable matrix의 non-zero eigen value의 수는 rank(A)와 같다. A는 VΛV^-1로 나타낼 수 있다. rank(VΛV^-1)에서 V와 V inverse는 full rank이기 때문에 무조건  Λ의 rank를 따른다. 여기서 non-zero eigen value의 수가 rank(A)를 결정짓기 때문에 이를 증명할 수 있다. 

 

5. 2. 3. symmetric matrix는 무조건 diagonalizable

 

symmetric matrix라는 것은 A = A^T라는 것이다. 이를 전개해 보자. 

 

$$A = V \Lambda V^{-1}$$

$$A^T = V^{-T} \Lambda V^T$$

 

이때 위의 수식이 같아야 하므로 아래의 수식으로 전개할 수 있다. 

 

$$V = V^{-T}$$

$$V^{-1} = V^T$$

 

V의 inverse와 V의 transpose와 같다는 것은 행렬 V가 직교행렬이라는 것이다. V와 V inverse의 곱, 즉 V와 V transpose의 곱은 1이라는 것이기 때문이다. 곱해서 1이 된다는 것은 두 행렬이 직교한다는 것이다. orthogonal matrix V의 transpose만 알아도 V의 inverse를 알 수 있다. 따라서 A = QΛQ^T로 표현할 수 있다. 

 

이 사실을 통해 아래와 같이 전개할 수 있다. 

 

$$A = \begin{bmatrix} \underline{q_1} & \underline{q_2} & \underline{q_3} \end{bmatrix} \begin{bmatrix} \lambda_1 & 0 & 0 \\ 0& \lambda_2 & 0 \\ 0& 0& \lambda_3 \end{bmatrix}  \begin{bmatrix} \underline{q_1}^T \\ \underline{q_2}^T \\ \underline{q_3}^T \end{bmatrix}  = \begin{bmatrix} \lambda_1 \underline{q_1} & \lambda_2 \underline{q_2} & \lambda_3 \underline{q_3} \end{bmatrix}  \begin{bmatrix} \underline{q_1}^T \\ \underline{q_2}^T \\ \underline{q_3}^T \end{bmatrix}  = \lambda_1 \underline{q_1} \underline{q_1}^T +  \lambda_2 \underline{q_2} \underline{q_2}^T  + \lambda_3 \underline{q_3} \underline{q_3}^T  $$

 

위의 수식은 A라는 행렬을 3개의 rank 1 matrix로 나눌 수 있다는 것을 의미한다. q와 q^T의 곱은 항상 rank 1이기 때문이다. 직교하 rank 1 matrix 세 개의 합으로써 A는 rank 3 matrix가 된다. 

 

Figure 1

 

 5-3강: Principal Component Analysis - 고윳값 분해의 응용

 

풀고 싶은 문제는 Figure 2와 같이 데이터 분포가 있을 때, 이 분포의 평균값, 즉 데이터 분포를 가장 잘 설명하는 벡터를 찾고자 하는 것이다. 다시 말해 차원을 축소하는 것이라고 할 수 있다. 

 

Figure 2

 

각 좌표를 벡터에 사영을 내리면 2차원 데이터가 1차원 데이터로 축소된다. 이 분포의 분산이 가장 큰 방향이 이 분포를 가장 잘 설명한다고 할 수 있다. 그리고 그다음으로 설명을 잘하는 방향은 그 다음으로 분포가 가장 큰 방향인, 첫 번째 방향과 수직 하는 방향이다. 이를 이제 증명해 보자. 

 

먼저 데이터 분포의 평균이 0이 되도록 데이터를 옮겨주자. 원래의 데이터 위치는 d_i tilda로 표기하고, 평균은 d_i bar, 평균이 0으로 옮겨진 데이터 위치는 d_i로 표기한다. 

 

$$\underline{\tilde{d_i}} = \begin{matrix} \tilde{x_i} \\ \tilde{y_i} \end{matrix}$$

$$\underline{\bar{d}} = \begin{bmatrix} \bar{x} \\ \bar{y} \end{bmatrix}$$

$$\underline{d_i} = \begin{bmatrix} x_i \\ y_i \end{bmatrix}$$

 

Figure 3

 

또 벡터를 u라고 표기한다. 데이터 분포를 벡터 u에 직교하게 내렸을 때의 오차범위가 가장 작을 때가 가장 주성분 벡터라고 할 수 있다. 이 오차를 minimize하고 싶다. 이 오차범위의 크기를 수식으로 나타내고, 모든 데이터에 대해 계산하기 위해 시그마로 계산 해준 후, 데이터 개수인 N분의 1로 곱해주면 아래의 수식을 얻을 수 있다. 

 

$$\min_{\underline{u}} \frac{1}{N} \sum_i (\underline{d_1} - \underline{d_i}^T \underline{u} \underline{u})^T  (\underline{d_1} - \underline{d_i}^T \underline{u} \underline{u})$$

 

$$||\underline{u}||^2_2 = \underline{u}^T \underline{u} = 1$$

 

위 수식을 만족하는 u에는 조건이 있다. u의 크기는 1이어야 한다는 것이다. 만약 u 벡터의 크기가 작으면 당연히 내적 값, 오차 범위가 작아질 수밖에 없다. 우리가 찾고자 하는 것은 이것이 아니기 때문에 u 벡터의 크기를 1로 조건화하는 것이다. 

 

위의 수식을 전개해보면 아래의 수식과 같다. 

 

$$\frac{1}{N} = \sum_i (\underline{d_i}^T \underline{d_i} - \underline{d_i}^T \underline{u} \underline{u}^T \underline{d_i} - \underline{d_i}^T (\underline{d_i}^T \underline{u}) \underline{u} + \underline{d_i}^T \underline{u} \underline{u}^T (\underline{d_i}^T \underline{u}) \underline{u}) = - \frac{1}{N} \sum_i \underline{u}^T \underline{d_i} \underline{d_i}^T \underline{u} = - \underline{u}^T \frac{1}{N} \sum_i (\underline{\tilde{d_i}} - \underline{\bar{d_i}}) (\underline{\tilde{d_i}} - \underline{\bar{d_i}})^T \underline{u}$$

 

위의 제일 오른쪽 우변에서 벡터 u를 제외한 부분은 sample covariace matrix(분산을 구하는 식)인 것이다. 이 matrix를 R_d라고 한다. 이 수식에서 마이너스 min을 max로 고치면 아래의 수식과 같이 간단하게 나타낼 수 있다. 

 

$$\max \underline{u}^T R_d \underline{u}$$