Gap-Aware Exact Nonnegative Matrix Factorization: A Two-Sided SVD Gauge and a Three-Regime W-Rank Taxonomy

技术摘要：具备间隙感知能力的精确非负矩阵分解

问题陈述
本文研究了“间隙机制”（gap regime）下的精确非负矩阵分解（Exact NMF）挑战，即目标非负秩 $r_+$ 严格大于矩阵秩 $r$（$r_+ > r$）。前人的工作 [1] 为均匀支撑（uniform-support）机制（$r_+ = r$）建立了“锥射线”（cone-ray）流水线，但该方法具有局限性：它假设内维等于矩阵秩，将恢复的因子 $W$ 限制在秩 $r$，且缺乏对奇异值分解（SVD）规范（gauge）的选择自由度。作者旨在将这一流水线扩展到 $r_+ > r$ 的情况，在这种情况下，解空间的几何结构会发生显著变化，并根据因子 $W$ 的秩结构对可恢复的分解进行分类。

方法论
其核心贡献是一个双侧 SVD 规范框架，它推广了锥射线流水线。

1. 对称参数化： 该方法并非使用秩为 $r$ 的截断 SVD 因子 $U_r$ 和 $V_r$，而是构建扩展的正交框架：
   $$U_{r_+}(G) = [U_r \mid U_\perp G], \quad V_{r_+}(K) = [V_r \mid V_\perp K]$$
   其中 $U_\perp$ 和 $V_\perp$ 分别张成 $M$ 的列空间和行空间的正交补，$(G, K)$ 是位于 Stiefel 流形 $St(m-r, r_+-r) \times St(n-r, r_+-r)$ 上的矩阵。
2. 平方一致性： 分解约束 $WH = M$被转化为中间因子$Q$和$P$ 的平方一致性条件：
   $$QP = \text{diag}(S_r, 0) \in \mathbb{R}^{r_+ \times r_+}$$
   这使得 $Q$ 和 $P$ 的秩可以独立地在 $r$ 到 $r_+$ 之间变化，只要它们的乘积秩为 $r$。
3. 算法流水线： 该方法采用两阶段法：
   • 阶段 A（SVD-规范锥射线）： 对于固定的规范 $(G, K)$，利用双描述法（Double Description Method, DDM）计算由 $U_{r_+}(G)$ 和 $V_{r_+}(K)$ 定义的锥的极射线。该方法按“钝角性”（obtuseness）对射线子集进行排序，并尝试寻找闭式解见证（closed-form witness）。如果失败，则退回到交替线性规划（alt-LP）。
   • 阶段 B（秩亏损 $W$ 分支）： 一个互补分支，直接枚举 $M$ 的 $r_+$ 个列子集。它通过线性规划（LP）逐列测试可行性。该分支针对的是 $W$ 为 $M$ 的列子集（意味着 $\text{rank}(W) = r$）的解。

三类机制分类法
本文根据因子 $W$ 的秩将精确 NMF 问题分为三个机制：

• 机制 A ($\text{rank}(W) = r_+$)： 全列满秩。数据锥在外部锥内的余维数为 $r_+ - r$。作者证明，对于稠密随机矩阵，“松弛包络”（slack enclosure）现象（额外的维度提供了充足的松弛）以及有效的非负秩分解（NRF）流形的“厚度”，使得盲目的 SVD 选择 $(G, K)$ 以概率 1 成功。
• 机制 B ($\text{rank}(W) = r$)： $W$ 是 $M$ 的一个列子集。在此情况下，有效的 NRF 流形由于结构约束（例如块对角矩阵）而退化为测度为零的集合（通常是 Grassmannian 中的单点）。盲目的 SVD 几乎必然失败，均匀的 Stiefel 重启也无法挽救。然而，秩亏损 $W$ 分支（阶段 B）可以高效解决这些情况。
• 机制 C ($r < \text{rank}(W) < r_+$)： $W$ 不是列子集，且其秩严格介于 $r$ 和 $r_+$ 之间。正八边形的松弛矩阵是主要示例。虽然对称形式化可以表示此类解（通过预设的规范验证），但盲目搜索正确的 $(G, K)$ 仍未解决。损失景观在组合单元上是分片常数的，导致局部黎曼优化方法（梯度下降、共轭梯度）停滞。

关键结果

• 稠密矩阵（机制 A）： 在 $10 \times 10$ 稠密随机间隙矩阵（$r=4, r_+ \in \{5, 6\}$）上，该流水线仅使用闭式解见证阶段就实现了 100/100 的恢复。这优于 $r_+ = r$ 的情况（在 79–87/100 处饱和），归功于间隙提供的几何“松弛”。
• 结构化矩阵（机制 B）： 对于矩阵族 $M_k = \text{diag}(C, J_k)$（其中 $C$ 是秩为 4 的循环矩阵，$J_k$ 是全 1 矩阵），盲目 SVD 流水线在 $k \ge 2$ 时完全失效（0/4 成功）。均匀 Stiefel 重启也失败了（0/50 命中）。然而，秩亏损 $W$ 分支在毫秒级内恢复了 4/4 的成功。
• 正八边形（机制 C）： 对于正八边形的松弛矩阵（$r=3, r_+=6$），存在大小为 6 的 NRF，且标准 NMF 求解器（sklearn）能以高精度找到它。然而，所提出的工具包无法盲目找到它。通过预设规范（oracle gauge）进行的实验证实，该形式化能够表示该解，但盲目搜索方法（Stiefel/Grassmannian 采样和黎曼梯度下降）无法定位可行规范，会陷入残差远大于零的局部极小值。
• 组合工具包： 一个先运行阶段 B 后运行阶段 A 的编排器涵盖了机制 A 和机制 B，且在稠密抽样上没有性能退化，在测试的这两个机制的并集上实现了 100% 的成功。

意义与主张
本文声称将精确 NMF 的锥射线流水线扩展到了间隙机制，提供了一个统一的几何框架。其意义在于：

1. 几何洞察： 证明了对于稠密矩阵，间隙机制（$r_+ > r$）放宽了包络问题，使得盲目的 SVD 选择变得有效；而具有紧凑秩约束的结构化矩阵会产生测度为零的解空间，盲目启发式方法会错过这些空间。
2. 实际鲁棒性： 引入了“秩亏损 $W$”分支，绕过了结构化矩阵的规范问题，确保工具包既能处理稠密随机数据，也能处理特定的结构化族（如块对角和）。
3. 局限性与开放问题： 作者谦逊地承认 机制 C 仍未解决。在正八边形上的局部优化失败凸显了一个根本性的病态特征：损失景观在组合单元上是分片常数的，这阻碍了基于梯度的方法跨越单元壁。论文指出，开发更平滑的代理损失函数或跳跃盆地（basin-hopping）策略是未来的研究方向，但并未声称已解决机制 C 的盲目搜索问题。

这项工作被呈现为一种“双侧 SVD 规范”和“三类机制分类法”，它理清了精确 NMF 工具的覆盖范围，区分了盲目 SVD 足够的情况、需要列子集枚举的情况，以及仍然悬而未决的问题。