正交非负矩阵分解的算法、理论与应用

Orthogonal nonnegative matrix factorization (ONMF) is a mathematical model for matrix approximation, deriving from linear algebra and multivariate statistical analysis. The problem can be described as: the given matrix is approximately decomposed into the product of two smaller nonnegative matrices, and one of the matrices satisfies the orthogonality constraint. The model is derived from nonnegative matrix factorization (NMF), which has been successfully used in computer vision, gene expression, document clustering, statistical learning, chemometrics, image and audio signal processing, text mining, recommendation systems and other fields of science and engineering. The biggest difference between ONMF and NMF is the addition of orthogonality constraints, which makes the problem more difficult to solve. Up to now, the study on ONMF is fragmented, and algorithms for solving ONMF is still scarce. We hope to propose a new efficient algorithm for solving the ONMF problem. The new algorithm should have the advantages of simple frame, high computational efficiency and high dimensional scalability (i.e., the computational efficiency can hardly be affected as the dimension increases).

正交非负矩阵分解（ONMF）是一种用于矩阵近似的数学模型，来源于线性代数和多元统计分析。该问题可以被描述为：将给定矩阵近似分解为两个规模较小的非负矩阵的乘积，且其中一个矩阵满足正交性约束。该模型源于非负矩阵分解（NMF），已被成功应用于计算机视觉、基因表达、文档聚类、统计学习、化学计量学、图像及音频信号处理、文本挖掘、推荐系统等诸多科学与工程领域。ONMF和NMF最大的区别在于添加了正交性约束，这个非凸约束使得求解该问题的难度大大提升。截至目前，关于ONMF的研究较为零散，求解ONMF的算法更为稀少。我们希望提出求解ONMF问题的新型高效算法，新算法应该具有框架简单、计算效率高、尺度可扩展性高（即问题规模增长时计算效率不会出现显著下降）等优点。

本项目主要研究正交非负矩阵分解(ONMF)问题的算法及其理论性质。该问题源于大数据背景下信息、生物等工程领域的实际应用问题，有较强的应用背景，并具有转化为生产力的可能性。我们首先考虑设计求解ONMF的高效算法，将经典的块坐标下降(BCD)、交替方向(ADMM)等算法应用到正交约束优化框架中去，设计求解ONMF 问题的新算法，同时结合线性化技术、邻近点技术、算子分裂技术等等简化子问题求解。课题组成员深入研究了ONMF模型，并通过变量分离技术提出多种等价的模型。事实上，虽然这些模型都是非凸模型且最优解一致，但是模型结构有较大区别。此外算法的选取也会对结果有较大影响，即使使用同一种算法求解，求解子问题的方法可能有较大差异，最终结果也可能会有很大差别。课题组对三种典型模型和两种算法进行了研究，确定了两块变量的等价模型和ADMM算法是较为适合的。课题组成员将新算法在Matlab编程实现，考虑求解人造问题、k-means聚类问题（可用于文本聚类）等问题，数据采用随机生成和真实数据集等。每种情况下，我们都测试了多种问题设置下算法的性能。初步实验结果显示，新算法在各种情况下均能得到令人满意的结果，在求解采用随机生成数据的k-means聚类问题时，聚类性能大大优于多种公认高效的算法。这些新模型和新算法的提出既丰富了信息科学领域的理论，又丰富了优化领域的理论和算法，还可据此编制算法包，用于求解聚类问题等。因此本课题的研究成果具有理论和应用的双重意义。