带线性约束的 QR 与 SVD 分解

带线性约束的 QR 分解

考虑矩阵 $A \in \mathbb{R}^{m \times n}$ ，MATLAB 提供的 QR 分解包括两种形式：完整的 QR 分解和 economy QR 分解。后者是在 $A$ 的行数大于列数的情况下进行尺寸精简，不会造成任何精度损失。（如果行数不大于列数，那么 economy QR 分解退化为完整的 QR 分解）

例如完整的 QR 分解形如

Copy LaTeX

其中 $Q \in \mathbb{R}^{m \times m}$ 为正交方阵， $R \in \mathbb{R}^{m \times n}$ 是上三角矩阵。如果 $m > n$ ，那么

Copy LaTeX

其中 $R_1 \in \mathbb{R}^{n \times n}$ 是上三角方阵。这同时表明 $Q$ 的后 $m - n$ 列是没有必要进行计算和存储的。

Copy LaTeX

其中 $Q_1 = Q(:,1:n) \in \mathbb{R}^{m \times n}$ 是 $Q$ 的前 $n$ 列。

如果 $A\in \mathbb{R}^{m \times n}$ 满足线性约束

Copy LaTeX

其中 $C \in \mathbb{R}^{m \times k}$ 列满秩（即 $k$ 个线性无关的约束），此时自然有

Copy LaTeX

也就是说 $A$ 的列向量张成的空间维数 $r = \operatorname{rank}(A)$ 不可能超过 $m-k$ 。那么：

在 $m \le n$ 时，完整的 QR 分解 $A = Q R$ 不可能保证 $Q \in \mathbb{R}^{m \times m}$ 满足线性约束 $C^\top Q = 0$ ，因为根本找不到一套完整的 $\mathbb{R}^m$ 正交基满足线性约束。
在 $m > n$ 时，economy QR 分解 $A = Q_1 R_1$ 在 $A$ 列满秩，即 $r=n\le m-k$ 时自动保证 $C^\top Q_1=0$ 。此时 $Q_1$ 与 $A$ 张成同一个 $n$ 维子空间，包含于约束子空间 $\ker(C^\top)$ ；只有 $n=m-k$ 时才张成整个约束子空间。秩亏时，未经约束的正交补全不保证满足约束。

在 $m > n$ 时，如果 $r < n \le m-k$ ，是否可以加上一些修改以保证线性约束满足？从子空间的角度理解，满足线性约束的子空间维度为 $m-k$ ，但是此时 $\operatorname{span}(A)$ 只张成了其中的 $r$ 维子空间，但是 $Q_1$ 需要选择一个 $n$ 维子空间，剩下的 $n-r$ 维子空间的基在原始的 QR 分解算法中是任取的，但是我们现在要限制它仍然在线性约束子空间中。记满足线性约束的子空间的一组单位正交基为 $Z \in \mathbb{R}^{m \times (m-k)}$ ，那么

Copy LaTeX

由于 $A$ 满足约束，显然有

Copy LaTeX

如果对 $Z^\top A \in \mathbb{R}^{(m-k)\times n}$ 进行 economy QR 分解（此时仍然有 $m-k \ge n$ ）

Copy LaTeX

其中 $\widetilde{Q}_1 \in \mathbb{R}^{(m-k)\times n}$ ，那么取 $Q_1 = Z \widetilde{Q}_1 \in \mathbb{R}^{m \times n}$ 就可以得到

Copy LaTeX

并且保证 $Q_1$ 满足线性约束

Copy LaTeX

需要说明的是，这里的整个算法流程只要求 $n \le m-k$ ，对于 $r = n$ 和 $r < n$ 的情况都可以进行处理。

在实际的数值求解中，构造一个完整的 $Z \in \mathbb{R}^{m \times (m-k)}$ 并不容易，我们考虑更典型的情况： $k=1$ 只有一个线性约束

Copy LaTeX

其中 $c \in \mathbb{R}^{m}$ 。不妨假设 $c$ 是单位化的，并且要求 $c \neq e_1 = (1,0,\dots,0)^\top \in \mathbb{R}^m$ ，构造 Householder 矩阵

Copy LaTeX

其中取 $v = c - e_1 \in \mathbb{R}^{m}$ ，显然在 $v$ 不是零向量时总是有 $\det(H) = -1$ ，因此 $H$ 是满秩的，由于

Copy LaTeX

那么可以取

Copy LaTeX

以保证 $Z$ 列满秩和 $c^\top Z = 0$ 。可以计算

Copy LaTeX

对于 $Z^\top A$ 的 QR 分解结果

Copy LaTeX

最后恢复 $Q_1$

Copy LaTeX

带线性约束的 SVD 分解

考虑矩阵 $A \in \mathbb{R}^{m \times n}$ ，MATLAB 提供的 SVD 分解包括两种形式：完整的 SVD 分解和 economy SVD 分解。后者是在 $A$ 非方阵的情况下进行尺寸精简，不会造成任何精度损失。（如果行数等于列数，那么 economy SVD 分解退化为完整的 SVD 分解）

例如完整的 SVD 分解形如

Copy LaTeX

其中 $U \in \mathbb{R}^{m \times m}$ 和 $V \in \mathbb{R}^{n \times n}$ 为完整的正交方阵， $S \in \mathbb{R}^{m \times n}$ 是对角矩阵。如果 $m > n$ ，那么

Copy LaTeX

其中 $S_1 \in \mathbb{R}^{n \times n}$ 是对角方阵。这同时表明 $U$ 的后 $m - n$ 列是没有必要进行计算和存储的。

Copy LaTeX

其中 $U_1 = U(:,1:n) \in \mathbb{R}^{m \times n}$ 是 $U$ 的前 $n$ 列。如果 $m < n$ ，那么

Copy LaTeX

其中 $S_1 \in \mathbb{R}^{m \times m}$ 是对角方阵。这同时表明 $V$ 的后 $n - m$ 列是没有必要进行计算和存储的。

Copy LaTeX

其中 $V_1 = V(:,1:m) \in \mathbb{R}^{n \times m}$ 是 $V$ 的前 $m$ 列。

如果 $A\in \mathbb{R}^{m \times n}$ 满足线性约束

Copy LaTeX

其中 $C \in \mathbb{R}^{n \times k}$ 列满秩（即 $k$ 个线性无关的约束），此时自然有

Copy LaTeX

也就是说 $A$ 的行向量张成的空间维数 $r = \operatorname{rank}(A)$ 不可能超过 $n-k$ 。那么：

在 $m \ge n$ 时，economy SVD 分解 $A = U_1 S_1 V^\top$ 不可能保证 $V \in \mathbb{R}^{n \times n}$ 满足线性约束 $V^\top C = 0$ ，因为根本找不到一套完整的 $\mathbb{R}^n$ 正交基满足线性约束。
在 $m < n$ 时，economy SVD 分解 $A = U S_1 V_1^\top$ 在 $A$ 行满秩，即 $r=m\le n-k$ 时自动保证 $V_1^\top C=0$ 。此时 $V_1$ 的列空间等于 $A$ 的行空间，是约束子空间 $\ker(C^\top)$ 中的一个 $m$ 维子空间；只有 $m=n-k$ 时才张成整个约束子空间。秩亏时，未经约束的正交补全不保证满足约束。

在 $m < n$ 时，如果 $r < m \le n-k$ ，是否可以加上一些修改以保证线性约束满足？从子空间的角度理解，满足线性约束的子空间维度为 $n-k$ ，但是此时 $\operatorname{span}(A^\top)$ 只张成了其中的 $r$ 维子空间，但是 $V_1$ 需要选择一个 $m$ 维子空间，剩下的 $m-r$ 维子空间的基在原始的 SVD 分解算法中是任取的，但是我们现在要限制它仍然在线性约束子空间中。记满足线性约束的子空间的一组单位正交基为 $Z \in \mathbb{R}^{(n-k) \times n}$ ，那么

Copy LaTeX

由于 $A$ 满足约束，显然有

Copy LaTeX

如果对 $A Z^\top \in \mathbb{R}^{m \times (n-k)}$ 进行 economy SVD 分解（此时仍然有 $m \le n-k$ ）

Copy LaTeX

其中 $\widetilde{V}_1 \in \mathbb{R}^{(n-k)\times m}$ ，那么取 $V_1 = Z^\top \widetilde{V}_1 \in \mathbb{R}^{n \times m}$ 就可以得到

Copy LaTeX

并且保证 $V_1$ 满足线性约束

Copy LaTeX

与 QR 分解不同，我们通常对 SVD 分解伴随低秩截断操作，此时和标准的 economy SVD 分解不同，我们不需要受限于 $m \le n - k$ 的情况，可以在更一般的情况下考虑：对 $A \in \mathbb{R}^{m \times n}$ ，假设满足线性约束

Copy LaTeX

其中 $C \in \mathbb{R}^{n \times k}$ 列满秩（即 $k$ 个线性无关的约束），我们要求一个低秩近似

Copy LaTeX

其中 $U_r \in \mathbb{R}^{m \times r}$ 和 $V_r \in \mathbb{R}^{n \times r}$ 满足列向量单位正交， $S_r \in \mathbb{R}^{r \times r}$ 是对角方阵。要求 $V_r$ 满足线性约束

Copy LaTeX

这必然要求 $r \le n-k$ 。记满足线性约束的子空间的一组单位正交基为 $Z \in \mathbb{R}^{(n-k) \times n}$ ，那么

Copy LaTeX

由于 $A$ 满足约束，显然有

Copy LaTeX

如果对 $A Z^\top \in \mathbb{R}^{m \times (n-k)}$ 进行截断 SVD 分解（这里要求 $r \le \min(m,n-k)$ ）

Copy LaTeX

其中 $\widetilde{V}_r \in \mathbb{R}^{(n-k)\times r}$ ，那么取 $V_r = Z^\top \widetilde{V}_r \in \mathbb{R}^{n \times r}$ 就可以得到

Copy LaTeX

并且保证 $V_r$ 满足

Copy LaTeX

对于截断 SVD 分解，整个流程只要求 $r \le \min(m,n-k)$ 。

Remark

在 $k=1$ 时的具体数值实现与前面 QR 分解的做法相同，这里不再重复。