An NPDo Approach for Principal Joint SVD-type Block Diagonalization

技术摘要：一种用于主联合 SVD 型块对角化的 NPDo 方法

问题陈述
本文解决了**主联合 SVD 型块对角化（pjbsvd）**问题。给定一组 $N$ 个矩阵 $B_\ell \in \mathbb{C}^{n_1 \times n_2}$，目标是寻找一对维度分别为 $n_1 \times k$ 和 $n_2 \times k$ 的正交矩阵 $(U, V)$（其中 $1 \le k \le \min\{n_1, n_2\}$），使得变换后的矩阵 $U^H B_\ell V$ 同时且最优地接近预定的块对角结构。

与标准联合 SVD（其中 $k = \min\{n_1, n_2\}$ 且块大小为 $1 \times 1$）不同，pjbsvd 允许 $k < \min\{n_1, n_2\}$，使其适用于仅关注主导分量的大规模问题。此外，块结构由 $k$ 的划分 $\tau_k = (k_1, \dots, k_t)$ 定义。具体目标是最大化所有矩阵中块对角部分的集体“质量”（Frobenius 范数平方）：
$$\max_{(U,V) \in \text{St}(k,n_1) \times \text{St}(k,n_2)} f(U, V) := \sum_{\ell=1}^N \| \text{BDiag}_{\tau_k}(U^H B_\ell V) \|_F^2$$
其中 $\text{St}(k, n)$ 表示复 Stiefel 流形。特例包括主联合 SVD（pjsvd）（所有 $k_i=1$）和主联合压缩（$t=1$）。

方法论
作者提出了一种基于**NPDo（具有正交极因子依赖性的非线性极分解）**的数值方法。该方法依赖于以下理论和算法框架：

1. KKT 条件与极分解：目标函数的最优性条件导出了两个耦合的极分解方程，涉及依赖于正交因子 $U$ 和 $V$ 的矩阵值函数 $H_1(U, V)$ 和 $H_2(U, V)$。
2. 交替 SCF（ASCF）迭代：核心算法（算法 3.1）通过交替自洽场（SCF）迭代求解这些耦合方程。在每一步中，算法通过计算梯度矩阵 $H_1$ 和 $H_2$ 的正交极因子来更新 $U$ 和 $V$。
   • 雅可比型更新：基于上一次迭代的值同时更新 $U$ 和 $V$。
   • 高斯 - 赛德尔型更新：先更新 $U$，然后在同一迭代中使用新的 $U$ 更新 $V$。
3. 加速（LOCG）：为了提高效率，作者引入了**局部最优共轭梯度（LOCG）**加速（算法 3.2）。这涉及构建由当前迭代点和残差梯度张成的约化子空间，在该子空间内求解问题的较小版本，并将解投影回去。
4. 复数与实数：公式是针对复 Stiefel 流形提出的，但指出可直接应用于实矩阵而无需变换。

主要贡献

• 公式化：本文形式化了部分/主联合 SVD 型块对角化问题，将现有的联合 SVD 概念扩展到输出维度 $k$ 小于输入维度且块可以大于 $1 \times 1$ 的情况。
• 算法开发：引入了针对此特定问题定制的 NPDo 方法，利用交替 SCF 迭代。作者提供了两种变体（雅可比和高斯 - 赛德尔）以及加速的 LOCG 版本。
• 收敛性分析：
  • 高斯 - 赛德尔：论文证明了高斯 - 赛德尔型 ASCF 迭代全局收敛于驻点，且目标函数在每一步单调递增。
  • 雅可比：虽然目标函数在雅可比情况下不能保证单调递增，但作者分析了中间对序列的收敛性，并证明了在特定条件下收敛于驻点。
  • 扩展：收敛性理论被证明适用于满足特定连续性和梯度性质的 Stiefel 流形上更一般的优化问题。
• 数值效率：所提出的方法旨在高效处理大规模矩阵，避免了将复数问题转换为实数问题的需求，这是一般用途流形优化包中的常见限制。

结果
在具有不同噪声水平（$\eta$）和维度（$n$ 高达 1000）的随机生成数据集上进行了数值实验。

• 有效性：结果矩阵 $U^H B_\ell V$ 的热图证实，该算法成功地将矩阵质量集中到预定的块对角结构中。
• 收敛性：所有方法均实现了低于 $10^{-8}$ 的 KKT 残差。加速版本（accNPDo）始终产生最小的残差。
• 性能：
  • LOCG 加速版本（accNPDo）显著快于标准 NPDo，特别是在问题规模较大时。
  • 对于 pjsvd 的特定情况（块大小 $1 \times 1$），高斯 - 赛德尔变体明显快于雅可比变体。然而，对于一般块对角化（pjbsvd），高斯 - 赛德尔和雅可比之间的性能差异不太明显。
  • 目标值根据方法的不同收敛到不同的驻点，表明了问题的非凸性质。

意义与主张
作者将这项工作定位为一种专门的数值线性代数方法，而非通用优化技术。他们声称，通过利用问题的特定结构（Stiefel 流形上耦合迹的和），他们的 NPDo 方法提供了：

1. 简单性与可嵌入性：算法易于实现，适合集成到大规模应用中。
2. 鲁棒性：高斯 - 赛德尔变体提供了具有单调目标改进的全局收敛保证。
3. 可扩展性：能够处理 $k \ll \min\{n_1, n_2\}$ 的情况，使该方法适用于需要从高维数据中提取主导分量的现代大数据应用。
4. 避免变换：与许多需要将复数流形问题转换为实数问题的现有求解器不同，该方法直接在复 Stiefel 流形上运行。

论文最后指出，虽然当前的公式化强制 $U$ 和 $V$ 具有相等的列数且块划分对称，但底层理论和方法适用于更一般的设置，尽管此类推广的实际应用仍有待探索。