奇異值分解推導及相關知識補充

奇異值分解（SVD）推導及相關數學知識補充

• 相關數學知識補充
• • 矩陣的秩
  • 正交矩陣（orthogonal matrix）
• SVD推導的相關引理
• • 引理1
  • 引理2
  • 引理3
  • 引理4
• SVD推導
• 參考資料

相關數學知識補充

矩陣的秩

定義

矩陣A中不為零的子式的最高階數，稱為矩陣A的秩，記作r(A)。零矩陣的秩為0。

性質

1. 秩是一個正整數或0。
2. 秩等于或小于矩陣的行數和列數。秩等于或小于矩陣的行數和列數。
3. 當n×n矩陣A的秩等于n時，則稱A是非奇異矩陣，或稱A滿秩。
4. 若r(Am×n)<min{m,n}，則稱A是秩虧缺的。
5. 若r(Am×n)=m（<n）,則稱矩陣A具有滿行秩。
6. 若r(Am×n)=n（<m）,則稱矩陣A具有滿列秩。
7. 任何矩陣A左乘滿列秩矩陣或者右乘滿行秩矩陣後，矩陣A的秩保持不變。

意義

「秩」是矩陣中所有行向量中極大線性代無關組的元素個數。

「秩」是圖像經過矩陣變換之後的空間次元。

正交矩陣（orthogonal matrix）

定義

如果AAT = E或ATA = E，則n階實矩陣A稱為正交矩陣。

性質

若A是正交矩陣，則滿足：

1. AT，A-1與A*也是正交矩陣（其中 A* 是 A的共轭轉置。）；
2. A的各行各列是機關向量且兩兩正交；
3. (Ax,Ay)=(x,y) 其中x,y∈R；
4. AT = A-1；
5. 正交矩陣相似于對角矩陣。

SVD推導的相關引理

引理1

内容：假設A ϵ \epsilon ϵ R m × n ^{m\times n} m×n, 則 A T A 與 A A T A^T A與A A^T ATA與AAT的特征值 （eigenvalue）非負。

證明：

假設 λ \lambda λ 為AT A的特征值，x是它對應的特征向量，即

A T A x = λ x A^T Ax=\lambda x ATAx=λx

由于 A T A A^T A ATA是 對稱的，故 λ \lambda λ 是一個實數，是以我們有：

0 ≦ ( A x , A x ) = ( A x ) T ( A x ) = x T A T A x = x T λ x = λ x T x 0\leqq(Ax, Ax)=(Ax)^T(Ax)=x^TA^TAx=x^T\lambda x=\lambda x^Tx 0≦(Ax,Ax)=(Ax)T(Ax)=xTATAx=xTλx=λxTx

因為xTx > 0，是以我們可以得到 λ ≧ 0 \lambda \geqq 0 λ≧0 。

同理，我們可以知道 A A T A A^T AAT的特征值也是非負的。

引理2

内容：假設A ϵ \epsilon ϵ R m × n ^{m\times n} m×n, 則我們有r(A) = r(ATA) = r(AAT)。

證明：

要證明r(A) = r(ATA) = r(AAT)，相當于證明Ax=0和ATAx=0有相同的解。

Ax=0 ⇒ \Rightarrow ⇒ ATAx=0

ATAx=0 ⇒ \Rightarrow ⇒ xTATAx=0 ⇒ \Rightarrow ⇒ (Ax)TAx=0 ⇒ \Rightarrow ⇒ Ax=0

由此，可以得到Ax=0 ⇔ \Leftrightarrow ⇔ ATAx=0

Ax=0和ATAx=0有相同的解，故A與ATA核相等，是以秩相等可證。

引理3

内容：假設A ϵ \epsilon ϵ R m × n ^{m\times n} m×n, ATA與AAT有相同的特征值。

證明：

假設 λ \lambda λ 為AT A的特征值，x是它對應的特征向量，即

A T A x = λ x A^T Ax=\lambda x ATAx=λx

則

A T A x = λ x ⇒ A A T A x = λ A x ⇒ A A T y = λ y A^T Ax=\lambda x \Rightarrow AA^T Ax=\lambda Ax \Rightarrow AA^T y=\lambda y ATAx=λx⇒AATAx=λAx⇒AATy=λy

故可證得ATA與AAT有相同的 λ \lambda λ。

引理4

内容：如果兩個矩陣是彼此正交等價，那麼它們的奇異值相同。

證明：

假設A ,B ϵ \epsilon ϵ R m × n ^{m\times n} m×n， 彼此正交等價，則存在正交矩陣U ϵ \epsilon ϵ R m × m ^{m\times m} m×m, V ϵ \epsilon ϵ R n × n ^{n\times n} n×n, s.t. A=UBV.

若A,B彼此正交相似，則存在正交矩陣P，使得 P-1BP=A

ATA = (UBV)TUBV = VTBTUTUBV = VTBTBV = V-1BTBV

故可得到 ATA 與BTB彼此正交相似，是以它們有相同的 λ \lambda λ；

奇異值 σ \sigma σ = λ \sqrt \lambda λ

​, 故兩者的奇異值相同。

SVD推導

A = U Σ \Sigma ΣVT

證明：

∵ \because ∵ ATA為對稱矩陣（證：(ATA)T=AT(AT)T=ATA)

（對稱矩陣性質：若A為對稱矩陣，必存在正交矩陣，将其化為對角矩陣，且對角矩陣的對角元素即為特征值）

∴ \therefore ∴ ATA = X λ \lambda λX-1

其 中 λ = ( λ 1 λ 2 ⋱ λ n ) 其中\lambda= \begin{pmatrix} \lambda_1 &amp; \\ &amp; \lambda_2&amp; \\ &amp; &amp; \ddots &amp; \\ &amp; &amp; &amp; \lambda_n \\ \end{pmatrix} 其中λ=⎝⎜⎜⎛​λ1​​λ2​​⋱​λn​​⎠⎟⎟⎞​

X-1ATAX = λ \lambda λ

用V來替換X， 得到 V-1ATAV = λ \lambda λ

∵ \because ∵矩陣V正交 ∴ \therefore ∴V-1=VT

故 VTATAX = λ \lambda λ = ( Δ 2 0 0 0 ) \begin{pmatrix} \Delta^2&amp;0 \\0&amp;0\\ \end{pmatrix} (Δ20​00​)

将V拆成V1和V2，其中V1 ϵ \epsilon ϵ R n × r ^{n\times r} n×r，V2 ϵ \epsilon ϵ R n × n − r ^{n\times n-r} n×n−r

則 ( V 1 V 2 ) \begin{pmatrix} V_1 \\V_2 \\ \end{pmatrix} (V1​V2​​)(ATA)(V_1,V_2) = ( V 1 T A T A V 2 T A T A ) \begin{pmatrix} V_1^TA^TA\\V_2^TA^TA \\ \end{pmatrix} (V1T​ATAV2T​ATA​)(V_1,V_2) = ( V 1 T A T A V 1 V 1 T A T A V 2 V 2 T A T A V 1 V 2 T A T A V 2 ) \begin{pmatrix} V_1^TA^TAV_1&amp;V_1^TA^TAV_2\\V_2^TA^TA V_1&amp;V_2^TA^TA V_2\\ \end{pmatrix} (V1T​ATAV1​V2T​ATAV1​​V1T​ATAV2​V2T​ATAV2​​)= ( Δ 2 0 0 0 ) \begin{pmatrix} \Delta^2&amp;0 \\0&amp;0\\ \end{pmatrix} (Δ20​00​)

∴ \therefore ∴ V 2 T A T A V 1 = 0 V_2^TA^TA V_1=0 V2T​ATAV1​=0 ⇒ \Rightarrow ⇒ (AV2)TAV2=0 ⇒ \Rightarrow ⇒AV2=0

Δ 2 = V 1 T A T A V 1 = ( A V 1 ) T A V 1 \Delta^2 = V_1^TA^TAV_1 = (AV_1)^TAV_1 Δ2=V1T​ATAV1​=(AV1​)TAV1​

設U1 ϵ \epsilon ϵ R n × r ^{n\times r} n×r ， U1 = AV1 Δ \Delta Δ-1

U 1 T U 1 = ( Δ − 1 ) T V 1 T A T A V 1 Δ − 1 = Δ − 1 Δ 2 Δ − 1 = E r U_1 ^TU_1=(\Delta^{-1})^TV_1^TA^T AV_1 \Delta^{-1} = \Delta^{-1}\Delta^2\Delta^{-1} = E^r U1T​U1​=(Δ−1)TV1T​ATAV1​Δ−1=Δ−1Δ2Δ−1=Er

這說明 U 1 U_1 U1​各列為兩兩正交的機關向量（自身與自身内積為1）

同理，U也可以寫成U = (U1,U2)

UTAV = ( U 1 T U 2 T ) A ( V 1 , V 2 ) \begin{pmatrix} U_1^T\\U_2^T \\ \end{pmatrix}A(V_1,V_2) (U1T​U2T​​)A(V1​,V2​) = ( U 1 T A V 1 U 1 T A V 2 U 2 T A V 1 U 2 T A V 2 ) \begin{pmatrix} U_1^TAV_1&amp;U_1^TAV_2\\U_2^TAV_1&amp;U_2^TAV_2 \\ \end{pmatrix} (U1T​AV1​U2T​AV1​​U1T​AV2​U2T​AV2​​) = ( U 1 T U Δ U 1 T ( A V 2 ) U 2 T U Δ U 2 T ( A V 2 ) ) \begin{pmatrix} U_1^TU\Delta&amp;U_1^T(AV_2)\\U_2^TU\Delta&amp;U_2^T(AV_2) \\ \end{pmatrix} (U1T​UΔU2T​UΔ​U1T​(AV2​)U2T​(AV2​)​) = ( Δ 0 0 0 ) \begin{pmatrix} \Delta&amp;0 \\0&amp;0\\ \end{pmatrix} (Δ0​00​)

是以，可以得到：

A = U U T A V V T = U ( Δ 0 0 0 ) V T A = UU^TAVV^T = U\begin{pmatrix} \Delta&amp;0 \\0&amp;0\\ \end{pmatrix}V^T A=UUTAVVT=U(Δ0​00​)VT

故SVD得證。

參考資料

實對稱矩陣的特征值和特征向量