강의정리
$m$ x $n$ 행렬 $A$ 에 대해서 $A^T A$ 는 대칭인 양의 정부호 행렬 Symetric Positive Definte 이다. ( 열이 독립인 가정하에. )
$A^T A = V\Lambda V^T $ ($n$ x $n$) 로 표현할 수 있고, $V$ 는 고유벡터, $\Lambda$는 고유값으로 나타낼 수 있다. 여기서 고유벡터들은 정규직교하고 고유값은 0 보다 크다. ( 대칭인 양의 정부호 )
다른 대칭행렬 $AA^T = U\Lambda U^T$ ( $m$ x $m$ ) 로 표현할 수도있다. 여기서 고유값은 $A^TA$ 와 동일하지만 $\Lambda$ 행렬은 $m$ x $m$ 이다. 따라서 부족한 대각성분은 0 으로 채워진다.
우리가 찾으려는 것은 아래 식이고, $r$ 은 Rank 이다.
$$ \begin{matrix} Av_1 = \lambda_1 u_1\\ \cdots \\ Av_r = \lambda_r u_r \\ Av_{r+1} = 0 \end{matrix} $$
여기서 각각 $v$ 는 정규직교하고 $A$ 행렬의 변환을 통해서 정규직교하는 $u$ 로 옮겨진다.
위 식을 행렬로 변환하면, 아래 형태로 표현할 수 있다.
$$ A \begin{bmatrix} v_1 & \cdots & v_r & \cdots \\ \end{bmatrix} = \begin{bmatrix} u_1 & \cdots & u_r & \cdots \\ \end{bmatrix} \begin{bmatrix} \sigma_1 & & & \\ & \ddots & & \\ & & \sigma_r & \\ & & & \ddots \\ \end{bmatrix} \\ AV = U \Sigma \\ A = U\Sigma V^T \\ A^TA = (V\Sigma^T U^T)(U \Sigma V^T) = V \Sigma^T \Sigma V^T\frac{}{} \\ AA^T = (U\Sigma V^T)(V \Sigma^T U^T) = U \Sigma \Sigma^T U^T $$
위에서 봤듯이 $V$ 는 $A^TA$ 의 고유벡터이면서, $A$ 의 우특이벡터이다.
$U$ 는 $AA^T$ 의 고유벡터이면서, $A$ 의 좌특이벡터이다.
$\Sigma^2$ 은 $A^TA$, $AA^T$ 의 고유값 행렬이다. 그리고 $A^TA$, $AA^T$ 고유값 행렬의 양수 제곱근은 $A$ 의 특이값 행렬이된다.
식 $Av_k = \sigma_k u_k$ 에서 $u_k = \frac{Av_k}{\sigma_k}$ 으로 변형시킨다.
$AA^T$ 의 고유벡터인 $u$ 는 정규직교하기 때문에, $u_iu_j = I$ 을 만족한다.
$u_i^Tu_j = \frac{(Av_i)^T(Av_j)}{\sigma_i \sigma_j} = \frac{v_i^T A^TA v_j}{\sigma_i \sigma_j} = \frac{v_i^T(A^TA)v_j}{\sigma_i \sigma_j} = \frac{v_i^T \sigma_j^T v_j}{\sigma_i \sigma_j} = \frac{\sigma_j}{\sigma_i}v_i^T v_j = 0 $
$A$ 의 row space 의 정규직교기저 $v$ 와, col space 의 직교기저 $Av$ 가 만들어진다.
그래서 $A^TA$ 로 $V$, $\Sigma^2$ 만 구하면, $U$ 를 구할수 있다는 소리이다.
실제로 아주큰 직사각형 행렬을 사용하는 데이터과학에서는 어떻게할까?
위에서 특이값을 구하려면 $A^TA$ 행렬을 구해야하는데, 이는 엄청난 계산비용이 든다.
그래서 $A^TA$ 는 증명에 유용하기때문에 사용하고, 실제 계산은 다른 방법을 사용한다.
$A = U\Sigma V^T$ 는 어떤 기하학적인 의미를 가질까?
단위원에 속하는벡터 $x$ 에 대해서
$V^Tx$ 는 길이가 변하지 않는 회전, 반사 등 변환을 해서 동일한 단위원을 만들고,
$\Sigma V^Tx$ 는 벡터들을 특이값 $\sigma_1 \geq \sigma_2 \cdots $ 에 의해 늘려져 타원형태를 만들고,
$U \Sigma V^T x$ 는 또다른 길이는 동일한 회전, 반사 등 변환을 해서 회전된 타원을 만든다.
- 여기서 $V$ 와 $U$ 가 동일한 경우는?
행렬 $A$ 가 정사각행렬이고 ( $V$ 와 $U$ 의 차원이 동일 ), 대칭행렬이고 ($A = Q\Lambda Q^T$ 이 성립), 우리는 이미 특이값이 음수가 아닌것을 가정하기 때문에, $A$ 는 대칭인 양의 정부호 행렬 (또는 준정부호 행렬 ) 이다.
$A = U\Sigma V^T $ 변환은 미지수표현을 어떻게 변화시킬까?
$ A = \begin{bmatrix} a & b \\ c & d \\ \end{bmatrix} $ 에서 미지수는 4개이고 변환 $U\Sigma V^T$ 에 미지수 abcd 가 어떻게든 숨겨져 있다.
$\Sigma$ 행렬엔 2개의 변수가 숨겨져 있고,
회전, 반사행렬이라 볼 수 있는 $U$, $V$ 에는 $\theta$, $\phi$ 회전각 변수 2개로 표현할 수 있다.
복잡하지만 abcd 로 4개의 미지수를 표현할 수 있다.
3x3 행렬에서는?
행렬에는 9개의 미지수가 있다.
$\Sigma$ 에는 3개의 특이값 미지수와,
회전에는 Roll Pitch Yaw 으로 고정축 xyz 에 대한 반시계방향 각도로 생각할 수 있다.
따라서 3개 3개 총 9 개의 미지수가 생긴다.
$A = U\Sigma V^T$ 의 행렬식은 특이값의 곱과 동일할까?
행렬식을 구하기위해 $A$ 는 정사각행렬이라 가정한다.
행렬의 행렬식은 각각행렬의 곱과 같다.
$U$, $V^T$ 는 직교행렬이므로 행렬식이 1 이다. 그래서 대각행렬 $\Sigma$ 의 행렬식은 각 대각원소의 곱이고, 그 값은 특이값의 곱이다. -> yes!
그러면 고유값들의 곱과 특이값들의 곱이 같다. 또한 $\sigma_1 \leq \lambda_1 \leq \lambda_2 \leq \sigma_2$ 식을 만족한다.
$m$ x $n$ 행렬 $A = U\Sigma V^T$ 를 부분적으로 표현하기
행렬 $A$ 을 표현하기위해, $U$ 는 $m$x$m$ 이고, $\Sigma$ 는 $m$ x $n$, $V^T$ 는 $n$ x $n$ 크기이다.
그런데, 랭크가 $r$ 인 경우에 $U$ 의 마지막 $m-r$ 개의 벡터와 $V$ 의 마지막 $n-r$ 개의 벡터는 $\Sigma$ 에의해 사용되지않아서 0 인 부분을 제외해서 $U$ 를 $m$ x $r$ , $V$ 를 $r$ x $n$, $\Sigma$ 를 $r$ x $r$ 으로 표현할 수 있다.
극분해 Polar decomposition $A = U\Sigma V^T = SQ$
$S$ 는 대칭인 실수부분, $Q$ 는 직교행렬 허수부분을 의미한다.
$A = U\Sigma V^T$ 중간에 $A = U\Sigma U^T U V^T$ 를 추가해 대칭인 부분 $S = U\Sigma U^T$ 과 $Q = UV^T$ 부분으로 나눈다.
거대한 데이터 행렬 $A$ 의 SVD
데이터 행렬 $A$ 에서 어느부분은 noise 이고, 어느부분은 signal 이다. 이 중 어떻게 제일 중요한 signal 을 찾아낼 수 있나?
보통 큰부분이 중요하고, 각각의 원소를 확인하진 않을테니깐, $A = U\Sigma V^T$ 를 확인한다. 여기서 $U$, $V$ 는 직교행렬로 크기는 변하지않고, $\Sigma$ 가 중요한데 이중에서도 가장큰 특이값 $\sigma_1$ 에 의해 만들어지는 rank 1 행렬 $u_1 \sigma_1 v_1^T$ 를 확인하는 것이 제일 중요하다. 이 행렬이 $A$ 의 주성분이기 때문이다.
책 정리
가장 좋은 행렬 ( 실수 대칭행렬 $S$ ) 는 실수인 고유값과 직교인 고유벡터를 갖는다.
그런데 많은 행렬이 고유값이 복소수이거나, 고유벡터가 직교도 아니고, $A$ 가 정가각행렬이 아니면 $Ax=\lambda x $ 가 성립하지 않고, 고유벡터도 존재하지 않는다.
모든 행려에서 사용할 수있는 방법으로 특이값 분해 Singular Value Decomposition 가 있다.
$m$ x $n$ 실수행렬에서 $n$ 개의 우특이벡터 $v$ 와, $m$ 개의 좌특이벡터 $u$ 들은 각각 $R^n$ 과 $R^m$ 에서 직교하고, $Ax = \lambda x$ 를 만족하지는 않지만, $Av = \sigma u$ 관계를 만족한다.
$Av_1 = \sigma_1 u_1 \cdots Av_r = \sigma_r u_r Av_{r+1} = 0 \cdots Av_n = 0$
$r$ 은 랭크이고, $r$ 개의 $u$, $v$ 를 제외한 $v$ 의 마지막 $n -r$ 개는 $A$ 의 영공간이고, $u$ 의 마지막 $m-r$ 개는 $A^T$ 의 영공간이다. $\sigma_1 \cdots \sigma_r$ 인 특이값은 내림차순으로 정렬되고 양수인 특징을 가진다.
우특이벡터 $v$ 는 $V$ 의 열로 정규직교하고, 좌특이벡터 $u$ 는 $U$ 의 열로 정규직교한다. $\sigma$ 는 대각행렬 $\Sigma$ 으로 나타내고 아래식을 만족한다.
$ AV = U\Sigma$
$A\begin{bmatrix} v_1 & v_r & v_n \\ \end{bmatrix}= \begin{bmatrix} u_1 & u_r & u_m \\ \end{bmatrix} \begin{bmatrix} \sigma_1 & & \\ & \sigma_r & \\ & & 0 \\ \end{bmatrix}$
위의 식에서 처음 $r$ 개의 식은 $Av = \sigma u$ 를 만족하고 이 $r$ 개의 $u$, $v$ 의 쌍에서 $u$ 는 $A$ 의 열공간의 기저, $v$ 는 $A$ 의 행공간의 기저를 의미한다.
$V$ 와 $U$ 는 정사각행렬이고 각 벡터가 정규직교하기 때문에 직교행렬이다. 따라서 아래식을 만족한다.
$A$의 특이값 분해는 $A = U\Sigma V^T$ 이다.
$U\Sigma$ 와 $V^T$ 의 열-행 곱은 랭크가 1 인 $r$ 개의 조각으로 나눈다.
$A = U\Sigma V^T = \sigma_1 u_1 v_1^T + \cdots + \sigma_r u_r v_r^T$
특이값이 큰 조각이 더 중요하고, 조각들을 뭉쳐서 다시 행렬 $A$ 로 만들수 있다.
축소형 특이값 분해
행렬 $A$ 의 랭크가 낮고 영공간이 크면, $\Sigma$ 에는 0 을 많이 포함하고 이들은 행렬곱에 영향을 끼치지않는다. 따라서 필요없는 부분을 지워 처음 $r$ 개의 $v$, $u$, $\sigma$ 만 포함시켜, $AV=U\Sigma$ 를 $AV_r = U_r\Sigma_r$ 으로 줄일 수 있다. 여기서 $\Sigma_r$ 은 정사각행렬이다.
$AV_r = U_r \Sigma_r = A\begin{bmatrix} v_1 & \cdots & v_r \\ \end{bmatrix}= \begin{bmatrix} u_1 & \cdots & u_r \\ \end{bmatrix} \begin{bmatrix} \sigma_1 & & \\ & \ddots & \\ & & \sigma_r \\ \end{bmatrix}$
$A = U_r \Sigma_r V_r^T$
$A = \sigma_1 u_1 v_1^T + \cdots + \sigma_r u_r v_r^T$
직교단위벡터인 $v$, $u$ 로 $V^TV = I$, $U^TU=I$ 를 성립하지만, 정사각행렬이 아니기때문에 역행렬 관계는 성립하지 않는다.
데이터 과학에서 중요한 사실
다른 분해 $A = LU$, $A=QR$, $S=Q\Lambda Q^T$ 와 같이 $A=U\Sigma V^T$ 또한 랭크 1인 조각들로 나눈다.
여기서 특이값분해의 특징은 이 조각들이 중요한 순서 ( $\sigma_1 \geq \sigma_2 \cdots $ ) 으로 나온다.
첫 번째 $k$ 개의 조각의 합은 $A$ 에 가장 가까운 랭크 $k$ 행렬이다. $A_k = \sigma_1 u_1 v_1^T + \cdots + \sigma_k u_k v_k^T$ 는 $A$ 에 대한 최적의 랭크 $k$ 근사이다.
에카트-영 : $B$ 의 랭크가 $k$ 이면 $||A-A_k|| \leq ||A-B||$ 이다.
특이값 분해의 첫 번째 증명
$A = U\Sigma V^T$ 의 특이벡터 $u$, $v$ 를 구하기 위해, $A^TA$, $AA^T$ 형태의 대칭행렬을 생각한다.
$$ A^TA = (V\Sigma^TU^T)(U\Sigma V^T) = V\Sigma^T \Sigma V^T \\ AA^T = (U\Sigma V^T)(V\Sigma^T U^T) = U\Sigma \Sigma^T U^T $$
위의 식은 $Q\Lambda Q^T$ 의 형태로 해석할 수 있고, 고유값 $\Lambda$ 는 $\Sigma \Sigma^T$ 또는 $\Sigma^T \Sigma$ 에, 고유벡터는 $Q=V$ 또는 $Q=U$ 에 있다.
$V$ 는 $A^TA$ 의 정규직교 고유벡터를 포함한다.
$U$ 는 $AA^T$ 의 정규직교 고유벡터를 포함한다.
$\sigma_1^2, \cdots, \sigma_r^2$ 는 $A^TA$ 와 $AA^T$ 모두의 0 이아닌 고유값이다.
정규직교벡터 $v$ 를 선택했을때, $u$ 를 구해보자.
$A^TA$ 의 정규직교 벡터 $v_1$, $\cdots$, $v_r$ 와, $\sigma_k=\sqrt{\lambda_k}$ 를 선택하면, $u$ 를 판단하기 위해서 $Av=\sigma u$ 가 필요하다.
$v$ -> $u$ : $A^TAv_k = \sigma_k^2 u_k$ 이고, $u_k = \frac{Av_k}{\sigma_k}$ $(k = 1, \cdots, r)$
위 식을 이용해서 $u$ 가 $AA^T$ 의 고유벡터인지 확인한다.
$$ AA^Tu_k = AA^T (\frac{Av_k}{\sigma_k}) = A(\frac{A^TAv_k}{\sigma_k} = A \frac{\sigma_k^2v_k}{\sigma_k} = \sigma_k^2 u_k $$
$v$ 는 정규직교인데 $u$ 도 정규직교인지 확인한다.
$$ u_j^Tu_k = (\frac{Av_j}{\sigma_j})^T (\frac{Av_k}{\sigma_k}) = \frac{v_j^T(A^TAv_k}{\sigma_j \sigma_k} = \frac{\sigma_k}{\sigma_j}v_j^T v_k = \begin{cases} 1 & \text{ if } j=k \\ 0 & \text{ if } j \neq k \end{cases} $$
마지막 $n-r$ 개의 $v$ 와, $m-r$ 개의 $u$ 를 선택하는 것은, $A$ 와 $A^T$ 의 영공간의 임의의 정규직교기저를 선택하면 된다.
자동적으로 $N(A)$ 인 $v$ 는 처음 $r$ 개의 $u$ 들 $C(A^T)$ 와 직교하고, $N(A^T)$ 인 $u$ 은 처음 $r$ 개의 $v$ 들 $C(A)$ 와 직교한다.
EX) $A = \begin{bmatrix} 3 & 0 \\ 4 & 5 \\ \end{bmatrix}$ 에서 $U$, $\Sigma$, $V$ 를 찾아라.
먼저 고유값은 5, 3 이고, $ A^TA = \begin{bmatrix} 25 & 20 \\ 20 & 25 \\ \end{bmatrix} $
의 고유값은 45, 5, 고유벡터는 (1,1), (-1, 1) 이다. 각 고유벡터를 정규직교벡터로 만들기위해 $\sqrt{2}$ 으로 나누고, 이는 우특이벡터 $v_1$, $v_2$ 가 된다.
좌특이벡터 $u_1 = \frac{Av_1}{\sigma_1}$, $u_2 = \frac{Av_2}{\sigma_2}$ 이다.
$Av_1 = \sqrt{45} \frac{1}{\sqrt{10}} \begin{bmatrix} 1 \\ 3 \end{bmatrix} = \sigma_1 u_1$,
$Av_2 = \sqrt{5} \frac{1}{\sqrt{10}} \begin{bmatrix} -3 \\ 1 \end{bmatrix} = \sigma_2 u_2$
이렇게 $v$, $\sigma$, $u$ 를 찾았다.
$U = \frac{1}{\sqrt{10}}\begin{bmatrix} 1 & -3 \\ 3 & 1 \end{bmatrix}$
$\Sigma = \begin{bmatrix} \sqrt{45} & \\ & \sqrt{5} \end{bmatrix}$
$V = \frac{1}{\sqrt{2}}\begin{bmatrix} 1 & -1 \\ 1 & 1 \end{bmatrix}$
$U$, $V$ 는 $A$ 의 열공간, 행공간의 정규직교기저를 포함한다. 이 벡터들은 $A$ 를 대각화한다.
$A$ 는 랭크 1 인 행렬 $\sigma_1 u_1 v_1^T$ + $\sigma_2 u_2 v_2^T$ 로 나타낼수 있다.
- $S = Q\Lambda Q^T$ 가 대칭인 양의 정부호 행렬일 때, 행렬의 특이값 분해는?
$U\Sigma V^T = Q \Lambda Q^T$ 이다. $U=V=Q$ 이고, $\Lambda = \Sigma$ 이다.
- $S = Q\Lambda Q^T$ 가 음수인 고유값($Sx=-\alpha x$)을 가질때, 특이값과 벡터 $v$, $u$ 는?
특이값은 양수 $\sigma = \alpha$ 를 가지고, 특이벡터 $v$, $u$ 중 하나는 반드시 $-x$ 이다.
- $A=Q$ 가 직교행렬일 때, 모든 특이값이 1 인 이유?
$A^TA = Q^TQ = I $ 이기때문에, 모든 특이값은 1 이다. 그러니 $\Sigma = I$ 인데, 특이벡터는 $Q = U\Sigma V^T$ 에서 $Q = QII^T$ 이거나, $Q=(QQ_1)IQ_1^T$ 일 수 있다.
- 정사각 행렬 $A$ 의 모든 고유값이 $\sigma_1$ 보다 작거나 같은 이유?
직교행렬 $V$ , $U$ 를 곱해도 크기는 변하지 않기 때문이다. $||Ax|| = ||U\Sigma V^Tx|| = ||\Sigma V^T x|| \leq \sigma_1 ||x||$ 이다. 그래서 고유값 $|\lambda| ||x|| \leq \sigma_1 ||x||$, $|\lambda \leq \sigma_1$ 이다.
- $A=xy^T$ 의 랭크가 1 이면, $v_1$, $u_1$, $\sigma_1$ 은? $| \lambda_1| \leq \sigma_1$ ?
특이벡터 $u_1 = \frac{x_1}{||x_1||}$, $v_1 = \frac{y_1}{||y_1||}$, $\sigma_1 = ||x|| ||y||$ 이다. 위의 고유값은 $(xy^T)x = x(y^Tx) = \lambda x$ 으로 $\lambda = y^Tx$ 이다. 따라서 $|\lambda_1| = |y^Tx| \leq \sigma_1 = ||y|| ||x||$
위의 부등식 $|\lambda| \leq \sigma$ 는 유명한 슈바르츠 부등식 이다.
- 카루넨-뢰브 Karhunem-Loeve, KL 변환은? 특이값 분해와 관련은?
특이값 분해의 기하학적 의미
특이값 분해는 $A = U\Sigma V^T$ ( 직교행렬 x 대각행렬 x 직교행렬 ) 로 분리한다. 2차원에서 이는 평면의 회전(반사), 길이조절, 회전(반사)을 의미한다.
각 $v$ 에 의해 변형되고, $\sigma$ 에 의해 길이조절되고, $u$ 에 의해 변형된다.
단위원 위의 벡터 $x$ 에 대해서 $Ax$ 를 수행할때, $x$ 는 타원의 형태를 띄게된다. 이때 장축은 $v_1$ 이 변형되어 생성되고, 단축은 $v_2$ 가 변형되어 생성된다.
첫 번째 특이벡터 $\sigma_1$
첫 번째 특이벡터 $v_1$, 특이값 $\sigma_1$ 을 구해보자.
비율 $\frac{|| Ax ||}{|| x ||}$ 를 최대화하자. $x=v_1$ 에서 최대값은 $\sigma_1$ 이다.
단위원 벡터 $x$ 를 $A$ 로 변형할때, $||v_1||=1$ 에서 $||Av_1|| = \sigma_1$ 로 변환된다. 여기서 $U$ $\Sigma$ $V$ 를 모른다면 어떻게 $x=v_1$ 일때, $\frac{||Ax||}{||x||}$ 비율이 최대임을 알수있는지는 미분을 통해 알 수 있다. 식에 제곱을 하면, 미분은 더 간단해진다.
$ \frac{||Ax||^2}{||x||} = \frac{x^TA^Tx}{x^Tx} = \frac{x^TSx}{x^Tx} $ 의 최대값은?
- $ \frac{\partial }{\partial x_i} (x^Tx) = \frac{\partial }{\partial x_i}(x_1^2 + \cdots + x_i^2 + \cdots + x_n^2) = 2x_i $
- $ \frac{\partial }{\partial x_i} (x^TSx) = \frac{\partial }{\partial x_i}(\sum_{i} \sum_{j} S_{ij} x_i x_j) = 2\sum_{j}S_{ij}x_j=2(Sx)_i $
- $ \frac{\partial }{\partial x_i}\frac{x^TSx}{x^Tx} = (x^Tx)2(Sx)_i - (x^TSx)2(x)_i=0 $
- $x$ 가 S 의 고유벡터면, $2Sx - 2\lambda x = 0 $
$2Sx = 2\lambda x $ 이면, $\frac{x^TSx}{x^Tx} = \frac{||Ax||^2}{||x||^2}$ 의 최대값은 $S$ 의 고유값 $\lambda$ 이다.
최대화하는 $x$ 의 검색 대상은 $S = A^TA$ 의 고유벡터로 좁혀졌고, 최대화된 고유벡터는 $x=v_1$ 이고 고유값은 $\lambda_1 = \sigma_1^2$ 이다. 즉 미분적분을 통해 우특이벡터와 특이값을 구할수도있다.
첫번째 특이벡터는 구했고, $k+1$ 번째 특이벡터는 이전특이벡터 $v_1, \cdots, v_k$ 들에 수직하는 조건하에 최대값을 구하면 특이벡터 $v_{k+1}$ 와 특이값 $\sigma_{k+1}$ 을 구할수 있다.
이와 비슷하게 우특이벡터도 $\frac{||A^Ty||}{||y||} $ 를 최대화하면 얻을수 있다.
$A^T$ 의 특이벡터
특이값 분해는 행렬 $A$ 가 row space 기저 $v$ 를 col space 의 기저 $u$ 로 변환한다.
반대로 $A^T = V\Sigma U^T$ 는 $u$ 에서 $v$ 로 변환한다.
다른 대칭행렬을 통한 특이값 분해
$A$ 의 특이값분해를, $A^TA$, $AA^T$ 인 대칭행렬로 분해했지만, 다른방법으로 대칭 블록행렬 $ S = \begin{bmatrix} 0 & A \\ A^T & 0 \\ \end{bmatrix} $ 를 도입한다. ( $m+n$ , $m+n$ )
$ S = \begin{bmatrix} 0 & A \\ A^T & 0 \\ \end{bmatrix} $ 의 고유벡터는 $ \begin{bmatrix} u_k \\ v_k\end{bmatrix} $ 와 $ \begin{bmatrix} -u_k \\ v_k \end{bmatrix} $
이 행렬의 $2r$ 개의 고유벡터는 $2r$ 개의 고유값을 가진다. $\lambda = 0$ 인 고유벡터는 $A^T$, $A$ 의 영공간에 포함된 $u$, $v$ 를 반드시 포함한다.
$AB$ 와 $BA$ : 0 이 아닌 고유값
$A$ : (m x n), $B$ : (n x m) 이면 $AB$ 와 $BA$ 행렬은 동일한 0 이아닌 고유값을 가진다.
$ABx = \lambda x $ , 양변 $B$, $BA(Bx) = \lambda (Bx)$, $Bx$ 는 $BA$ 의 고유벡터로 고유값이 $\lambda$ 로 같다는 걸 알수있다. 여기서 $Bx$ 고유벡터이기 위해 $\lambda \neq 0 $ 이 필요하다.
$B$ 가 정사각행렬이고 가역이면, $B^{-1}(AB)B = AB$ 으로 $AB$, $BA$ 는 닮음이다. 따라서 동일한 고유값을 가진다고 할수 있다.
$B=A^T$ 이면, 특이값 분해에서 $A^TA$ 와 $AA^T$ 는 동일한 고유값을가질뿐아니라, $A$ 의 특이값을 제공한다.
더 작은 특이값을 가지는 부분행렬
$A$ 의 부분행렬에 대해서, 부분행렬은 전체 행렬의 노름보다 클 수 없음을 의미한다.
$B$ 에 $A$ 의 $M \leq m $ 개의 행과, $N \leq n $ 개의 열이 있으면, $||B|| \leq ||A||$ 이다.
$B$ 의 사라진 행과 열은 $\sigma_1$ 을 더이상 증가시키지 않는다. $\frac{||By||}{||y||} $ 의 최대값은 $\frac{||Ax||}{||x||} 보다 작거나 같다.
미분과 적분을 위한 특이값 분해
역사적으로 특이값분해는 행렬이아니라 함수를 위해 고안되었다.
함수적으로 보면 그러면 행렬 $A$ 는 변환, 즉 연산자로 여겨진다.
예를들어 살펴보면 적분 행렬 $A$, 미분 행렬 $D$ 를 생각해보자.
$Ax(s) = \int_0^t x(t) \mathrm{d} t$, $Dx(t) = \frac{\mathrm{d} x}{\mathrm{d} t}
$DA = I$ 를 만족하고, 상수의 미분은 0 이기때문에 $AD \neq I$ 이다. 그럼, $D$ 는 종속인 열이 있는 행렬과 같이 영공간이 존재한다.
$D$ 는 $A$ 의 유사역행렬이다.
- 여기서 $A$ 와 $D$ 의 특이벡터는 무엇일까?
$A$ 의 $v$ 는 코사인 함수 $u$ 는 사인함수, $D$ 의 $v$ 는 사인함수 $u$ 는 코사인함수이다.
$Av = \sigma u$, $A(\cos kt ) = \frac{1}{k} (\sin kt ) 이고, $D(\sin kt) = k (\cos kt)$
특이값 분해에서 알수 있듯이 각 특이벡터는 직교한다. 확인해보자.
$$ v_k^Tv_j = \int_{0}^{2 \pi}(\cos kt)(\cos jt)\mathrm{d}x = 0 \\
u_k^Tu_j = \int_{0}^{2\pi}(\sin kt)(\sin jt)\mathrm{d}x = 0 $$
여기서 두 함수 $x_1$ 와 $x_2$ 의 내적은 $x_1(t)x_2(t)$ 의 적분이다.
유한 차분
미분의 이산형태는 유한 차분이고, 적분의 이산형태는 합이다.
후진차분 $f(x) - f(x - \Delta x)$ 와 대응하는 4x3 행렬을 찾을 수 있다.
$$ D = \begin{bmatrix} 1 & & \\ -1 & 1 & \\ & -1 & 1 \\ & & -1 \\ \end{bmatrix} \\
D^T = \begin{bmatrix} 1 & -1 & & \\ & 1 & -1 & \\ & & 1 & -1 \\ \end{bmatrix} $$
이 행렬의 특이값과 특이벡터를 찾아보자.
$$ D^TD = \begin{bmatrix} 2 & -1 & \\ -1 & 2 & -1 \\ & -1 & 2 \\ \end{bmatrix} \\
DD^T = \begin{bmatrix} 1 & -1 & & \\ -1 & 2 & -1 & \\ & -1 & 2 & -1 \\ & & -1 & 1 \\ \end{bmatrix} $$
이 행렬들의 고유값은 아래와 같다.
$$ \lambda_1 = \sigma_1^2 = 2 + \sqrt{2} & \lambda_2 = \sigma_2^2 = 2 & \lambda_3 = \sigma_3^2 = 2 - \sqrt{2} $$
$D^TD$ 의 고유벡터 $v$ 는 $D$ 의 좌특이벡터이고 이는 이산 사인이다. $DD^T$ 의 $u$ 는 $D$ 의 우특이벡터이고 이산 코사인이다.
$$ \sqrt{2}V = \begin{bmatrix} \sin{\frac{\pi}{4}} & \sin{\frac{2\pi}{4}} & \sin{\frac{3\pi}{4}} \\ \sin{\frac{2\pi {4}} & \sin{\frac{4\pi}{4}} & \sin{\frac{6\pi}{4}} \\ \sin{\frac{3\pi}{4}} & \sin{\frac{6\pi}{4}} & \sin{\frac{9\pi}{4}} \\ \end{bmatrix} \\
\sqrt{2}U = \begin{bmatrix} \cos{\frac{1}{2}\frac{\pi}{4}} & \cos{\frac{1}{2}\frac{2\pi}{4}} & \cos{\frac{1}{2}\frac{3\pi {4}} & 1 \\ \cos{\frac{3}{2}\frac{\pi}{4}} &\cos{\frac{3}{2}\frac{2\pi}{4}} & \cos{\frac{3}{2}\frac{3\pi}{4}} & 1 \\ \cos{\frac{5}{2}\frac{\pi}{4}} & \cos{\frac{5}{2}\frac{2\pi}{4}} & \cos{\frac{5}{2}\frac{3\pi}{4}} & 1 \\ \cos{\frac{7 {2}\frac{\pi}{4}} & \cos{\frac{7}{2}\frac{2\pi}{4}} & \cos{\frac{7}{2}\frac{3\pi}{4}} & 1 \\ \end{bmatrix} $$
이 행렬들이 유명한 이산 사인변환 (Discrete Sine Transform, DST) 행렬과, 이산 코사인 변환 (Discrete Cosine Transform, DCT) 행렬이고, DCT 행렬은 JPEG 이미지 압축의 핵심이다.
이는 하나의 예로 특이값분해가 얼마나 중요한지 나타낸다.
극분해 Polar Decomposition $A = SQ$
모든 복소수 $x+iy$ 는 극형식 Polar Form $re^{i\theta}$ 으로 표현할 수 있다. 극형식은 단위원 위의 $e^{i\theta}$ 에 수 $r \geq 0$ 를 곱한 것이고, $x+iy = r\cos{\theta} + ir\sin{\theta} = re^{i\theta}$ 이 성립한다.
이 수들을 1x1 의 행렬로 생각한다면, $e^{i\theta}$ 는 직교행렬 $Q$로, $r \geq 0 $ 은 양의 준정부호 행렬 $S$ 생각해서 표현할 수 있다.
이 1x1 행렬을 m x n 행렬로 확장한 것이 극분해 Polar Decomposition 이다.
즉 행렬 $A$ 를 직교행렬과 양의 준정부호 행렬 $S$ 의 곱으로 나타낸다.
$A = U\Sigma V^T = (UV^T)(V\Sigma V^T) = (Q)(S)$ 또는,
$A = U\Sigma V^T = (U \Sigma U^T) (UV^T) = (K)(Q)$ 로 분해할 수 있다.
행렬 $S$, $K$ 는 $A$ 의 특이값을 고유값으로 가지기 떄문에, 양의 준정부호 행렬이다.
$A$ 가 가역이면, $\Sigma$ 는 정사각행렬에 대칭행렬이고, $S$ $K$ 또한 대칭행렬이다. 또한 선행하는 모든 $A$ 의 행렬식이 양수이고 $A$ 의 특이값의 모든 곱이 양수이기 때문에 $S$, $K$ 또한 양의 정부호이다.
$A$ 가 가역이아니면, $S$ $K$ 는 양의 준정부호 행렬이된다.
'선형머수학' 카테고리의 다른 글
| 10. 레일리 몫과 일반화된 고유값 (0) | 2022.04.16 |
|---|---|
| 9. 주성분과 최적의 낮은 랭크 행렬 (0) | 2022.04.15 |
| 7. 대칭인 양의 정부호 행렬 Symmetric Positive Definite (0) | 2022.04.11 |
| 6. 고유값과 고유벡터 (0) | 2022.04.11 |
| 5. 직교행렬과 부분공간 (0) | 2022.04.09 |