Exact Nonnegative Matrix Factorization via Cone-Ray Witnesses: Obtuseness Ranking, Saturation Curves, and an Augmented Alt-LP Breakthrough

技术摘要：基于锥射线见证者的精确非负矩阵分解

问题陈述
本文研究了**精确非负矩阵分解（Exact Nonnegative Matrix Factorization, NMF）问题。给定一个非负秩至多为 $r$ 的非负矩阵 $A \in \mathbb{R}^{m \times n}_{\ge 0}$，目标是寻找非负因子 $W \in \mathbb{R}^{m \times r}_{\ge 0}$ 和 $H \in \mathbb{R}^{n \times r}_{\ge 0}$，使得 $A = WH^\top$ 且残差为零。不同于旨在寻求低误差近似的近似 NMF（用于主题模型和推荐系统，该问题是 NP-hard），本研究专注于在不假设可分性（separability）**条件（即 $A$ 的列是基向量的一个子集）的情况下，恢复精确分解。本文针对的是在理论上可行但由于组合约束而具有计算挑战性的规模较小的实例。

方法论
作者提出了一种“锥-射线流水线（cone-ray pipeline）”，将 NMF 问题转化为对多面锥的搜索。该方法论分为四个阶段：

1. SVD 截断： 输入矩阵 $A$ 通过精简 SVD（$A = U S V^\top$）进行分解。作者定义正交基 $A_{orth} = U_{:,1:r} \sqrt{S_{1:r,1:r}}$ 和 $A_{orth1} = V_{:,1:r} \sqrt{S_{1:r,1:r}}$。任何精确分解都可以表示为 $W = A_{orth}Q$ 和 $H = A_{orth1}P$，其中 $Q, P \in \mathbb{R}^{r \times r}$ 满足 $QP^\top = I_r$。
2. 多面锥构建： $W$ 和 $H$ 的非负性约束意味着 $Q$ 和 $P$ 的列必须位于由 $A_{orth}$ 和 $A_{orth1}$ 定义的特定多面锥内。作者使用通过 cddlib 实现的**双描述法（Double Description Method, DDM）**来计算这些锥的极射线（extreme rays, $R_{orth}$ 和 $R_{orth1}$）。
3. 均匀支撑见证者（闭式解）： 核心创新在于一种参数化方法，其中 $Q$ 和 $P$ 的列被限制为锥的极射线中特定 $r$ 个射线的非负组合。令 $T$ 和 $K$ 为射线索引的 $r$ 子集。若 $Q = R_T \mu$ 且 $P = R_K \nu$ 且 $\nu = I_r$，则约束 $QP^\top = I_r$ 坍缩为一个闭式条件：
   $$M_T = R_T^{-1} (R_K^\top)^{-1} \ge 0$$
   如果矩阵 $M_T$ 是逐元素非负的，则可以直接恢复出精确 NMF。该测试计算开销极低（微秒级）。
4. 钝角排序搜索： 由于 $r$-子集的数量是组合爆炸的，作者根据几何“钝角度（obtuseness）”得分对候选子集进行排序：$|\det(R_T)| / \prod \|R_{T,i}\|$。该得分衡量了射线的近正交性；得分越高表示锥体越“胖”，越有可能产生非负见证者。算法会对排名靠前的候选者进行遍历。
5. 增强型交替线性规划（Alt-LP）回退： 当闭式见证者 $M_T$ 不可行（即包含负元素）时，该方法并不仅是简单地丢弃该对组合。相反，它通过添加与现有射线角距离最大的 $k=2$ 个额外射线来增强支撑集 $T$ 和 $K$。这创建了一个 $r \times (r+k)$ 的支撑。随后，作者使用**交替线性规划（alt-LP）**来求解系数 $\mu, \nu$，以最小化松弛量，从而在保持可处理性的同时放宽了严格的均匀支撑约束。

核心贡献

1. 均匀支撑下的闭式见证者： 本文确立了对于精确秩输入，联合非负性约束可以简化为预计算矩阵 $M_T$ 的简单逐元素非负性检查。这为精确分解的可行性提供了微秒级的测试。
2. 钝角排序搜索与饱和分析： 通过 100 次蒙特卡洛试验（$m=n=10$），作者表征了钝角启发式算法的性能。他们证明了搜索在排名前 200 的候选者预算下会趋于饱和；将预算增加到前 400 名带来的收益微乎其微。至关重要的是，他们表明超过此点的失败是结构性的（即锥体缺乏近正交子集），而非由于搜索预算不足。
3. 识别规模墙（Scaling Walls）： 本文记录了特定的失效模式：
   • 维度性： 在固定 $r$ 的情况下增加 $m, n$（例如 $m=n=15$）实际上会降低成功率，因为对偶锥变得更加“瘦削”，缺乏近正交子集。
   • DDM 瓶颈： 在处理如 Olivetti 面部图像（$400 \times 4096$）等大型数据集时，由于不等式数量爆炸，即使对于较小的 $r$，DDM 步骤也会变得难以处理。
4. 混合增强型交替-LP突破： 主要贡献是结合了闭式测试与增强型支撑交替-LP的混合算法。通过仅在必要时才放宽均匀支撑限制，该方法打破了闭式见证者所观察到的结构性天花板。

结果

• 小规模（$m=n=10$）：
  • 闭式方法（前 200 名）在 $r=4, 5, 6$ 时分别实现了 100 次试验中的 79/85/58 次成功。
  • 混合方法（闭式 + 增强型交替-LP）将这些成功率提高到了 99/95/75，有效地打破了结构性天花板。
  • 在成功的情况下，重构误差达到了机器精度（$\sim 10^{-15}$）。
• 中规模（$m=n=15$）：
  • 闭式方法显著失效（对于 $r=4, 5, 6$，成功次数分别为 37/7/0）。
  • 混合方法恢复了 78/28/0 次成功，显示出改进，但在 $r=6$ 时遇到了新的结构性墙，因为此时锥体过于瘦削，即使进行 $k=2$ 增强也无法解决。
• 大规模（Olivetti）：
  • 流水线无法在 1 小时的预算内完成 DDM 步骤，凸显了高维数据下精确极射线枚举的不可行性。

意义与主张
本文声称提供了一个完全可执行的精确 NMF 工具包，该工具包不依赖于可分性假设。其意义在于：

• 认证性： 不同于近似方法，该工具包在成功时会返回精确性的证书（机器精度重构）。
• 几何洞察： 它严谨地表征了实现精确分解所需的几何条件（锥射线间的近正交性），表明“胖”锥体是闭式解的必要条件。
• 实践突破： 混合增强型交替-LP 方法是研究中第一个能果断打破闭式见证者结构性天花板的方法，将成功率推升至 90% 以上。

作者对局限性保持谦逊，承认该流水线面临四个“规模墙”：DDM 射线计数爆炸、均匀支撑限制（部分被解除）、数值稳定性以及在完全非均匀变体上松弛-LP 的平台期。他们指出，未来的工作必须解决 DDM 的可扩展性（通过采样）以及针对剩余结构性失败的更深层次增强或替代求解器（如 NNLS）。