矩陣對角化與奇異值分解

09-10

矩陣對角化與奇異值分解

來自專欄本科生的筆記本6 人贊了文章

Part.1 矩陣對角化

1.1矩陣和線性變換

Definition1: 對於向量空間 $V$ 的一個變換 $mathscr{A}$ （一般使用花體拉丁字母 $mathscr{A},mathscr{B},cdots$ 代表 $V$ 的變換, $mathscr{A}(oldsymbol{alpha})$ 代表元素 $oldsymbol{alpha}$ 在變換 $mathscr{A}$ 下的象)，如果對於 $V$ 中任意元素 $oldsymbol{alpha,eta}$ 和數域 $P$ 中任意數 $k$ ，都有： $egin{equation} mathscr{A}(oldsymbol{alpha+eta})=mathscr{A}(oldsymbol{alpha})+mathscr{A}(oldsymbol{eta}),~~mathscr{A}(koldsymbol{alpha})=kmathscr{A}(oldsymbol{alpha}) end{equation} ag{1*}$ 則稱變換(映射) $mathscr{A}$ 為線性變換（映射)

一個矩陣 $A_{m imes n}$ 乘一個向量 $v_{n imes 1}$ 實際上是把 $v_{n imes 1}$ 「變換」為另一個向量 $(Av)_{m imes 1}$ ，即將 $v_{n imes 1} in mathbb{R^n}$ 映射到 $mathbb{R^m}$ 中。矩陣乘法法則告訴我們 $A(v_1+v_2)=Av_1+Av_2,A(kv)=kA(v) ag{2}$

式(2)符合式(1)關於線性變換的定義，因此矩陣和向量相乘本質上是一種線性變換，這種變換將 $mathbb{R^n}$ 中的一個向量映射到 $mathbb{R^m}$ 中去。

比如 $left[ egin{matrix}2 &-1\1& 0\3&2end{matrix} ight] left[egin{matrix}1\1end{matrix} ight]= left[ egin{matrix}1\1\5end{matrix} ight]$ 將 $left[egin{matrix}1\1end{matrix} ight] in mathbb{R^2}$ 映射為 $left[ egin{matrix}1\1\5end{matrix} ight] in mathbb{R^3}$ 。

當 $m=n$ 即 $A$ 是方陣時這個線性變換為 $mathscr{A}：mathbb{R^n} longmapsto mathbb{R^n} ag{3}$

$A_2=left[ egin{matrix}0 &-1\1& 0end{matrix} ight]$ 與向量 $left[egin{matrix}1\1end{matrix} ight]$ 相乘 $left[ egin{matrix}0 &-1\1& 0end{matrix} ight] left[ egin{matrix}1\1end{matrix} ight]= left[ egin{matrix}-1\1end{matrix} ight]$ 意味著將二維空間 $V$ 中的向量 $left[egin{matrix}1\1end{matrix} ight]$ 映射為二維空間 $W$ 中的向量 $left[ egin{matrix}-1\1end{matrix} ight]$

1.2特徵值與特徵向量

先給出定義，然後我們會用一個例子來說明特徵向量的幾何意義

Definition2:設 $A$ 是 $n$ 階方陣，如果數 $lambda$ 和 $n$ 維非零向量 $x$ 使 $Ax=lambda x$ 成立，則稱 $lambda$ 是特徵值， $x$ 是對應於 $lambda$ 的特徵向量

How to find $x$ : $Ax=lambda xLeftrightarrow (A-lambda I)x=0$

注意到 $A-lambda I$ 是一個方陣，所以 $(A-lambda I)x=0 ag{4*}$ 在 $det(A-lambda I )=0$ 時有非零解，這些非零解便是 $A$ 的特徵向量。現在看一個例題。由 $det(A-lambda I )=0$ 可列出關於 $lambda$ 的方程，這個方程被稱為 $A$ 的特徵方程。

Problem: 設有矩陣 $A=left[ egin{matrix}.8&.3\.2&.7end{matrix} ight]$ ，求它的特徵值和特徵向量 Solution： $detleft[ egin{matrix}.8-lambda&.3\.2&.7-lambdaend{matrix} ight] =lambda^2- frac{3}{2}lambda+frac{1}{2}= (lambda -1)(lambda-frac{1}{2})$
令其等於零可得： $lambda_1=1,lambda_2=1/2$ ，將 $lambda_1,lambda_2$ 分別代回方程(4)可得： $Ax_1=left[ egin{matrix}.8&.3\.2&.7end{matrix} ight] left[ egin{matrix}.6\.4 end{matrix} ight]=1x_1 \ Ax_2=left[ egin{matrix}.8&.3\.2&.7end{matrix} ight] left[ egin{matrix}1\-1 end{matrix} ight]=frac{1}{2}x_2 ag{5}$

用一張圖表示(5)：

由上圖不難發現特徵向量在經過與 $A$ 相乘這個變換操作後得到的新向量方向與特徵向量相同。

1.矩陣與向量相乘是一種線性變換
2.矩陣的特徵向量經過矩陣所代表的線性變換後方向與原方向保持一致

這種「變換」中的」不變性「被我們看作矩陣的一種特徵，故而叫特徵值與特徵向量，它反映了變換矩陣所代表的線性變換的固有特點。

1.3矩陣對角化

假設 $A_{n imes n}$ 有 $n$ 個特徵值 $lambda_1,lambda_2,dots,lambda_n$ 和特徵向量 $x_1,x_2,dots,x_n$ ，由1.2中方程 $Ax=lambda x$ 可得:

$AS=A left[ egin{matrix} x_1 dots x_nend{matrix} ight]= left[ egin{matrix}lambda_1 x_1 dots lambda_nx_nend{matrix} ight] ag{6}$

$SLambda=left[ egin{matrix}lambda_1 x_1 dots lambda_nx_nend{matrix} ight]= left[ egin{matrix} x_1 dots x_nend{matrix} ight] left[ egin{matrix} lambda_1 &\ &ddots &\ &&lambda_nend{matrix} ight] ag{7}$

由(6)(7)得： $S^{-1}AS=LambdaLeftrightarrow A=S Lambda S^{-1}\ Lambda=left[ egin{matrix} lambda_1 &\ &ddots &\ &&lambda_nend{matrix} ight]\ S=left[egin{matrix}x_1 x_2dots x_n end{matrix} ight] ag{8*}$

上式意味著如果給一個方陣 $A$ 左乘其特徵向量矩陣 $S$ 的逆，右乘 $S$ 便可得到一個對角陣。

觀察式(8)不難發現要對角化 $A$ 有兩個前提條件

1. $S$ 可逆
$S=left[egin{matrix}x_1 x_2dots x_n end{matrix} ight]$ 可逆意味著 $A$ 有 $n$ 個獨立的特徵向量 $x_1,x_2,dots,x_n$
2. $A$ 是方陣
非方陣沒有特徵值和特徵向量，也就無法構成 $S$ 矩陣

Part.2 實對稱矩陣

2.1 實對稱矩陣的對角化

Definition3：若 $A^T=A$ ，則稱 $A$ 為對稱矩陣 。
由定義容易知道一個對稱矩陣 $A$ 必然是一個方陣

Theorem1: 投影矩陣 $P$ 必為對稱矩陣 Proof：

根據眼淚不會為你而流：投影矩陣與最小二乘法這篇文章1.2部分的內容可知，如果我們要把一個向量 $b$ 投影到由向量 $a_1,dots,a_n$ 張成的空間 $C(A),A=[a_1 a_2 dots a_n]$ 中去，就要找到一個投影矩陣 $P=A(A^TA)^{-1}A^T$ 用 $b$ 去右乘 $P$ 來得到 $b$ 在 $C(A)$ 中的投影 $p=Pb$ 。
$P^T=[A(A^TA)^{-1}A^T]^T =(A^T)^T[(A^TA)^{-1}]^TA^T =(A^T)^T[(A^TA)^T]^{-1}A^T =P$
故投影矩陣 $P$ 為對稱矩陣Q.E.D

Theorem2:所有實對稱矩陣都可分解為 $A=QLambda Q^{-1}=QLambda Q^T,Q^{-1}=Q^T$ 。
其中 $Q$ 由 $A$ 的正交特徵向量組成， $A$ 的特徵值均為實數。

a.先證明 $A$ 的所有特徵值為為實數

Proof: 1.2告訴我們求 $A$ 的特徵值等價於求方程 $(A-lambda I)x=0 ag{a1}$ 的非零解，我們先利用 $det(A-lambda I)=0$ 求得特徵值 $lambda$ ,再將 $lambda$ 回代入(a1)解出特徵向量 $x$ 。容易發現，當特徵值為複數時， $(A-lambda I)$ 必有複數元素，因此特徵向量 $x$ 也必含複數元素。則有 $Ax=lambda x\ ag{a2} lambda=a+ib(a,b in R)$
因為 $A$ 是實矩陣，所以兩邊取共軛得： $A overline x= overline lambda overline x Leftrightarrow overline x^T A= overline x^T overline lambda \ overline lambda=a-ib(a,b in R) ag{a3}$
給(a2)左乘 $overline x^T$ ，給(a3)右乘 $x$ 得： $overline x^T Ax= overline x^T lambda x \ overline x^T Ax= overline x^T overline lambda x ag{a4}$
所以 $lambda overline x^Tx = overline lambdaoverline x^T x$ ，又 $overline x^T x =|x_1|^2+|x_2|^2+dots=||x||^2 e 0$
所以 $overline lambda=lambda ag{*}$

b.證明對稱矩陣 $A$ 的特徵向量均正交之前，先引入兩個引理

Lemma1: 實對稱矩陣 $A$ 對應於不同特徵值的特徵向量必正交 Proof：設 $p_1,p_2$ 為對應於 $lambda_1,lambda_2(lambda_1 eqlambda_2)$ 的特徵向量：

$Ap_1=lambda_1p_1\ Ap_2=lambda_2p2 ag{b1}$
想辦法構造出 $p_1^Tp_2$ (或 $p_2^Tp_1$ ):
$lambda_1p_1^T(=(lambda_1p_1)^T=p_1^TA^T)=p_1^TA$ $lambda_1p_1^T p_2=p_1^TA p_2=p_1^Tlambda_2p2$
即 $(lambda_1-lambda_2)p_1^T p_2=0 ag{b2}$ $ecause lambda_1 eqlambda_2 herefore p_1^Tp_2=0$ Q.E.D.

Lemma2: 若 $lambda$ 是實對稱矩陣 $A$ 的特徵方程的 $r$ 重根，則 $r(A-lambda I)=n-r$ , $dim(N(A-lambda) )=r$ ,因此可從 $N(A-lambda I)$ 中選出 $r$ 個正交的向量作為 $(A-lambda I)=0$ 的解，也就是作為 $A$ 的特徵向量 。
Proof：略

容易驗證當 $n$ 階方陣 $A$ 的互不相等的特徵值 $lambda_1,dots,lambda_s$ 的重數分別為 $r_1,dots,r_s$ 時， $r_1+dots+r_s=n$ 。

根據Lemma2可知：對於每一個 $lambda_i$ 均對應了 $r_i$ 個正交的特徵向量，記這組正交向量為 $Q_i$ 。根據Lemma1可知: 不同組內的特徵向量也相互正交。所以 $Q_1,dots,Q_s$ 中的 $r_1+dots+r_s=n$ 個特徵向量均正交。

2.2小結*

在矩陣對角化後面介紹對稱矩陣主要是因為實對稱矩陣有著良好的性質和廣泛的應用。下面我們概述下前面的內容。

2.2.1矩陣對角化的本質

不了解基變換矩陣請參考 【熟肉】線性代數的本質 - 09 - 基變換

特徵向量來自於方陣 $A$ 的行空間中。特徵向量 $p in R(A)$ ,式 $Ap=lambda p$ 表明對 $p$ 施加 $A$ 所代表的變換 $mathscr{A}:mathbb{R^n} longmapsto mathbb{R^n}\ mathscr{A}:rowspace longmapsto columnspace$ 後，將其映射為 $column space$ 中的 $lambda p$ ，也就是說在映射前後， $p$ 的方向不發生改變而長度伸縮 $lambda$ 倍。當方陣有足夠的( $n$ 個)特徵向量時，我們用這些特徵向量作為空間 $mathbb{R^n}$ 的基，由特徵向量的定義知：線性變換 $mathscr{A}$ 在這組基向量上都是伸縮變換 $mathscr{A}(p_1,dots,p_n)=A(p_1,dots,p_n)= lambda_1p_1+dots+lambda_np ag{9}$

$A$ 這個矩陣代表的線性變換是在基向量 $(1,0,dots,0)(0,1,dots,0)dots(0,0,dots,1)$ 上進行的，而 $Lambda=S^{-1}AS$ 則是在基向量 $p_1,dots,p_n$ 上進行的， $S$ 是一個基變換矩陣。

$A$ 和 $Lambda$ 是同一個線性變換在不同基下的描述。
矩陣對角化就是把一組基上的線性變換用另一組基來描述，用後一組基描述時，線性變換 $mathscr{A}$ 只是單純的伸縮變換。

當方陣沒有足夠的（ $n$ 個）線性無關的特徵向量時，就無法作為 $mathbb{R^n}$ 的一組基，也就無法在特徵向量基上描述線性變換 $mathscr{A}$ 。

當 $A$ 不是實對稱矩陣時，我們可以直接組成 $S$ ，也可以將特徵向量單位化再組成 $S$

我們為什麼能對特徵向量進行單位化，既然可以單位化那能不能正交化呢？

Lemma3：如果 $p$ 是 $A$ 的特徵向量，則 $A(kp)=lambda ( k p),k in R$ ，即 $kp$ 也是 $A$ 的特徵向量。 Lemma3解釋了特徵向量為什麼能夠單位化。同時注意：如果對特徵向量進行正交化，特徵向量將不再保持原有方向，與特徵向量保持方向不變的性質相衝突。所以一般而言不能對非正交的特徵向量進行正交化操作。

特別地，當方陣 $A$ 是對稱矩陣時，我們證明了 $A$ 一定有足夠的( $n$ 個)線性無關特徵向量構成 $S$ 矩陣，並且此時 $S^T=S^{-1}$ , 即 $S$ 是單位正交矩陣(orthonormal matrix)。

雖然我們只證明了 $S$ 是正交矩陣(orthogonal matrix)，但根據Lemma3，我們可以將特徵向量全部單位化再組成 $S$ ,這樣 $S$ 就變成了單位正交矩陣，也就有 $S^T=S^{-1}$

2.2.2實對稱矩陣的對角化

特徵向量來自方陣的行空間， $n$ 階實對稱矩陣必有 $n$ 個單位正交的特徵向量。我們完全可以用 $n$ 個單位正交的特徵向量 $p_1,dots,p_n$ 作為行空間 $R(A):mathbb{R^n}$ 的基向量組 ，令人偷稅的是，在經過方陣所代表的線性變換映射後，這組基在列空間中的象仍是正交的。一般而言，正交的總是最好最簡潔最方便的！

Proof: $mathscr{A}(p_1,dots,p_n)=A(p_1,dots,p_n)= lambda_1p_1+dots+lambda_np_n ag{c1}$
因為 $p_1,dots,p_n$ 正交，所以 $p_i^Tp_j=0(i eq j)$ ,故 $lambda_ip_i^Tlambda_jp_j=0(i eq j) ag{c2}$ Q.E.D

Part.3奇異值分解(SVD)

3.1SVD的動機和靈感

當 $A$ 是方陣時我們給出了矩陣對角化的方法，當 $A$ 不是方陣時我們能不能也將 $A$ 「對角化」呢？

對角化打引號是因為當 $A$ 不是方陣時，我們通過SVD得到的是形如 $Sigma= left. left[ egin{matrix} sigma_1&0&dots&0\ 0&sigma_2&dots&0\ vdots&vdots&ddots&sigma_r\ vdots&vdots&vdots&vdots end{matrix} ight] ight } ext{一共$m>r$行}, r=rank(A)$
或者形如 $Sigma^T$ 的矩形」對角陣「。而在Part.1和Part.2中我們得到的對角陣是方陣 $Lambda=left[ egin{matrix} sigma_1&&&\ &sigma_2&&\ &&ddots&\ &&& sigma_n end{matrix} ight]$ 。

在2.2中我們知道方陣 $A_{n imes n}$ 對角化的含義：

矩陣對角化就是把一組基上的線性變換用另一組基（特徵向量基）來描述。用後一組基描述時，線性變換 $mathscr{A}$ 只是單純的伸縮變換，其對應的變換矩陣為對角矩陣 $Lambda$ 。特別地，當 $A$ 是實對稱矩陣時，特徵向量基是正交的。

也就是說 $Lambda$ 和 $A$ 代表的是同一種線性變換，只是用於描述的基向量不同罷了。

奇異值分解本質上同方陣對角化意義相同，即在不同的基上描述同一種線性變換。矩陣 $A_{m imes n}$ 對應的線性變換為 $mathscr{A} : mathbb{R^n} longmapsto mathbb{R^m}$ ，對於 $mathbb{R^i}$ 我們總是默認基向量為 $e_1=overbrace{(1,0,dots,0)}^{ ext{一共$i$個}}\ e_2=(0,1,dots,0)\ dots=dots\ e_i=(0,0,dots,1)$

而 $A$ 便是在這組默認的基上對 $mathscr{A}$ 的數值化描述，因此實際上 $A$ 對 $mathscr{A}$ 的數值描述為： $mathscr{A} : span{e_1,e_2,dots,e_n} mapsto span{e_1,e_2,dots, e_m} ag{10}$

方陣對角化中選擇合適的基（由特徵向量組成的基）描述線性變換使該變換在數值描述上成為單純的伸縮變換，特別地，在對稱方陣對角化過程中這組基是正交的。於是我們就想能不能給非方陣 $A_{m imes n}$ 對應變換 $mathscr{A}$ 的定義域 $mathbb{R^n}$ ，值域 $mathbb{R^m}$ 也選擇合適的基向量，使變換 $mathscr{A}$ 在數值描述上也像方陣對角化里那樣變為單純的伸縮變換？或者更進一步像對稱方陣對角化中那樣選取的基也是正交的？答案當然是能！

3.2選擇合適的基

在開始選擇基向量之前先回顧矩陣四個子空間的聯繫圖

給 $mathscr{A}$ 的定義域也就是 $mathbb{R^n}$ 選擇一組正交基等價於在 $A$ 的 $rowspace$ 和 $nullspace$ 中分別找到兩組正交的基。

在投影矩陣與最小二乘法這篇文章的附錄 [2]，我們證明過 $N(A^TA)=N(A) ag{11}$ 由矩陣的四個子空間及其聯繫這篇文章2.2部分可知行空間和零空間互為 $mathbb{R^n}$ 下的正交補，故 $R(A^TA)=R(A) ag{12}$

由(11)(12)知:

Lemma4: $A$ 和 $A^TA$ 具有相同的行空間和零空間。因此在 $A$ 的 $rowspace$ 和 $nullspace$ 中分別找兩組正交的基等價於在 $A^TA$ 的 $rowspace$ 和 $nullspace$ 中分別找兩組正交基。

設 $A$ 的秩為 $r$ ，則由(11)和秩-零度定理[1]可知： $rank(A^TA)=rank(A)=r ag{13}$ $A^TA$ 明顯是實對稱矩陣，根據本文2.1和2.2可知 $A^TA$ 的正交特徵向量 $v_1,dots,v_r$ 來自其行空間 $R(A^TA)$ , $v_{r+1},dots,v_n$ 來自其零空間 $N(A^TA)$ 。來自於零空間的 $v_{r+1},dots,v_n$ 均對應於特徵值 $0$ 。

Lemma4告訴我們 $A$ 和 $A^TA$ 具有相同的行空間和零空間，因此來自 $R(A^TA)$ 的 $v_1,dots,v_r$ 可作為 $R(A)$ 的一組正交基, $v_{r+1},dots,v_n$ 可作為 $N(A)$ 的一組正交基。因為 $R(A)$ $N(A)$ 互為正交補,所以 $v_1,dots,v_r,v_{r+1},dots,v_n$ 是 $mathbb{R^n}$ 的一組正交基。

類似地，我們可以發現

$C(A)$ 的正交基 $u_1,dots,u_r$ 和 $N(A^T)$ 的正交基 $u_{r+1},dots,u_m$ 是 $AA^T$ 的單位正交特徵向量。又因為 $C(A)$ 與 $N(A^T)$ 互為正交補，所以 ${u_1,dots,u_r}ot{u_{r+1},dots,u_m}$ ,即 $u_1,dots,u_r,u_{r+1},dots,u_m$ 是 $mathbb{R^m}$ 的一組正交基

到目前為止，我們找到了映射 $mathscr{A}$ 定義域 $mathbb{R^n}$ 內的正交基 $v_1,dots,v_r,v_{r+1},dots,v_n$ 和值域 $mathbb{R^m}$ 內的正交基。現在問題變成了：用我們找到的這兩正交基組基是否能使映射 $mathscr{A}:mathbb{R^n} longmapsto mathbb{R^m}$ 的數值化描述變為單純的伸縮變換 $Sigma=left[ egin{matrix} sigma_1&0&dots&0\ 0&sigma_2&dots&0\ vdots&vdots&ddots&sigma_r\ vdots&vdots&vdots&vdots end{matrix} ight]$ ？

答案是能！下面我們來證明它。

Theorem3：設有矩陣 $A_{m imes n}$ ，其對應的線性映射為 $mathscr{A}:mathbb{R^n} longmapsto mathbb{R^m}$ 。已知對稱陣 $(A^TA)_{n imes n}$ 的單位特徵向量 ${v_1,dots,v_r}cup { v_{r+1},dots,v_n}$ 可作為 $mathbb{R^n}$ 的一組正交基。
對稱陣 $(AA^T)_{m imes m}$ 的單位特徵向量 ${u_1,dots,u_r } cup {u_{r+1},dots,u_m}$ 可作為 $mathbb{R^m}$ 的一組正交基，試證明 $A v_i=k_iu_i,k_i in R$
Proof:因為 ${v_1,dots,v_r}$ 是 $(A^TA)_{n imes n}$ 的單位特徵向量，不妨設對應的特徵值為 $sigma_i^2$ $A^TA v_i=sigma^2_iv_i ag{d2}$
(d2)兩邊左乘 $v_i^T$ 得 $v_i^TA^TA v_i=sigma^2_iv_i^Tv_i ag{d3}$
因為 $v_i$ 是單位向量( $||v_i||=1$ ),故 $v_i^Tv_i=||v_i||^2=1$ ,所以有: $\ ||A v_i||^2=sigma^2_i Leftrightarrow ||A v_i||=sigma_i ag{d4}$
(d2)兩邊左乘 $A$ 得 $(AA^T)A v_i=sigma^2_iAv_i ag{d5}$
(d5)表明向量 $Av_i$ 就是方陣 $(AA^T)_{m imes m}$ 的特徵向量，其對應的特徵值為 $sigma^2$ 。將 $Av_i$ 單位化就是求 $Av_i /||Av_i||=Av_i/ sigma_i$ 。因此 $AA^T$ 的單位特徵向量 $u_i=Av_i/ sigma_i$ ，即有 $A v_i=sigma_iu_i$ ，其中 $sigma_i$ 是方陣 $(A^TA)_{n imes n}$ 特徵值 $sigma_i^2$ 的平方根。

我們證明了 $A v_i=sigma_iu_i ag{14}$

其中 $sigma_i$ 是方陣 $(A^TA)_{n imes n}$ 特徵值的平方根。根據這個式子我們可以寫出SVD的形式：

$Aleft[ egin{matrix}v_1dots v_rdots v_n end{matrix} ight]=[u_1dots u_rdots u_m] overbrace{ left. left[ egin{matrix} sigma_1&0&dots&0&dots\ 0&sigma_2&dots&0&dots\ vdots&vdots&ddots&sigma_r&\ vdots&vdots&vdots&vdots&ddots end{matrix} ight] ight } m行 }^{ ext{$n$列}}$

$AV=U Sigma$ ，又因為 $V$ 由方陣 $A^TA$ 的正交特徵向量組成，所以 $V^T=V^{-1}$ 。所以

$A=U Sigma V^{-1}=U Sigma V^T=u_1 sigma_1v_1^T+dots+u_r sigma_rv_r^T ag{*}$

除了 $sigma_1,dots,sigma_r$ 其他元素全為 $0$ 。式(*)右邊是 $r$ 個秩為 $1$ 的 $m imes n$ 矩陣 $u_isigma_iv_i^T$ 。如果把這些秩 $1$ 矩陣看作組成 $A$ 的成分，則 $sigma_i$ 代表了該秩 $1$ 矩陣這個成分佔 $A$ 的比重。

在圖片壓縮技術中應用SVD便可以找到圖像矩陣中佔比最大的成分。刪去佔比過大的成分，會使原圖片丟失較多信息，變得模糊，就如本文正文前兩張圖片展示的一樣。

附錄

[1]Rank-nullity theorem