arXiv:2508.07134cs.LGcs.DM2025-08

提出一种全局最优的半非负矩阵分解方法,无需迭代即可获得最佳重构结果。

A Globally Optimal Analytic Solution for Semi-Nonnegative Matrix Factorization with Nonnegative or Mixed Inputs

  • 基于输入数据散度矩阵的正交分解,直接求解全局最优解。
  • 在低秩情况下(如秩1或2)可精确还原标准NMF结构,且重构误差更低。
  • 适合追求理论保证与高精度重构的优化与数据分析研究者使用。

半非负矩阵分解(semi-NMF)通过允许基矩阵包含正负值,扩展了经典非负矩阵分解(NMF)的应用范围,适用于符号混合的数据。然而,现有semi-NMF算法多为迭代、非凸,易陷入局部极小。本文提出一种新方法,在Frobenius范数下通过输入数据的散度矩阵正交分解,获得semi-NMF问题的全局最优解,并严格证明该解达到重建误差的全局最小。当输入矩阵为非负时,本方法通常比标准NMF获得更低的重建误差,尽管基矩阵可能不满足非负性;特别地,在秩1或2等低秩情形下,解精确退化为非负分解,恢复NMF结构。实验在合成数据与UCI Wine数据集上验证,本方法在重构精度上持续优于现有NMF与semi-NMF方法。结果表明,该非迭代、全局最优的公式兼具理论保障与实证优势,为矩阵分解提供了新的优化视角。

原文摘要 · Abstract (English)

Semi-Nonnegative Matrix Factorization (semi-NMF) extends classical Nonnegative Matrix Factorization (NMF) by allowing the basis matrix to contain both positive and negative entries, making it suitable for decomposing data with mixed signs. However, most existing semi-NMF algorithms are iterative, non-convex, and prone to local minima. In this paper, we propose a novel method that yields a globally optimal solution to the semi-NMF problem under the Frobenius norm, through an orthogonal decomposition derived from the scatter matrix of the input data. We rigorously prove that our solution attains the global minimum of the reconstruction error. Furthermore, we demonstrate that when the input matrix is nonnegative, our method often achieves lower reconstruction error than standard NMF algorithms, although unfortunately the basis matrix may not satisfy nonnegativity. In particular, in low-rank cases such as rank 1 or 2, our solution reduces exactly to a nonnegative factorization, recovering the NMF structure. We validate our approach through experiments on both synthetic data and the UCI Wine dataset, showing that our method consistently outperforms existing NMF and semi-NMF methods in terms of reconstruction accuracy. These results confirm that our globally optimal, non-iterative formulation offers both theoretical guarantees and empirical advantages, providing a new perspective on matrix factorization in optimization and data analysis.

矩阵分解优化算法数据降维

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。