大规模张量特征值的计算方法及其在超图中的应用

With the coming era of massive data, people always analyze relationships among multiple objects using tensors and hypergraphs. Motivated by widespread applications of matrix-based spectral graph methods for various real-world problems, we study a new kind of tensor-based spectral hypergraph methods in this project. On the base of our work published in SIAM J. Sci. Comput. (2016), we further use recent advance in spectral tensor theory, spectral hypergraph theory and nonlinear programming to study the following issues. First, we investigate the spectra of a Laplacian tensor of a hypergraph, analyze the connections between this spectra and Cheeger constant of the hypergraph, and then establish a new model for hypergraph partitioning. Second, we address the spectra of the adjacency tensor of a hypergraph and propose a new model for hypergraph clustering. Third, by exploring the inherent structure of large scale tensors arising from a hypergraph, such as the sparsity of a tensor itself and the sparsity of factor matrices of tensor decomposition, we develop fast computational techniques for products of the large scale tensors and vectors. Then, we customize some first-order and second-order optimization algorithms for these new models. Using the semi-algebraic property of tensors, we prove the strong convergence theory of these optimization algorithms and estimate the probability of optimization algorithms attaining the global solution. Finally, we apply the new tensor-based spectral methods for real-world problems of hypergraph clustering and partitioning, and illustrate the power and efficiency of the new spectral hypergraph methods.

随着大数据时代的来临，人们需要利用张量与超图分析多个因素之间的关联。由于基于矩阵的图谱方法在许多实际问题中有广泛应用，本项目研究新的基于张量的超图谱方法。在SIAM J. Sci. Comput. (2016)文章的基础上，我们利用张量谱理论、超图谱理论和非线性规划等的最新成果，研究以下内容。一、研究超图Laplacian张量的谱信息，分析其与超图Cheeger常数的联系，进而建立超图谱划分的新模型。二、研究超图邻接张量的谱信息，建立超图谱聚类的新模型。三、挖掘超图相关的大规模张量的结构特征，如张量本身的稀疏性和张量分解后因子矩阵的稀疏性，设计大规模张量与向量乘积的快速算法。然后，我们定制相应的一阶与二阶优化算法，利用张量的半代数性质分析算法的收敛性，并估计算法收敛到全局最优解的概率。四、将基于张量谱的新方法应用到实际的超图聚类与划分问题，研究并证实新的超图谱方法的有效性。

随着国家大数据战略的施行，人们研究多个因素之间的关联需要大规模张量、超图模型和最优化方法。受超图中的相关优化问题驱动，项目组围绕超图Laplacian张量的基础理论、大规模张量特征值的计算方法与收敛性分析、超图划分的实际应用和相关张量研究，开展了系列研究攻关，取得了一系列研究成果。我们定义了偶一致超图的规范化的Laplacian张量，证明了其最小的Z-特征值是零，第二小Z-特征值为正的充要条件是该超图是连通的。我们称该Laplacian张量的第二小Z-特征值为超图的代数连通度；相应的Z-特征向量为超图的Fiedler向量，该向量可用于划分超图的顶点集。我们建立了超图的代数连通度与超图的结构常数Cheeger数之间的联系。在计算方面，我们利用超图的结构，探索Laplacian张量的分解因子的稀疏性，设计了Laplacian张量与任意向量乘积的快速算法。由于张量具有半代数性质，我们利用Łojasiewicz性质证明了算法的总体收敛性，并分析了收敛速率。数值实验表明，基于超图Laplacian张量的谱划分方法对子空间聚类、人脸识别、图像分割和运动轨迹判定都非常有效。该方法已推广到解超图顶点集的多聚类问题。我们还研究了一类结构张量的特征值计算的半定规划算法，该方法可以在多项式时间内求得解。对于实际问题中的大规模张量，我们提出了张量的三元分解，并设计和分析了交替最小二乘和谱梯度下降算法。本项目自启动以来，项目组成员共发表论文19篇，另有几篇论文在投稿中。项目负责人在Springer合作出版了1部专著《Tensor Eigenvalues and Their Applications》；在SCI杂志《Pacific Journal of Optimization》第17卷第3期合作编辑了1本专刊。此外，项目负责人获得了广东省自然科学二等奖《结构张量的理论、计算与应用》。