广义奇异值分解

线性代数中，广义奇异值分解（GSVD）是基于奇异值（SVD）的两种不同算法的统称。其区别在于，一个是分解两个矩阵（类似于高阶或张量SVD），另一种使用施加于单矩阵SVD奇异向量上的约束。

版本1：双矩阵分解

广义奇异值分解（GSVD）是对矩阵对的矩阵分解，将奇异值分解推广到两个矩阵的情形。它由Van Loan ^[1]于1976年提出，后来由Paige与Saunders完善，^[2]也就是本节描述的版本。与SVD相对，GSVD可以同时分解具有相同列数的矩阵对。SVD、GSVD及SVD的其他一些推广^[3]^[4]^[5]被广泛用于研究线性系统在二次半范数方面的条件调节与正则化。下面设 $\mathbb {F} =\mathbb {R}$ ，或 $\mathbb {F} =\mathbb {C}$ 。

定义

$A_{1}\in \mathbb {F} ^{m_{1}\times n}$ 与 $A_{2}\in \mathbb {F} ^{m_{2}\times n}$ 的广义奇异值分解为 ${\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}}$ ，其中

$U_{1}\in \mathbb {F} ^{m_{1}\times m_{1}}$ 为酉矩阵；
$U_{2}\in \mathbb {F} ^{m_{2}\times m_{2}}$ 为酉矩阵；
$Q\in \mathbb {F} ^{n\times n}$ 为酉矩阵；
$W\in \mathbb {F} ^{k\times k}$ 为酉矩阵；
$D\in \mathbb {R} ^{k\times k}$ 对角线元素为正实数，包含 $C={\begin{bmatrix}A_{1}\\A_{2}\end{bmatrix}}$ 的非零奇异值的降序排列，
$0_{D}=0\in \mathbb {R} ^{k\times (n-k)}$ ,
$\Sigma _{1}=\lceil I_{A},S_{1},0_{A}\rfloor \in \mathbb {R} ^{m_{1}\times k}$ 是非负实数分块对角阵，其中 $S_{1}=\lceil \alpha _{r+1},\dots ,\alpha _{r+s}\rfloor$ ，其中 $1>\alpha _{r+1}\geq \cdots \geq \alpha _{r+s}>0$ , $I_{A}=I_{r}$ ，且 $0_{A}=0\in \mathbb {R} ^{(m_{1}-r-s)\times (k-r-s)}$ ；
$\Sigma _{2}=\lceil 0_{B},S_{2},I_{B}\rfloor \in \mathbb {R} ^{m_{2}\times k}$ 是非负实数分块对角阵，其中 $S_{2}=\lceil \beta _{r+1},\dots ,\beta _{r+s}\rfloor$ ，其中 $0<\beta _{r+1}\leq \cdots \leq \beta _{r+s}<1$ , $I_{B}=I_{k-r-s}$ ，且 $0_{B}=0\in \mathbb {R} ^{(m_{2}-k+r)\times r}$ ；
$\Sigma _{1}^{*}\Sigma _{1}=\lceil \alpha _{1}^{2},\dots ,\alpha _{k}^{2}\rfloor$ ,
$\Sigma _{2}^{*}\Sigma _{2}=\lceil \beta _{1}^{2},\dots ,\beta _{k}^{2}\rfloor$ ,
$\Sigma _{1}^{*}\Sigma _{1}+\Sigma _{2}^{*}\Sigma _{2}=I_{k}$ ,
$k={\textrm {rank}}(C)$ .

记 $\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$ 。而 $\Sigma _{1}$ 是对角阵， $\Sigma _{2}$ 不总是对角阵，因为前导矩形零矩阵；相反， $\Sigma _{2}$ 是“副对角阵”。

变体

GSVD有许多变体，与这样一个事实有关： $Q^{*}$ 总可以左乘 $EE^{*}=I<(E\in \mathbb {F} ^{n\times n})$ 是任意酉矩阵。记

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

下面是GSVD的一些变体：

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

广义奇异值

$A_{1}$ 与 $A_{2}$ 的广义奇异值 是一对 $(a,b)\in \mathbb {R} ^{2}$ 使得

${\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}}$ 我们有

$A_{i}A_{j}^{*}=U_{i}\Sigma _{i}YY^{*}\Sigma _{j}^{*}U_{j}^{*}$
$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}^{*}$

根据这些性质，可以证明广义奇异值正是成对的 $(\alpha _{i},\beta _{i})$ 。有 ${\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}}$ 因此

{\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}}

对某个 $i$ ，当 $a=\alpha _{i},\ b=\beta _{i}$ 时，表达式恰为零。

在^[2]中，广义奇异值被认为是求解 $\det(b^{2}A_{1}^{*}A_{1}-a^{2}A_{2}^{*}A_{2})=0$ 的奇异值。然而，这只有当 $k=n$ 时才成立，否则行列式对每对 $(a,b)\in \mathbb {R} ^{2}$ 都将是0；这可通过替换上面的 $\delta =0$ 得到。

广义逆

对任意可逆阵 $E\in \mathbb {F} ^{n\times n}$ ，令 $E^{+}=E^{-1}$ ，对任意零矩阵 $0\in \mathbb {F} ^{m\times n}$ ，令 $0^{+}=0^{*}$ ，对任意分块对角阵令 $\left\lceil E_{1},E_{2}\right\rfloor ^{+}=\left\lceil E_{1}^{+},E_{2}^{+}\right\rfloor$ 。定义 $A_{i}^{+}=Q{\begin{bmatrix}Y^{-1}\\0\end{bmatrix}}\Sigma _{i}^{+}U_{i}^{*}$ 可以证明这里定义的 $A_{i}^{+}$ 是 $A_{i}$ 的广义逆阵；特别是 $A_{i}$ 的 $\{1,2,3\}$ 逆。由于它一般不满足 $(A_{i}^{+}A_{i})^{*}=A_{i}^{+}A_{i}$ ，所以不是摩尔-彭若斯广义逆；否则可以得出，对任意所选矩阵都有 $(AB)^{+}=B^{+}A^{+}$ ，这只对特定类型的矩阵成立。

设 $Q={\begin{bmatrix}Q_{1}&Q_{2}\end{bmatrix}}$ ，其中 $Q_{1}\in \mathbb {F} ^{n\times k},\ Q_{2}\in \mathbb {F} ^{n\times (n-k)}$ 。这个广义逆具有如下性质：

$\Sigma _{1}^{+}=\lceil I_{A},S_{1}^{-1},0_{A}^{T}\rfloor$
$\Sigma _{2}^{+}=\lceil 0_{B}^{T},S_{2}^{-1},I_{B}\rfloor$
$\Sigma _{1}\Sigma _{1}^{+}=\lceil I,I,0\rfloor$
$\Sigma _{2}\Sigma _{2}^{+}=\lceil 0,I,I\rfloor$
$\Sigma _{1}\Sigma _{2}^{+}=\lceil 0,S_{1}S_{2}^{-1},0\rfloor$
$\Sigma _{1}^{+}\Sigma _{2}=\lceil 0,S_{1}^{-1}S_{2},0\rfloor$
$A_{i}A_{j}^{+}=U_{i}\Sigma _{i}\Sigma _{j}^{+}U_{j}^{*}$
$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

' $A_{1}$ 与 $A_{2}$ 的'广义奇异比是 $\sigma _{i}=\alpha _{i}\beta _{i}^{+}$ 。由以上性质， $A_{1}A_{2}^{+}=U_{1}\Sigma _{1}\Sigma _{2}^{+}U_{2}^{*}$ 。注意 $\Sigma _{1}\Sigma _{2}^{+}=\lceil 0,S_{1}S_{2}^{-1},0\rfloor$ 是对角阵，忽略前导零矩阵，按降序包含着奇异比。若 $A_{2}$ 可逆，则 $\Sigma _{1}\Sigma _{2}^{+}$ 没有前导零，广义奇异比就是奇异值， $U_{1}$ 与 $U_{2}$ 则是 $A_{1}A_{2}^{+}=A_{1}A_{2}^{-1}$ 的奇异向量矩阵。事实上计算 $A_{1}A_{2}^{-1}$ 的SVD是GSVD的动机之一，因为“形成 $AB^{-1}$ 并求SVD，当 $B$ 的方程解条件不佳时，可能产生不必要、较大的数值误差”。^[2]因此有时也被称为“商GSVD”，虽然这并不是使用GSVD的唯一原因。若 $A_{2}$ 不可逆，并放宽奇异值降序排列的要求，则 $U_{1}\Sigma _{1}\Sigma _{2}^{+}U_{2}^{*}$ 仍是 $A_{1}A_{2}^{+}$ 的SVD。或者，把前导零移到后面，也可以找到降序SVD： $U_{1}\Sigma _{1}\Sigma _{2}^{+}U_{2}^{*}=(U_{1}P_{1})P_{1}^{*}\Sigma _{1}\Sigma _{2}^{+}P_{2}(P_{2}^{*}U_{2}^{*})$ ，其中 $P_{1}$ 与 $P_{2}$ 是适当的置换矩阵。由于秩等于非零奇异值的个数，所以 $\mathrm {rank} (A_{1}A_{2}^{+})=s$ 。

构造

令

$C=P\lceil D,0\rfloor Q^{*}$ 为 $C={\begin{bmatrix}A_{1}\\A_{2}\end{bmatrix}}$ 的SVD，其中 $P\in \mathbb {F} ^{(m_{1}+m_{2})\times (m_{1}\times m_{2})}$ 是酉矩阵， $Q$ 与 $D$ 如上所述；
$P=[P_{1},P_{2}]$ ，其中 $P_{1}\in \mathbb {F} ^{(m_{1}+m_{2})\times k}$ 与 $P_{2}\in \mathbb {F} ^{(m_{1}+m_{2})\times (n-k)}$ ；
$P_{1}={\begin{bmatrix}P_{11}\\P_{21}\end{bmatrix}}$ ，其中 $P_{11}\in \mathbb {F} ^{m_{1}\times k}$ 与 $P_{21}\in \mathbb {F} ^{m_{2}\times k}$ ；
$P_{11}=U_{1}\Sigma _{1}W^{*}$ 通过 $P_{11}$ 的SVD得到，其中 $U_{1}$ 、 $\Sigma _{1}$ 与 $W$ 如上所述，
$P_{21}W=U_{2}\Sigma _{2}$ 经过类似于QR分解的分解，其中 $U_{2}$ 与 $\Sigma _{2}$ 如上所述。

那么， ${\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}}$ 还有 ${\begin{bmatrix}U_{1}^{*}&0\\0&U_{2}^{*}\end{bmatrix}}P_{1}W={\begin{bmatrix}\Sigma _{1}\\\Sigma _{2}\end{bmatrix}}.$ 因此 $\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.$ 由于 $P_{1}$ 的列归一正交， $||P_{1}||_{2}\leq 1$ ，因此 $||\Sigma _{1}||_{2}=||U_{1}^{*}P_{1}W||_{2}=||P_{1}||_{2}\leq 1.$ 对每个 $x\in \mathbb {R} ^{k}$ ，有 $||x||_{2}=1$ ，使得 $||P_{21}x||_{2}^{2}\leq ||P_{11}x||_{2}^{2}+||P_{21}x||_{2}^{2}=||P_{1}x||_{2}^{2}\leq 1.$ 因此 $||P_{21}||_{2}\leq 1$ ； $||\Sigma _{2}||_{2}=||U_{2}^{*}P_{21}W||_{2}=||P_{21}||_{2}\leq 1.$