超图H谱理论和稀疏低秩优化算法研究

发布时间：2018-03-01 21:03

本文关键词： H特征值张量超图 LP正则规划 Sylvester方程　出处：《清华大学》2016年博士论文　论文类型：学位论文

【摘要】：高维矩阵称为张量,它在数据分析和超图理论等领域有着广泛的应用。利用张量的特征值理论来研究各种超图谱理论是多重线性代数的一个新兴领域。而随着大数据时代的到来,为了减少海量数据的采样、存储、传输和分析负担,分析问题的稀疏或低秩解也变得越来越重要。本论文围绕这两部分展开,一部分是基于张量H特征值的超图谱理论研究,另一部分是稀疏低秩优化的相关算法研究。本论文的主要结果如下:1.我们给出了核超图和幂超图的邻接张量和无符号拉普拉斯张量的H特征值的一些性质。利用这些性质,我们计算出了太阳花、超星和超圈的邻接张量和无符号拉普拉斯张量的最大H特征值。另外,我们给出了超路的邻接张量和无符号拉普拉斯张量的最大H特征值更紧的界,并提供了数值算法求解。2.我们给出了超星、超路和超圈的邻接张量、拉普拉斯张量和无符号拉普拉斯张量的所有H特征值。数值结果表明,对于固定长度的几类超图,随着k的增加,其H特征值呈收敛状态。我们给出了超星、长度为2的超圈和长度为3的超路的H谱的收敛性证明。3.L_p(0p1)正则优化问题是研究稀疏和低秩优化的关键问题,其中无约束的模型已经有大量的研究,但带约束的模型研究相对较少。我们设计了求解带上下界约束的L_p正则向量优化问题、带半正定或非负矩阵约束的L_p正则优化问题的迭代算法,并给出了数值实验。数值结果验证了算法的有效性。4.我们证明了一般Sylvester类矩阵方程的低秩解问题是NP难的。进一步,给出了三类具有特殊结构的Sylvester类矩阵方程的低秩解是多项式可解的,并提出了数值求解算法。
[Abstract]:The high-dimensional matrix is called Zhang Liang, It has been widely used in the field of data analysis and hypergraph theory. It is a new field of multiplex linear algebra to study various hypergraph theories by the theory of eigenvalue of Zhang Liang. In order to reduce the burden of sampling, storage, transmission and analysis of mass data, the sparse or low rank solution of the problem becomes more and more important. The main results of this paper are as follows: 1. We give some properties of H eigenvalues of nuclear hypergraphs and power hypergraphs adjacent to Zhang Liang and unsigned Laplacian #internal_person1#. We have calculated the maximum H eigenvalues of the sunflowers, superstars and hypercycles adjacent to Zhang Liang and unsigned Laplacian Zhang Liang. In addition, we have given a more compact bound of the maximum H eigenvalues of the superpaths adjacent to Zhang Liang and unsigned Laplacian #internal_person2#. We give all the H eigenvalues of Zhang Liang, Laplace Zhang Liang and unsigned Laplace Zhang Liang adjacent to superstars, hyperpaths and hypercycles. The numerical results show that for several types of hypergraphs of fixed length, With the increase of k, the H eigenvalue of k converges. We prove the convergence of H spectra of superstars, hypercycles of 2 and hyperpaths of 3. 3. The problem of regular optimization is a key problem in the study of sparse and low rank optimization. There has been a lot of research on the unconstrained model, but the research on the constrained model is relatively few. We design the LP regular vector optimization problem with upper and lower bound constraints. The iterative algorithm of LP regular optimization problem with positive semidefinite or nonnegative matrix constraints is presented, and numerical experiments are given. The numerical results verify the validity of the algorithm .4.We prove that the low rank solution problem for general Sylvester class matrix equations is NP-hard. In this paper, three classes of Sylvester class matrix equations with special structure are given. The low rank solutions are polynomial solvable, and a numerical algorithm is proposed.
【学位授予单位】：清华大学
【学位级别】：博士
【学位授予年份】：2016
【分类号】：O157.5

【相似文献】