廣義奇異值分解

線性代數中，廣義奇異值分解（GSVD）是基於奇異值（SVD）的兩種不同算法的統稱。其區別在於，一個是分解兩個矩陣（類似於高階或張量SVD），另一種使用施加於單矩陣SVD奇異向量上的約束。

版本1：雙矩陣分解

廣義奇異值分解（GSVD）是對矩陣對的矩陣分解，將奇異值分解推廣到兩個矩陣的情形。它由Van Loan ^[1]於1976年提出，後來由Paige與Saunders完善，^[2]也就是本節描述的版本。與SVD相對，GSVD可以同時分解具有相同列數的矩陣對。SVD、GSVD及SVD的其他一些推廣^[3][4][5]被廣泛用於研究線性系統在二次半範數方面的條件調節與正則化。下面設${\displaystyle \mathbb {F} =\mathbb {R} }$，或${\displaystyle \mathbb {F} =\mathbb {C} }$。

定義

${\displaystyle A_{1}\in \mathbb {F} ^{m_{1}\times n}}$與${\displaystyle A_{2}\in \mathbb {F} ^{m_{2}\times n}}$的廣義奇異值分解為$${\displaystyle {\begin{aligned}A_{1}&=U_{1}\Sigma _{1}[W^{*}D,0_{D}]Q^{*},\\A_{2}&=U_{2}\Sigma _{2}[W^{*}D,0_{D}]Q^{*},\end{aligned}}}$$，其中

• ${\displaystyle U_{1}\in \mathbb {F} ^{m_{1}\times m_{1}}}$為酉矩陣；
• ${\displaystyle U_{2}\in \mathbb {F} ^{m_{2}\times m_{2}}}$為酉矩陣；
• ${\displaystyle Q\in \mathbb {F} ^{n\times n}}$為酉矩陣；
• ${\displaystyle W\in \mathbb {F} ^{k\times k}}$為酉矩陣；
• ${\displaystyle D\in \mathbb {R} ^{k\times k}}$對角線元素為正實數，包含${\displaystyle C={\begin{bmatrix}A_{1}\\A_{2}\end{bmatrix}}}$的非零奇異值的降序排列，
• ${\displaystyle 0_{D}=0\in \mathbb {R} ^{k\times (n-k)}}$,
• ${\displaystyle \Sigma _{1}=\lceil I_{A},S_{1},0_{A}\rfloor \in \mathbb {R} ^{m_{1}\times k}}$是非負實數分塊對角陣，其中${\displaystyle S_{1}=\lceil \alpha _{r+1},\dots ,\alpha _{r+s}\rfloor }$，其中${\displaystyle 1>\alpha _{r+1}\geq \cdots \geq \alpha _{r+s}>0}$, ${\displaystyle I_{A}=I_{r}}$，且${\displaystyle 0_{A}=0\in \mathbb {R} ^{(m_{1}-r-s)\times (k-r-s)}}$；
• ${\displaystyle \Sigma _{2}=\lceil 0_{B},S_{2},I_{B}\rfloor \in \mathbb {R} ^{m_{2}\times k}}$是非負實數分塊對角陣，其中${\displaystyle S_{2}=\lceil \beta _{r+1},\dots ,\beta _{r+s}\rfloor }$，其中${\displaystyle 0<\beta _{r+1}\leq \cdots \leq \beta _{r+s}<1}$, ${\displaystyle I_{B}=I_{k-r-s}}$，且${\displaystyle 0_{B}=0\in \mathbb {R} ^{(m_{2}-k+r)\times r}}$；
• ${\displaystyle \Sigma _{1}^{*}\Sigma _{1}=\lceil \alpha _{1}^{2},\dots ,\alpha _{k}^{2}\rfloor }$,
• ${\displaystyle \Sigma _{2}^{*}\Sigma _{2}=\lceil \beta _{1}^{2},\dots ,\beta _{k}^{2}\rfloor }$,
• ${\displaystyle \Sigma _{1}^{*}\Sigma _{1}+\Sigma _{2}^{*}\Sigma _{2}=I_{k}}$,
• ${\displaystyle k={\textrm {rank}}(C)}$.

記${\displaystyle \alpha _{1}=\cdots =\alpha _{r}=1,\ \alpha _{r+s+1}=\cdots =\alpha _{k}=0,\ \beta _{1}=\cdots =\beta _{r}=0,\ \beta _{r+s+1}=\cdots =\beta _{k}=1}$。而${\displaystyle \Sigma _{1}}$是對角陣，${\displaystyle \Sigma _{2}}$不總是對角陣，因為前導矩形零矩陣；相反，${\displaystyle \Sigma _{2}}$是「副對角陣」。

變體

GSVD有許多變體，與這樣一個事實有關：${\displaystyle Q^{*}}$總可以左乘${\displaystyle EE^{*}=I<(E\in \mathbb {F} ^{n\times n})}$是任意酉矩陣。記

• ${\displaystyle X=([W^{*}D,0_{D}]Q^{*})^{*}}$
• ${\displaystyle X^{*}=[0,R]{\hat {Q}}^{*}}$，其中${\displaystyle R\in \mathbb {F} ^{k\times k}}$是上三角可逆陣；${\displaystyle {\hat {Q}}\in \mathbb {F} ^{n\times n}}$是酉矩陣。QR分解總可以得到這樣的矩陣。
• ${\displaystyle Y=W^{*}D}$，那麼${\displaystyle Y}$可逆。

下面是GSVD的一些變體：

• MATLAB（gsvd）：$${\displaystyle {\begin{aligned}A_{1}&=U_{1}\Sigma _{1}X^{*},\\A_{2}&=U_{2}\Sigma _{2}X^{*}.\end{aligned}}}$$
• LAPACK（LA_GGSVD）：$${\displaystyle {\begin{aligned}A_{1}&=U_{1}\Sigma _{1}[0,R]{\hat {Q}}^{*},\\A_{2}&=U_{2}\Sigma _{2}[0,R]{\hat {Q}}^{*}.\end{aligned}}}$$
• 簡化：$${\displaystyle {\begin{aligned}A_{1}&=U_{1}\Sigma _{1}[Y,0_{D}]Q^{*},\\A_{2}&=U_{2}\Sigma _{2}[Y,0_{D}]Q^{*}.\end{aligned}}}$$

廣義奇異值

${\displaystyle A_{1}}$與${\displaystyle A_{2}}$的廣義奇異值 是一對${\displaystyle (a,b)\in \mathbb {R} ^{2}}$使得

$${\displaystyle {\begin{aligned}\lim _{\delta \to 0}\det(b^{2}A_{1}^{*}A_{1}-a^{2}A_{2}^{*}A_{2}+\delta I_{n})/\det(\delta I_{n-k})&=0,\\a^{2}+b^{2}&=1,\\a,b&\geq 0.\end{aligned}}}$$我們有

• ${\displaystyle A_{i}A_{j}^{*}=U_{i}\Sigma _{i}YY^{*}\Sigma _{j}^{*}U_{j}^{*}}$
• ${\displaystyle A_{i}^{*}A_{j}=Q{\begin{bmatrix}Y^{*}\Sigma _{i}^{*}\Sigma _{j}Y&0\\0&0\end{bmatrix}}Q^{*}=Q_{1}Y^{*}\Sigma _{i}^{*}\Sigma _{j}YQ_{1}^{*}}$

根據這些性質，可以證明廣義奇異值正是成對的${\displaystyle (\alpha _{i},\beta _{i})}$。有$${\displaystyle {\begin{aligned}&\det(b^{2}A_{1}^{*}A_{1}-a^{2}A_{2}^{*}A_{2}+\delta I_{n})\\=&\det(b^{2}A_{1}^{*}A_{1}-a^{2}A_{2}^{*}A_{2}+\delta QQ^{*})\\=&\det \left(Q{\begin{bmatrix}Y^{*}(b^{2}\Sigma _{1}^{*}\Sigma _{1}-a^{2}\Sigma _{2}^{*}\Sigma _{2})Y+\delta I_{k}&0\\0&\delta I_{n-k}\end{bmatrix}}Q^{*}\right)\\=&\det(\delta I_{n-k})\det(Y^{*}(b^{2}\Sigma _{1}^{*}\Sigma _{1}-a^{2}\Sigma _{2}^{*}\Sigma _{2})Y+\delta I_{k}).\end{aligned}}}$$因此

${\displaystyle {\begin{aligned}{}&\lim _{\delta \to 0}\det(b^{2}A_{1}^{*}A_{1}-a^{2}A_{2}^{*}A_{2}+\delta I_{n})/\det(\delta I_{n-k})\\=&\lim _{\delta \to 0}\det(Y^{*}(b^{2}\Sigma _{1}^{*}\Sigma _{1}-a^{2}\Sigma _{2}^{*}\Sigma _{2})Y+\delta I_{k})\\=&\det(Y^{*}(b^{2}\Sigma _{1}^{*}\Sigma _{1}-a^{2}\Sigma _{2}^{*}\Sigma _{2})Y)\\=&|\det(Y)|^{2}\prod _{i=1}^{k}(b^{2}\alpha _{i}^{2}-a^{2}\beta _{i}^{2}).\end{aligned}}}$

對某個${\displaystyle i}$，當${\displaystyle a=\alpha _{i},\ b=\beta _{i}}$時，表達式恰為零。

在^[2]中，廣義奇異值被認為是求解${\displaystyle \det(b^{2}A_{1}^{*}A_{1}-a^{2}A_{2}^{*}A_{2})=0}$的奇異值。然而，這只有當${\displaystyle k=n}$時才成立，否則行列式對每對${\displaystyle (a,b)\in \mathbb {R} ^{2}}$都將是0；這可通過替換上面的${\displaystyle \delta =0}$得到。

廣義逆

對任意可逆陣${\displaystyle E\in \mathbb {F} ^{n\times n}}$，令${\displaystyle E^{+}=E^{-1}}$，對任意零矩陣${\displaystyle 0\in \mathbb {F} ^{m\times n}}$，令${\displaystyle 0^{+}=0^{*}}$，對任意分塊對角陣令${\displaystyle \left\lceil E_{1},E_{2}\right\rfloor ^{+}=\left\lceil E_{1}^{+},E_{2}^{+}\right\rfloor }$。定義$${\displaystyle A_{i}^{+}=Q{\begin{bmatrix}Y^{-1}\\0\end{bmatrix}}\Sigma _{i}^{+}U_{i}^{*}}$$可以證明這裡定義的${\displaystyle A_{i}^{+}}$是${\displaystyle A_{i}}$的廣義逆陣；特別是${\displaystyle A_{i}}$的${\displaystyle \{1,2,3\}}$逆。由於它一般不滿足${\displaystyle (A_{i}^{+}A_{i})^{*}=A_{i}^{+}A_{i}}$，所以不是摩爾-彭若斯廣義逆；否則可以得出，對任意所選矩陣都有${\displaystyle (AB)^{+}=B^{+}A^{+}}$，這隻對特定類型的矩陣成立。

設${\displaystyle Q={\begin{bmatrix}Q_{1}&Q_{2}\end{bmatrix}}}$，其中${\displaystyle Q_{1}\in \mathbb {F} ^{n\times k},\ Q_{2}\in \mathbb {F} ^{n\times (n-k)}}$。這個廣義逆具有如下性質：

• ${\displaystyle \Sigma _{1}^{+}=\lceil I_{A},S_{1}^{-1},0_{A}^{T}\rfloor }$
• ${\displaystyle \Sigma _{2}^{+}=\lceil 0_{B}^{T},S_{2}^{-1},I_{B}\rfloor }$
• ${\displaystyle \Sigma _{1}\Sigma _{1}^{+}=\lceil I,I,0\rfloor }$
• ${\displaystyle \Sigma _{2}\Sigma _{2}^{+}=\lceil 0,I,I\rfloor }$
• ${\displaystyle \Sigma _{1}\Sigma _{2}^{+}=\lceil 0,S_{1}S_{2}^{-1},0\rfloor }$
• ${\displaystyle \Sigma _{1}^{+}\Sigma _{2}=\lceil 0,S_{1}^{-1}S_{2},0\rfloor }$
• ${\displaystyle A_{i}A_{j}^{+}=U_{i}\Sigma _{i}\Sigma _{j}^{+}U_{j}^{*}}$
• ${\displaystyle A_{i}^{+}A_{j}=Q{\begin{bmatrix}Y^{-1}\Sigma _{i}^{+}\Sigma _{j}Y&0\\0&0\end{bmatrix}}Q^{*}=Q_{1}Y^{-1}\Sigma _{i}^{+}\Sigma _{j}YQ_{1}^{*}}$

商SVD

'${\displaystyle A_{1}}$與${\displaystyle A_{2}}$的'廣義奇異比是${\displaystyle \sigma _{i}=\alpha _{i}\beta _{i}^{+}}$。由以上性質，${\displaystyle A_{1}A_{2}^{+}=U_{1}\Sigma _{1}\Sigma _{2}^{+}U_{2}^{*}}$。注意${\displaystyle \Sigma _{1}\Sigma _{2}^{+}=\lceil 0,S_{1}S_{2}^{-1},0\rfloor }$是對角陣，忽略前導零矩陣，按降序包含着奇異比。若${\displaystyle A_{2}}$可逆，則${\displaystyle \Sigma _{1}\Sigma _{2}^{+}}$沒有前導零，廣義奇異比就是奇異值，${\displaystyle U_{1}}$與${\displaystyle U_{2}}$則是${\displaystyle A_{1}A_{2}^{+}=A_{1}A_{2}^{-1}}$的奇異向量矩陣。事實上計算${\displaystyle A_{1}A_{2}^{-1}}$的SVD是GSVD的動機之一，因為「形成${\displaystyle AB^{-1}}$並求SVD，當${\displaystyle B}$的方程解條件不佳時，可能產生不必要、較大的數值誤差」。^[2]因此有時也被稱為「商GSVD」，雖然這並不是使用GSVD的唯一原因。若${\displaystyle A_{2}}$不可逆，並放寬奇異值降序排列的要求，則${\displaystyle U_{1}\Sigma _{1}\Sigma _{2}^{+}U_{2}^{*}}$仍是${\displaystyle A_{1}A_{2}^{+}}$的SVD。或者，把前導零移到後面，也可以找到降序SVD：${\displaystyle U_{1}\Sigma _{1}\Sigma _{2}^{+}U_{2}^{*}=(U_{1}P_{1})P_{1}^{*}\Sigma _{1}\Sigma _{2}^{+}P_{2}(P_{2}^{*}U_{2}^{*})}$，其中${\displaystyle P_{1}}$與${\displaystyle P_{2}}$是適當的置換矩陣。由於秩等於非零奇異值的個數，所以${\displaystyle \mathrm {rank} (A_{1}A_{2}^{+})=s}$。

構造

令

• ${\displaystyle C=P\lceil D,0\rfloor Q^{*}}$為${\displaystyle C={\begin{bmatrix}A_{1}\\A_{2}\end{bmatrix}}}$的SVD，其中${\displaystyle P\in \mathbb {F} ^{(m_{1}+m_{2})\times (m_{1}\times m_{2})}}$是酉矩陣，${\displaystyle Q}$與${\displaystyle D}$如上所述；
• ${\displaystyle P=[P_{1},P_{2}]}$，其中${\displaystyle P_{1}\in \mathbb {F} ^{(m_{1}+m_{2})\times k}}$與${\displaystyle P_{2}\in \mathbb {F} ^{(m_{1}+m_{2})\times (n-k)}}$；
• ${\displaystyle P_{1}={\begin{bmatrix}P_{11}\\P_{21}\end{bmatrix}}}$，其中${\displaystyle P_{11}\in \mathbb {F} ^{m_{1}\times k}}$與${\displaystyle P_{21}\in \mathbb {F} ^{m_{2}\times k}}$；
• ${\displaystyle P_{11}=U_{1}\Sigma _{1}W^{*}}$通過${\displaystyle P_{11}}$的SVD得到，其中${\displaystyle U_{1}}$、${\displaystyle \Sigma _{1}}$與${\displaystyle W}$如上所述，
• ${\displaystyle P_{21}W=U_{2}\Sigma _{2}}$經過類似於QR分解的分解，其中${\displaystyle U_{2}}$與${\displaystyle \Sigma _{2}}$如上所述。

那麼，$${\displaystyle {\begin{aligned}C&=P\lceil D,0\rfloor Q^{*}\\{}&=[P_{1}D,0]Q^{*}\\{}&={\begin{bmatrix}U_{1}\Sigma _{1}W^{*}D&0\\U_{2}\Sigma _{2}W^{*}D&0\end{bmatrix}}Q^{*}\\{}&={\begin{bmatrix}U_{1}\Sigma _{1}[W^{*}D,0]Q^{*}\\U_{2}\Sigma _{2}[W^{*}D,0]Q^{*}\end{bmatrix}}.\end{aligned}}}$$還有$${\displaystyle {\begin{bmatrix}U_{1}^{*}&0\\0&U_{2}^{*}\end{bmatrix}}P_{1}W={\begin{bmatrix}\Sigma _{1}\\\Sigma _{2}\end{bmatrix}}.}$$因此$${\displaystyle \Sigma _{1}^{*}\Sigma _{1}+\Sigma _{2}^{*}\Sigma _{2}={\begin{bmatrix}\Sigma _{1}\\\Sigma _{2}\end{bmatrix}}^{*}{\begin{bmatrix}\Sigma _{1}\\\Sigma _{2}\end{bmatrix}}=W^{*}P_{1}^{*}{\begin{bmatrix}U_{1}&0\\0&U_{2}\end{bmatrix}}{\begin{bmatrix}U_{1}^{*}&0\\0&U_{2}^{*}\end{bmatrix}}P_{1}W=I.}$$由於${\displaystyle P_{1}}$的列歸一正交，${\displaystyle ||P_{1}||_{2}\leq 1}$，因此$${\displaystyle ||\Sigma _{1}||_{2}=||U_{1}^{*}P_{1}W||_{2}=||P_{1}||_{2}\leq 1.}$$對每個${\displaystyle x\in \mathbb {R} ^{k}}$，有${\displaystyle ||x||_{2}=1}$，使得$${\displaystyle ||P_{21}x||_{2}^{2}\leq ||P_{11}x||_{2}^{2}+||P_{21}x||_{2}^{2}=||P_{1}x||_{2}^{2}\leq 1.}$$因此${\displaystyle ||P_{21}||_{2}\leq 1}$；$${\displaystyle ||\Sigma _{2}||_{2}=||U_{2}^{*}P_{21}W||_{2}=||P_{21}||_{2}\leq 1.}$$

應用

張量GSVD是比較譜分解的一種，是SVD在多張量上的推廣，提出動機是同時識別其中的相似與不相似數據，並從任何數量和維度的任意數據類型中得到單一相干模型。

GSVD是一種比較譜分解，^[6]已成功應用於信號處理和數據科學，如基因組信號處理。^[7][8][9]

這些應用啟發了其他幾種比較譜分解，即高階GSVD（HO GSVD）^[10]與張量GSVD。^{[11] [12]}

當特徵函數以線性模型（即再生核希爾伯特空間）為參數時，它同樣適於估計線性運算的譜分解。^[13]

版本2：加權單矩陣分解

廣義奇異值分解（GSVD）的加權情形是一種有約束矩陣分解，約束施加在奇異向量上。^[14][15][16]這種GSVD是SVD的推廣。給定m×n實或複數矩陣M的SVD分解

${\displaystyle M=U\Sigma V^{*}\,}$

，其中

${\displaystyle U^{*}W_{u}U=V^{*}W_{v}V=I.}$

其中I是單位矩陣；${\displaystyle U}$與${\displaystyle V}$在約束條件下（${\displaystyle W_{u}}$；${\displaystyle W_{v}}$）是標準正交矩陣。另外，${\displaystyle W_{u}}$、${\displaystyle W_{v}}$是正定矩陣（通常是權的對角矩陣）。這種形式的GSVD是某些算法的核心，如廣義主成分分析和對應分析。

加權形式的GSVD之所以被稱為加權形式，是因為在正確取權時，可以推出許多算法（如多維標度與線性判別分析）。^[17]