广义奇异值分解

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

## 版本1：双矩阵分解

广义奇异值分解（GSVD）是对矩阵对的矩阵分解，将奇异值分解推广到两个矩阵的情形。它由Van Loan 于1976年提出，后来由Paige与Saunders完善，也就是本节描述的版本。与SVD相对，GSVD可以同时分解具有相同列数的矩阵对。SVD、GSVD及SVD的其他一些推广被广泛用于研究线性系统在二次半范数方面的条件调节与正则化。下面设$\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{align} A_1 & = U_1\Sigma_1 [ W^* D, 0_D] Q^*, \\ A_2 & = U_2\Sigma_2 [ W^* D, 0_D] Q^*, \end{align}$$，其中

- $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} \ge \cdots \ge \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} \le \cdots \le \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^*$总可以左乘$E E^* = 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{align} A_1 & = U_1\Sigma_1 [ Y, 0_D] Q^*, \\ A_2 & = U_2\Sigma_2 [ Y, 0_D] Q^*. \end{align}$$

### 广义奇异值

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

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

- $$A_i A_j^* = U_i \Sigma_i Y Y^* \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 Y Q_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 Q Q^*) \\ = & \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$时，表达式恰为零。

在中，广义奇异值被认为是求解$\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^T_B, 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 Y Q_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$的方程解条件不佳时，可能产生不必要、较大的数值误差”。因此有时也被称为“商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.$$

## 应用

<image>

GSVD是一种比较谱分解，已成功应用于信号处理和数据科学，如基因组信号处理。

这些应用启发了其他几种比较谱分解，即高阶GSVD（HO GSVD）与张量GSVD。

当特征函数以线性模型（即再生核希尔伯特空间）为参数时，它同样适于估计线性运算的谱分解。

## 版本2：加权单矩阵分解

广义奇异值分解（GSVD）的加权情形是一种有约束矩阵分解，约束施加在奇异向量上。这种GSVD是SVD的推广。给定m×n实或复数矩阵M的SVD分解

$$M = U\Sigma V^* \,$$

其中

$$U^* W_u U = V^* W_v V = I.$$

其中I是单位矩阵；$U$与$V$在约束条件下（$W_u$；$W_v$）是标准正交矩阵。另外，$W_u$、$W_v$是正定矩阵（通常是权的对角矩阵）。这种形式的GSVD是某些算法的核心，如广义主成分分析和对应分析。

加权形式的GSVD之所以被称为加权形式，是因为在正确取权时，可以推出许多算法（如多维标度与线性判别分析）。

## 阅读更多

- LAPACK manual