0. 흐름

SVD 하기 전에 대각화를 알아야 되고 대각화를 알기 전에 고유값(eigen value)과 고유 벡터(eigen vector)에 대해 알아야 한다.. 맨날 까먹어서 정리한다.

1. 고유값과 고유 벡터

그 의미를 적진 않겠다. 바로 시작해보자.
A는 n x n square matrix이다.

를 만족하는 0이 아닌 열 벡터 x를 고유벡터라고 하고 $\lambda$를 고유값이라 한다.

A가 꼭 square matrix 여야 한다.
square matrix라고 고유값-고유벡터가 항상 존재하는 것은 아니다.
ex) $\begin{bmatrix}0&1\\-1&0\\ \end{bmatrix}$, $\lambda = i, -i$
어떤 행렬은 1개만 존재할 수도 있고 최대 n개까지 존재한다. (복소수까지 센다면 항상 n개)
ex) $\begin{bmatrix}0&0\\1&0\\ \end{bmatrix}, \lambda = 0, v= \begin{bmatrix}0\\1\\ \end{bmatrix}$ (삼각행렬의 특성이다.)

그렇다면

이 $\lambda$를 어떻게 구할 수 있을까? 왼쪽으로 이항한다.

0이 아닌 벡터 x가 있기 위한 필요충분 조건은

성질 1. 모든 고유값의 합은 trace와 같다.

$det(A-\lambda I)$를 Big formula방식으로 계산했다고 생각해보자.
$\begin{vmatrix} \begin{array}{ccc} a_{11}-{\lambda}& \cdots &a_{1n} \\ \vdots& \ddots &\vdots \\ a_{n1} &\cdots & a_{nn}-{\lambda} \end{array} \end{vmatrix} \\= (a_{11}-\lambda)(a_{22}-\lambda)\cdots(a_{nn}-\lambda)-R(\lambda)=0$
$R(\lambda)$에서 가장 높은 차수는 $n-2$임을 알 수 있다. $\lambda^{n}$과 $\lambda^{n-1}$은 모두 앞 항에서 만들어진다. $\lambda^{n}$의 계수는 $(-1)^{n}$, $\lambda^{n-1}$의 계수는 $(-1)^{n-1} \times tr(A)$이므로
근과 계수와의 관계에 의해서

성질 2. 모든 고유값의 곱은 det(A)와 같다.

$(a_{11}-\lambda)(a_{22}-\lambda)\cdots(a_{nn}-\lambda)-R(\lambda) \\= (\lambda_{1}-\lambda)(\lambda_{2}-\lambda)\cdots(\lambda_{n}-\lambda)$
에 $\lambda=0$을 대입하면 얻을 수 있다.

성질 3. 역행렬의 고유값은 원래 행렬의 고유값의 역수이다. (고유벡터는 동일)

성질 4. 고유값과 고유벡터의 관계 : 서로 다른 고유값에 대한 고유 벡터는 선형 독립이다.

성질 5. 대칭 행렬과 고유값 : 대칭행렬의 고유값은 실수이다. (허미션 행렬의 고유값은 실수이다.)

성질 6. 서로 다른 고유값을 가진 대칭행렬의 고유벡터는 서로 직교한다.

성질 7.더 나아가서, 대칭행렬의 고유벡터는 (고유값이 서로 다르지 않아도) 서로 수직이다.

2. 대각화

$A$의 n개의 선형독립인 고유벡터가 있다고 가정하자. 그리고 그 고유벡터를 열로 하는 matrix $S$ 가 있다고 생각해보자.
$\begin{aligned} AS &= A\begin{bmatrix} | & | & & |\\ x_1 & x_2 &\dotsm & x_n \\ | & | & & | \end{bmatrix}\\ &= \begin{bmatrix} | & | & & |\\ \lambda_1 x_1 & \lambda_2 x_2 &\dotsm & \lambda_n x_n \\ | & | & & | \end{bmatrix} \\&= \begin{bmatrix} | & | & & |\\ x_1 & x_2 &\dotsm & x_n \\ | & | & & | \end{bmatrix} \begin{bmatrix} \lambda_1 & & \\ & \ddots \\ & & \lambda_n \end{bmatrix} = S \Lambda \end{aligned}$
$S^{-1}$를 왼쪽에 곱하면 대각화, 오른쪽에 곱하면 eigen-value decomposition이라 한다.

성질 1. diagonalizable과 필요충분조건 : 고유벡터 n개가 선형 독립이다.

성질 2. 스펙트럼 정리 : (실수)대칭행렬은 orthogonal matrix로 대각화가 가능하다.

3. SVD

기본 성질

• The columns of $U$ are eigenvectors of $AA^T$
• The columns of $V$ are eigenvectors of $A^TA$
• The $r$ singular values on the diagonal of $\Sigma$ are the square roots of the nonzero eigenvalues of both $AA^T$ and $A^TA$

다음과 같은 의문이 등장할 수 밖에 없다.

1. $AA^T$와 $AA^T$의 모든 eigen value는 0 이상인가?
2. $AA^T$와 $AA^T$의 nonzero eigenvalues가 같은가?

질문의 답은 모두 Yes 이다. 쉽게 증명 가능하다.
$1.\ pf)\\ AA^Tv = \lambda v\\ v^TAA^Tv = \lambda v^Tv\\ ||A^Tv|| = \lambda ||v^Tv||\\ \therefore \lambda \geq0$

$A^TA$도 정확히 같은 방법으로 증명 가능

$2.\ pf)\\ AA^Tv = \lambda v$라고 하자.
$A^TAA^Tv = \lambda A^T v$, $A^T v$가 0이 아니면 $\lambda$는 $A^TA$의 고유값이다.
그런데 $A^T v=0$이라면 $AA^Tv=0$이고 $\lambda = 0$이어야 하므로 $A^T v \neq 0$
즉, $AA^T$의 nonzero eigen value는 $A^TA$의 nonzero eigen value이다.
반대방향도 같은 방법으로 증명 가능.

어떤 matrix든 SVD가 가능하다는 것은 $A^TA$, $AA^T$가 대칭행렬이므로 항상 orthogonal matrix로 대각화가 가능(대각화 성질 2.)하다는 것으로 알 수 있다.

** $A^TA, AA^T$ 모두 PSD 행렬