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

Graph clustering is an important topic in data analysis. It divides a set of given data objects in Euclidean space into several clusters. The objects those who have similar characteristics are categorized in a same cluster, and vice versa. The most common model for graph clustering is called k-means clustering, which is equivalent to an orthogonal nonnegative matrix factorization (ONMF) problem. Therefore, to design efficient algorithms for ONMF is very important. On the other hand, no matter nonnegative matrix factorization or general orthogonal constrained optimization are NP-hard. Moreover, due to the essential combinatorial property, to solve ONMF is an extremely challenging topic. In this project, we aim to deal with the nonnegative constraint and the orthogonal constraint by two strategies, "splitting" and "alternating", and propose efficient algorithms for ONMF. We will analyze the convergence of new proposed algorithms and also investigate their numerical performance in graph clustering.

在大数据分析中，图聚类是一类重要的课题。它可以将一组空间数据对象分成若干个类别，这些对象与同一个类别中的对象彼此相似，与其它类别中的对象相异。最常见的图聚类模型是基于相对距离的k平均聚类模型，而k平均聚类模型等价于一个含有正交约束的非负矩阵分解问题。可见设计正交非负矩阵分解的高效算法对数据聚类有着非常重要的价值。另一方面，无论是非负矩阵分解，还是一般的含正交约束的矩阵优化问题，都是NP-难的，而正交非负矩阵分解由于其内蕴的组合性质，要求解它更是一个极具挑战性的课题。本项目通过分裂与轮换两种方法来处理非负性与正交性，以期得到求解正交非负矩阵分解的快速优化算法，并分析其收敛性质。我们还将考察新算法在图聚类问题中的表现。

本项目对正交非负矩阵分解进行了一定的研究，设计了有效的增广拉格朗日乘子交替方向算法。通过一定来源于大数据分析的图聚类问题检验了方法的可行性。对于两类特殊问题，矩阵完整化问题和鲁棒PCA问题，设计了高效的交替投影方法，并分析了其理论性质。