2022-10-30-psd.md

title	layout	Created	tags	use_math	comments	sitemap
Positive (Semi) Definite Matrices	post	October 25, 2022 3:48 PM	Linear Algebra	true	true	changefreq priority daily 1.0

Gilbert Strang의 MIT OCW 강의 5. Positive Definite and Semidefinite Matrices 를 주로 참고하여 정리한 내용입니다. Positive (semi) Definite임을 검증할 수 있는 방법(정의)에 대한 내용이다. 해당 내용을 이해하기 위해선, eigen value decomposition, energy of matrix, trace of matrix, pivot elimination 등을 알아야 한다.

---

Symmetric Postive Definite S

1. All eigen value $\lambda_i>0$
2. Energy $x^{T}Sx>0$ (for all $x\ne0$)
3. $S=A^{T}A$ (independent cols in A)
4. All Leading determinants > 0
5. All Pivots in elimination > 0

위의 5개의 정의 각각이 Positive Definite인지 검증(test) 할 수 있는 방법 들이다. Positive Definite S에 대한 가장 명쾌한 정의는 모든 고유 값들이 양수일 때, symmetric matrix가 Positive definite라고 할 수 있다. 하지만 행렬이 주어졌을때, PD인지 검증하려고 할때 고유값들을 모두 찾는 것은 어려울 수 있다.

다음과 같은 대칭 행렬 $S$가 주어졌을 때, Positive Definite한지 검증 해보자.

$$S= \begin{bmatrix} 3 & 4 \ 4 & 5\end{bmatrix}$$

$2\times2$이니깐 eigen value를 구해 볼수도 있고, energy로 확인할 수 있고, 3번과 같이 Factorize를 할 수 있다. 가장 쉬운 방법은 Determinant를 계산하는 방법이다. det(S) = -1 이고, 이것은 곧 두개의 eigen value의 곱이다. (이것에 대한 증명은 다음 링크의 6번 문제를 참고.)

즉 eigen value 중 하나는 음수 이므로 Positive definite가 아니라, indefinite matrix이다. 그러면 S를 positive definite로 만들어 보자. 5를 6으로 바꿔 보자.

$$S= \begin{bmatrix} 3 & 4 \ 4 & 6\end{bmatrix}$$

4번 방법에서 Leading은 무엇을 의미할까? 다음 예제에서 1x1 det값을 생각해보자

$$S_1=\begin{bmatrix} -3 & 4 \ 4 & -6\end{bmatrix}$$

$det(S_1)= 18$ 로 동일하지만 $1\times1 \space det(S_1)= -3$이고, 이것은 양수가 아니다. 즉, Leading determinant라는 것은 upper left로부터의 det값이고, n개의 eigen value들이 있고, All Leading determinant > 0를 검증하는 것 또한 n번 계산해야 한다.

이제 Pivot과의 연관성에 대해 고려해 보자. First Pivot은 무엇인가? $1\times 1$ entry 값인 3이다. Second Pivots는 다음과 같은 elimination을 통해 구해야 한다.

$$S= \begin{bmatrix} 3 & 4 \ 4 & 6\end{bmatrix} \rightarrow \begin{bmatrix} 3 & 4 \ 0 & 2/3\end{bmatrix}$$

( $2\over3$ = ${2\times 2 \space det}\over{1\times 1 \space det}$)

여기서 Energy를 계산 해보자.

$$x=\begin{bmatrix} x &y \end{bmatrix}$$라 하면 energy는 다음과 같이 작성할 수 있다.

$$f(x,y)=\begin{bmatrix}x&y\end{bmatrix} \begin{bmatrix} -3 & 4 \ 4 & -6\end{bmatrix}\begin{bmatrix}x\y\end{bmatrix}$$

다음을 전개해하면 다음과 같다.

$$f(x,y)=3x^2+6y^2+8xy$$

Graph of f(x,y)를 그려보자. 앞의 제곱이 있는 두개의 항은 항상 0보다 크고, 마지막 항은 음수가 될 수 있다. 만약 양수의 값이 음수보다 크다면 bowl 처럼 그래프가 그려진다. 다음은 energy of positive definite matrix의 그래프이다.

이게 딥러닝에 대한 것이다. Loss function이 $L(x,y)=x^TSx$의 꼴일 때 위와 같은 그래프가 나올 수 있다. 즉 말하고 싶은것은 딥러닝은 energy를 최소화 하기 위해 많은 계산을 한다는 것이다.

$L(x,y) = x^TSx+x^Tb$ 이라면 data b에 대한 least sqaure problem이라고 할 수 있다. 이 그래프 또한 Bowl 형태가 나온다. $L(x,y)$에 대한 minimum을 어떻게 찾을까? (더 복잡한 형태의 loss function에 대해서도)

$L(x,y)$가 convex, non-convex와 무관하게, Bowl의 surface 중 어떠한 point $x_0$에서 시작하여 minimum을 찾는다고 해보자. 기본적인 아이디어는 first derivative를 계산해서 gradient descent하는 것이다.

$$\nabla f=\begin{bmatrix}df\over dx \ df \over dy \end{bmatrix}$$

해당 지점에서의 gradient는 steepest한 방향을 알려준다고 할 수 있다. 하지만 항상 잘 작동하지 않는다. 두개의 Eigen value가 있다고 해보자. 하나는 1이고 하나는 매우 작은 값이라면 Bowl은 매우 길고 얇은 형태가 될 것이다. 그렇다면 valley(골짜기)를 금방 지나쳐 버릴 것이다.

이것이 왜 positive semidefinite한 이유 중 하나이다. Positive definite이라면 위와 같이 Loss function을 그릴 수 있다. 그렇다면 eigen value가 모두 같다면 Bowl은 Pefectly circular bowl일 것이다. 예를 들어 $f(x,y)=x^2+y^2$라고 하면, 어떤 곳에서 시작 하든 center(minimum)에 도달 할수 있을 것이다.

---

1. $S,T$가 positive definite라면, S+T 또한 positive definite일까? S+T에 대한 eigen value를 검사하는 것(1번 방법)은 어렵기 때문에, Energy를 계산(2번 방법)해보자.

   $$Energy : X^T(S+T)X$$

   $$x^T(S+T)x =x^TSx+x^TTx$$ 이므로 S+T 또한 Positive definite이다.

2. S가 positive definite라면, $S^{-1}$은 positive definite일까?

(1번방법) eigen value를 구하는 것으로 positive definite임을 증명할 수 있다. eigen values of $S^{-1}$는 $1\over \lambda$이므로 P.D이다.

1. $Q^{T}SQ$ (symmetric)은 P.D일까? (Q: orthogonal matrix)

   $Q^TSQ=Q^{-1}SQ$ ($\because$ Q is orthogonal)이고, 이 형태는 S와 similar matrix라고 할 수 있다. S와 similar 하다는 것은 같은 eigen value를 갖는 다는 것을 의미한다. 즉, 1번의 이유로 P.D이다.

   2번인 energy로 검증할 수 도 있다. $x^{T}Q^{T}SQx=y^{T}Sy$ ($Qx=y$라 하자.) 이고, y에 대한 energy이므로 양수이다.

---

Positive Semi Definite

1. All eigen value $\lambda_i\ge0$
2. Energy $x^{T}Sx\ge0$ (for all $x\ne0$)
3. $S=A^{T}A$
4. All Leading determinants $\ge$ 0
5. r Pivots $\gt$ 0, $r\le n$

---

$$S= \begin{bmatrix} 3 & 4 \ 4 & 16\over3\end{bmatrix}$$

위의 S에 대한 det(S)=0이므로, 0값의 eigen value를 갖는다. 그렇다면 다른 eigen value들이 양수인것을 어떻게 찾을까? Tr(S)를 통해 찾을 수 있다. $\lambda_2=0$이므로, $\lambda_1=8{1\over3}$일 것이다. 이것이 P.S.D이다.

다른 예시이다.

$$S= \begin{bmatrix} 1 & 1 &1 \ 1 & 1 &1 \ 1 & 1 &1 \end{bmatrix}$$

S는 Positive Semi Definite 일까? rank는 1이므로, 오직 하나의 non-zero eigen value가 존재한다. 그리고, trace(S)=3이므로, eigen value= {3,0,0}이다. 즉, S는 Positive Semi Definite이다.

Symetric matrix S이므로, eigen value들을 이용해서 다음과 같이 작성할 수 있다.

$$S=\lambda_1q_1q_1^T+\lambda_1q_1q_1^T+\lambda_1q_1q_1^T=Q^T𝐴Q$$ (spectrum theory에 대한 증명은 다음 링크를 참고하라.)