低秩半定矩阵恢复算法研究

发布时间：2018-05-09 14:27

本文选题：低秩半定矩阵恢复 + 最优解　；参考：《北京交通大学》2015年博士论文

【摘要】：低秩半定矩阵恢复问题在信号与图像处理、金融学、控制、图理论、系统识别等众多领域中都有着广泛的应用.它是最优化及其相关领域的一个热点研究课题.通常,低秩半定矩阵恢复问题是NP-难的.为了克服这个困难,凸的核范数松弛技术被广泛应用在文献中,但它并不总是有效的.本文主要针对低秩半定矩阵恢复问题的非凸松弛模型、不松弛的秩正则化模型以及秩在约束条件下的最小二乘模型分别设计有效且稳定的算法.针对低秩半定矩阵恢复问题的特例：低秩半定矩阵完备化问题,首先证明在一定条件下,低秩半定矩阵完备化问题与它的S1/2松弛模型有相同的唯一解.接着建立了S1/2正则化模型解的渐近性.进一步证明了S1/2正则化模型的全局最优解是某个对称矩阵半阈值算子的不动点.基于此条件,设计了一种求解S1/2正则化模型的算法框架,分析了它的收敛性.结合最优的正则化参数设计及截断技术,进一步设计了求解S1/2正则化模型可执行的半阈值特征值算法.数值实验表明该算法的有效性和鲁棒性.针对低秩半定矩阵恢复问题,建立了它的非凸Sp(0p1)正则化模型.通过发展对称矩阵p-阈值算子表示理论,建立了其全局最优解的必要性条件,并给出了全局最优解正特征值的精确下界.进一步得到了全局最优解具有一定低秩性的一个充分条件.设计了p-阈值特征值算法,并给出收敛性分析.数值实验表明该算法能有效地求解这类问题.针对低秩半定矩阵恢复问题,建立了它的秩正则化模型.利用特殊秩函数全局极小解具有显式表达式,证明了其全局最优解是某一对称矩阵硬阈值算子的不动点.基于此不动点方程,设计了一种硬阈值算法,并给出相应的收敛性分析.数值实验表明所设计算法的有效性及稳定性.针对低秩半定矩阵恢复问题秩在约束条件下的最小二乘模型,通过目标函数的优超函数,将原问题转化成非凸集上的投影.利用非凸集上投影的显式表达式,给出了原问题全局最优解的一个必要性条件.进而设计了求解该问题的优超算法,并证明了其迭代点列的任何一个聚点都是原问题的一阶稳定点.
[Abstract]:Low-rank semidefinite matrix restoration problem has been widely used in many fields such as signal and image processing, finance, control, graph theory, system recognition and so on. It is a hot research topic in optimization and related fields. In general, the restoration problem of low rank semidefinite matrices is NP- difficult. In order to overcome this difficulty, convex kernel norm relaxation technique is widely used in literature, but it is not always effective. In this paper, an efficient and stable algorithm is designed for the non-convex relaxation model, the non-relaxed rank regularization model and the least square model of the rank under the constraint conditions for the restoration of the low-rank semidefinite matrix. For the special case of the low rank semidefinite matrix restoration problem: the low rank semidefinite matrix completion problem, it is first proved that, under certain conditions, the low rank semidefinite matrix completeness problem has the same unique solution as its S 1 / 2 relaxation model. Then the asymptotic behavior of the solution of S 1 / 2 regularization model is established. It is further proved that the global optimal solution of the S1 / 2 regularization model is a fixed point of the semi-threshold operator of a symmetric matrix. Based on this condition, an algorithm framework for solving S1 / 2 regularization model is designed and its convergence is analyzed. Based on the optimal regularization parameter design and truncation technique, an executable semi-threshold eigenvalue algorithm for S1 / 2 regularization model is designed. Numerical experiments show that the algorithm is effective and robust. A non-convex Spn0p1) regularization model is established for the restoration of low rank semidefinite matrices. By developing the representation theory of symmetric matrix p-threshold operator, the necessary conditions for the global optimal solution are established, and the exact lower bound of the positive eigenvalue of the global optimal solution is given. Furthermore, a sufficient condition for the global optimal solution to have a certain low rank is obtained. The p-threshold eigenvalue algorithm is designed and the convergence analysis is given. Numerical experiments show that the algorithm can solve this kind of problem effectively. A rank regularization model is established for the restoration of low rank semidefinite matrices. It is proved that the global optimal solution is a fixed point of a symmetric matrix hard threshold operator by using the explicit expression of the global minimal solution of a special rank function. Based on the fixed point equation, a hard threshold algorithm is designed and the convergence analysis is given. Numerical experiments show the effectiveness and stability of the proposed algorithm. For the least square model of the low rank semidefinite matrix restoration problem under the constraint condition, the original problem is transformed into a projection on a non-convex set by the optimal superfunction of the objective function. By using the explicit expression of projection on the non-convex set, a necessary condition for the global optimal solution of the original problem is given. Furthermore, an optimal superalgorithm for solving the problem is designed, and it is proved that any accumulation point of the iterative point sequence is the first order stable point of the original problem.
【学位授予单位】：北京交通大学
【学位级别】：博士
【学位授予年份】：2015
【分类号】：O151.21

【相似文献】