고윳값 분해

최소 자승법이라는 고비를 넘었으나 바로 2차 고비인 고윳값 분해가 나왔다. 칙쇼

뭐 어쨌든 여기서 배우는 것은 다음과 같다.

1. 고윳값, 고유 벡터란?
2. 고윳값, 고유 벡터 구하기
3. 고윳값 분해

 

고윳값, 고유 벡터란?

고윳값 분해에 대해서 다루기 전 먼저 고윳값과 고유 벡터에 대해 알아야 한다.

$$
A\textbf v = \lambda \textbf v
$$

고윳값과 고유 벡터는 위 식으로 설명할 수 있는데, 위 식을 만족하는 $\textbf v$를 eigen vector, $\lambda$를 eigen value라 부른다.

위 식에 대해서 자세히 살펴보기 전 이때 먼저 $A$가 정 사각 행렬이라는 점을 짚고 넘어가야 한다. 정 사각 행렬이 아닌 행렬에 대해서는 고값과 고유 벡터라는 것이 정의가 되지 않는다.

당연하게도 $A\textbf v$에서 $A$가 $m \times n$이라면 $\textbf v$는 $n \times 1$이고, 결과는 $m \times 1$인데 이 값이 $\textbf v$와 같은 shape를 가져야 하므로 $m = n$이 되어 $A$는 정 사각 행렬이 된다.

어쨌든 위 식을 살펴보면 정 사각 행렬 $A$에 $\textbf v$를 곱하니 그냥 $\textbf v$를 스칼라 배 한 것이 된다는 것이다.

즉, 임의의 정방 행렬 $A$와 어떤 벡터 $\textbf v$를 곱하면 벡터 $\textbf v$가 방향은 그대로인데, 크기만 바뀐다는 의미이다.

예를 들어 $A = \begin{bmatrix}
2 & -1 \\
-1 & 2
\end{bmatrix}$인 행렬이 있다고 해보고 여기에 여러가지 벡터들을 곱해보자.

$$
\begin{matrix}
A\begin{bmatrix}
2 \\
1
\end{bmatrix} \rightarrow \begin{bmatrix}
3 \\
0
\end{bmatrix} \\
A\begin{bmatrix}
1 \\
0
\end{bmatrix} \rightarrow \begin{bmatrix}
2 \\
-1
\end{bmatrix} \\
A\begin{bmatrix}
1 \\
-1
\end{bmatrix} \rightarrow \begin{bmatrix}
3 \\
-3
\end{bmatrix}
\end{matrix}
$$

잘 보면 $\begin{bmatrix}
1 \\
-1
\end{bmatrix} \rightarrow \begin{bmatrix}
3 \\
-3
\end{bmatrix}$로 이 벡터만은 방향은 그대로에 크기만 변한 것을 확인할 수 있고 나머지 두 벡터들은 방향도 변한 것을 확인할 수 있다.

https://youtu.be/xDARfmKauuA?si=5NY4lw0LFqGinIvq&t=585

위 영상에서 9:45초부터 시작하는 행렬에 의해 공간의 변화 시각화가 정말 좋다.

 

고윳값, 고유 벡터 구하기

고유 벡터란 정방 행렬 $A$와 곱하여 방향은 그대로인데 크기만 고값만큼 변하는 것이라는 것은 알았다.

그렇다면 어떻게 고윳값과 고유 벡터를 구할까? 방금처럼 마구잡이로 대입하는 방식은 컴퓨터를 이용해서 무수히 많은 벡터를 대입해 볼 수 있겠지만 이 방법은 너무 비 효율적이다. 좀 더 스마트한 방식이 필요하다.

$$
\begin{align}
A\textbf v &= \lambda \textbf v \\
A\textbf v - \lambda \textbf v &= 0 \\
(A - \lambda I)\textbf v &= 0
\end{align}
$$

위에서 본 식을 정리하면 위와 같다.

위 식에서 $\textbf v$가 결국 0 벡터라면 0이 되는 trivial solution과 $A-\lambda I$의 null space가 $\textbf v$가 되는 solution이 존재한다.

이때 $A - \lambda I$가 determinant $\det(A-\lambda I) \neq 0$인 경우 이 경우는 역행렬이 존재한다는 것이고, 이 행렬의 역 행렬을 양 변에 곱하면 $\textbf v = 0$인 경우밖에 없으므로 $\det(A-\lambda I) = 0$을 만족시키는 $\lambda$들을 찾으면 된다.

이렇게 얻은 $\lambda$들을 고윳값이라고 부르고 $A-\lambda I$의 null space에 존재하는 벡터의 basis를 보통 그 고윳값의 고유 벡터라 부르며, $\det(A-\lambda I) = 0$을 특성 방정식(Characteristic Equation)이라 부른다. 이 특성 방정식의 해가 고윳값들이다.

 

 

고윳값 분해(Eigen Decomposition)

고유가 분해

지금까지 고유 벡터와 고윳값에 대해서 알아보았다. 아니 그럼 고윳값 분해라는게 대체 뭔데 선형 대수 배운 놈들이 왜 그렇게 자주 언급하는 걸까?

고윳값과 고유 벡터를 처음 본 식을 다시 가져와서 살펴보자.

$$
A\textbf v = \lambda \textbf v
$$

이때 이를 만족하는 벡터들을 모두 찾은 행렬을 $V = \begin{bmatrix}
\textbf v_1, \textbf v_2, \dots, \textbf v_n
\end{bmatrix}$라 하자.

이때 아래를 만족하게 된다.

$$
AV = A\begin{bmatrix}
\textbf v_1, \textbf v_2, \dots, \textbf v_n
\end{bmatrix} = \begin{bmatrix}
\lambda_1\textbf v_1, \lambda_2\textbf v_2, \dots, \lambda_n\textbf v_n
\end{bmatrix}
$$

위 결과에서 우항은 $V$와 $\Lambda = \begin{bmatrix}
\lambda_1 & 0 & \dots & 0 \\
0 & \lambda_2 & \dots & 0 \\
0 & 0 & \dots & \lambda_n
\end{bmatrix}$의 곱이 되어 다음 식을 만족한다.

$$
AV = V\Lambda
$$

양변 오른쪽에 $V^{-1}$을 곱하면 최종적으로 아래와 같이 정리된다.

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

위와 같은 식으로 정리된 형태를 고윳값 분해(Eigen Decomposition)라 부르며 반대로 우항을 $\Lambda$만 남겨보자.

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

이 경우 $A$를 대각 행렬로 변화시켰으므로 이를 대각화(Diagonalization)이라 부르며 이것이 가능함을 대각화 가능(Diagonalizable)이라 부른다.

이때 대각화 가능함은 고윳값 분해가 가능하다는 것과 동치이며 이는 $A$가 $n \times n$인 행렬일때 독립인 Eigen vector의 개수가 n개라는 것과 동치이며 이는 $V$의 역행렬이 존재하다는 것과 동치이다.

그렇다면 이런 귀찮은 고윳값 분해를 하면 어떤 장점이 있길래 하는걸까?

 

 

고윳값 분해의 특성

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

고윳값 분해를 하게되면 위와 같이 $A$를 $V, \Lambda, V^{-1}$로 3가지로 분해가 되며, 위에서 설명한 것처럼 $V$는 eigen vector들을 column vector로 가지는 행렬, $\Lambda$는 eigen value들을 주 대각선 요소로 포함하는 대각 행렬, $V^{-1}$은 $V$의 역행렬이다.

 

이렇게 고윳값 분해가 가능한 경우 특성에 대해 알아보자.

1. $A^k = V\Lambda V^{-1} V\Lambda V^{-1} V\Lambda V^{-1} V\Lambda V^{-1} \dots V\Lambda V^{-1} = V\Lambda^kV^{-1}$로 고윳값 분해를 해놓으면 제곱이 간단하다. (대각행렬의 제곱은 매우 간편)
2. $A^{-1} = (V\Lambda V^{-1})^{-1} = V\Lambda^{-1}V^{-1}$
3. $\det(A) = \det(V\Lambda V^{-1}) = \det(V)\det(\lambda)\det(V^{-1}) = \det(V)\det(\lambda)\frac{1}{\det(V)} = \det(\lambda) = \prod_{i = 1} \lambda_i$로 행렬식이 고윳값의 합과 같다.
4. $tr(A) = tr(V\Lambda V^{-1}) = tr(V^{-1}V\Lambda) = tr(\Lambda) = \sum_{i = 0} \lambda_i$로 행렬의 Trace(대각합)은 Eigen value의 합과 같다.
5. rank deficient ↔ $\det(A) = 0$ ↔ 0인 eigen value가 하나 이상 존재 ↔ eigen value에 0이 없으면 역행렬이 존재한다.
6. $A^T$의 Eigen value는 $A$의 Eigen value와 동일
7. $\det(A-\lambda I) = \det((A - \lambda I)^T) = \det(A^T - \lambda I)$
8. $A$가 Orthogonal Matrix면 $\lambda_i = \pm 1$
9. $Qv = \lambda v$ → $(Qv)^TQv = v^TQ^TQv = v^TIv = ||v||^2_2 = \lambda^2||v||^2_2 \therefore \lambda = \pm 1$
10. $A$가 Positive Semi-definite(p.s.d)인 경우$i$$\lambda_i \ge 0$와 동치
11. Positive Semi-definite 정의에 의해 $z^TAz \ge 0$이 성립한다. 이때 $Az = \lambda z$이므로 $z^T\lambda z =\lambda ||z||^2_2 \ge 0$으로 $||z||^2_2$는 항상 양수이므로 $\lambda$ 또한 양수여야한다.
12. Diagonalizable Matrix의 non-zero eigen value의 수 = rank($A$)

 

 

Symmetric Matrix의 고윳값 분해

Symmetric Matrix의 경우에는 무조건 대각화가 가능하다(Diagonalizable). 이게 고윳값 분해에서 가장 중요한 점이다.

즉, $A^T = A \rightarrow A = V\Lambda V^{-1}$ 이때 매우 중요한 점이 있는데 $A$에 Transpose를 취해보면 아래와 같이 된다.

$$
\begin{matrix}
A^T = (V\Lambda V^{-1})^T = V^{-1}\Lambda^TV^T = A = V\Lambda V^{-1} \\
\therefore V^T = V^{-1}
\end{matrix}
$$

즉, $V$가 Orthogonal Matrix라는 것이며, $V^{-1}$을 구하기가 매우 쉬워진다. 최종적으로 Symmetric Matrix의 고윳값 분해는 아래와 같이 말할 수 있다.

💡 Symmetric Matrix는 Diagonalizable이며 $A = Q\Lambda Q^T$이다.

Symmetric Matrix을 Rank-1 행렬의 합으로 분해하기

Symmetric Matrix는 직교하는 eigen vector들로 고윳값 분해가 가능하단 것을 알게되었다.

이러한 성질을 이용해 데이터 압축과 연관지어서 볼 수 있다.

$$
\begin{matrix}
A = \begin{bmatrix}
q_1 & q_2 & q_3
\end{bmatrix} \begin{bmatrix}
\lambda_1 & 0 & 0 \\
0 & \lambda_1 & 0 \\
0 & 0 & \lambda_1
\end{bmatrix} \begin{bmatrix}
q^T_1 \\
q^T_2 \\
q^T_3
\end{bmatrix} = \begin{bmatrix}
\lambda_1 q_1 & \lambda_2 q_2 & \lambda_3 q_3
\end{bmatrix} \begin{bmatrix}
q^T_1 \\
q^T_2 \\
q^T_3
\end{bmatrix} \\
= \lambda_1 q_1q^T_1 + \lambda_2 q_2q^T_2 + \lambda_3 q_3q^T_3
\end{matrix}
$$

여기서 최종 결과 $A = \lambda_1 q_1q^T_1 + \lambda_2 q_2q^T_2 + \lambda_3 q_3q^T_3$에서 $q_iq^T_i$는 하나의 벡터로 만든 행렬이므로 rank = 1인 행렬들이다. 즉, $A$는 3개의 rank-1 행렬들의 가중합으로 표현될 수 있다는 것을 의미한다.

이때 $\lambda_i$가 매우 작다면 그 행렬은 매우 작은 정보를 가져 없어도 무방해진다. 즉, 데이터 압축 또는 노이즈 제거를 할 수 있다는 의미이다.

이를 벡터 $x$와 곱하는 경우에 대해서도 생각해보면 행렬과 벡터의 곱을 통한 선형 변환에 좋은 직관을 제공할 수 있다.

$$
Ax = \lambda_1 q_1q^T_1x + \lambda_2 q_2q^T_2x + \lambda_3 q_3q^T_3x
$$

위 식에서 $q_i^Tx$는 각 eigenvector로 내린 정사영 크기가 되고 여기에 $q_i$를 곱한 $q_iq^T_ix$는 $q_i$로 정사영 내린 벡터가 된다.

이는 $\lambda_i$만큼 각 eigen vector쪽으로 정사영 내린 벡터를 늘리고 줄인 벡터들의 가중합으로 행렬과 벡터의 곱의 결과를 해석해 볼 수 있다.

 

드디어 고윳값 분해라는 큰 산을 넘었다. 정 사각 행렬에 밖에 사용할 수 없다는 단점이 있지만 이를 직 사각 행렬에 일반화 시킨 SVD도 있다.

 

Reference

• Deeplearning Ch.2 Linear Algebra
• 유튜브 혁펜하임
• 데이터 사이언스 스쿨 - 고윳값 분해
• 행렬의 분해(고윳값 분해, 스펙트럼 분해, 특잇값 분해)