矩阵低秩稀疏分解的两步凸松弛法研究

项目名称： 矩阵低秩稀疏分解的两步凸松弛法研究

项目编号： No.11501219

项目类型： 青年科学基金项目

立项/批准年度： 2016

项目学科： 数理科学和化学

项目作者： 韩乐

作者单位： 华南理工大学

项目金额： 18万元

中文摘要： 矩阵低秩稀疏分解在统计、信号与图像处理、机器学习、以及金融等诸多领域中有着广泛而重要的应用。本课题拟基于秩函数与零模函数的有效非凸代理，构建矩阵低秩稀疏分解问题的非光滑局部Lipschitz连续优化模型，进而开展两步凸松弛法的研究，包括（1）构造秩函数与零模函数的局部Lipschitz连续非凸代理，建立矩阵低秩稀疏分解的局部Lipschitz连续优化模型；（2）通过对局部Lipschitz连续优化模型作两步适当凸松弛，设计两步凸松弛方法；（3）研究每步凸松弛的最优解与矩阵低秩稀疏分解真实解的误差界、近似秩界和近似稀疏度，并量化第一步的误差界、近似秩界和近似稀疏度在第二步的下降量；（4）设计求解凸松弛问题的有效收敛算法，编写低秩稀疏分解两步凸松弛法的程序代码并进行数值试验。该研究成果将丰富低秩稀疏优化和结构非光滑凸矩阵优化的理论，并为矩阵低秩稀疏分解提供实际有效的计算工具。

中文关键词： 矩阵低秩稀疏分解；凸松弛；误差界；非凸代理

英文摘要： Low-rank and sparse matrix decomposition has wide and important applications in statistics, signal and image processing, machine learning, financial and many other fields. The topics aims to carry out the research on the two-step convex relaxation methods for low-rank and sparse matrix decomposition by constructing nonsmooth and locally Lipschitz continuous optimization models, based on the non-convex surrogates for rank function and zero norm. The topic includes (1) constructing the locally Lipschitz continuous and nonconvex surrogates for rank function and zero norm and establishing the locally Lipschitz continuous optimization models for low-rank and sparse matrix decomposition; (2) designing the two-step convex relaxations for the locally Lipschitz continuous optimization models; (3) studying the error bound and the bounds on rank error and sparsity error of the optimal solution of the convex relaxations in each step and the true solution of the low-rank and sparse matrix decomposition, emphatically analyzing the decline of error bounds in the second convex relaxation compared with that in the first step; (4) designing an effective algorithm to solve the convex relaxation problems and testing the new algorithm. The research results will not only enrich the theory on low-rank and sparse matrix optimization and structurally nonsmooth convex optimization, but also provide efficiently computational tools for low-rank and sparse matrix decomposition.

英文关键词： low-rank and sparse matrix decomposition;convex relaxation;error bound;nonconvex surrogate