Sum-of-norms regularized Nonnegative Matrix Factorization

本文研究了非负矩阵分解（NMF）中的非负秩问题，因为该秩通常是启发式估计的，而计算其确切值是NP难的。作者提出了一种近似方法，在解决NMF的同时估计该秩。作者使用了一种鼓励成对相似性的组套索（SON）结构来减少因开始时过高估计秩而导致的因子矩阵秩。在各种数据集上，SON-NMF能够自动揭示数据的正确非负秩，无需任何先验知识或调整。SON-NMF是一个非凸非光滑非可分离非可近问题，解决它并不容易。首先，由于NMF中的秩估计是NP难的，所以所提出的方法不具有较低的计算复杂度。通过图论的论证，作者证明了SON-NMF的复杂度几乎是不可降低的。其次，任何解决SON-NMF的算法的每次迭代成本可能很高，这促使作者提出了一种一阶BCD算法，以低迭代成本近似解决SON-NMF，其中使用了近端平均算子。最后，作者提出了一种简单的贪心方法进行后处理。SON-NMF具有良好的应用特点。除了能够自动从数据中估计秩外，SON-NMF还可以处理秩缺失的数据矩阵，可以检测能量较小的弱成分。此外，在高光谱成像应用中，SON-NMF自然地处理了光谱变异问题。

本文旨在解决非负矩阵分解（NMF）中的非负秩参数估计问题。由于计算其确切值是NP难的，因此通常采用启发式方法进行估计。本文提出了一种近似方法，在解决NMF的同时估计该秩。

本文提出了一种基于sum-of-norm（SON）的方法来减小因秩被高估而导致的因子矩阵的秩。SON是一种鼓励成对相似性的group-lasso结构。本文证明了SON-NMF的复杂性几乎是不可约的。为了解决这个问题，本文提出了一个低迭代成本的一阶BCD算法来近似求解SON-NMF。最后，本文提出了一个简单的贪心方法进行后处理。

本文提出的SON-NMF方法具有自动估计数据秩的能力，可以处理秩不足的数据矩阵，可以检测能量较小的弱分量。在高光谱成像应用中，SON-NMF自然地处理了光谱可变性问题。本文在多个数据集上进行了实验，并且提供了开源代码。

最近在这个领域中，还有一些相关的研究。例如，2019年发表的论文《Robust Nonnegative Matrix Factorization via Joint Graph Laplacian and Discriminative Information》和2018年发表的论文《Nonnegative Matrix Factorization with Group Sparsity for Clustering》。