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

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.

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

矩阵低秩稀疏分解在统计、信号与图像处理、机器学习、以及金融等诸多领域中有着广泛而重要的应用。本课题基于矩阵秩函数与零模函数的有效非凸代理，构建了矩阵低秩稀疏分解问题的非光滑局部Lipschitz连续优化模型，进而开展了两步凸松弛法的研究，主要包括（1）构造矩阵秩函数与零模函数的局部Lipschitz连续非凸代理，建立矩阵低秩稀疏分解的两个局部Lipschitz连续优化模型；（2）通过对局部Lipschitz连续优化模型作两步适当凸松弛，分别设计矩阵低秩加稀疏极小化问题和正则化问题两步凸松弛方法；（3）针对不同的优化问题，在适当限制特征值条件下建立了每阶段凸松弛问题的最优解到矩阵低秩稀疏分解问题真实解的Frobenius 范数误差界，且从理论上严格证实第二阶段的凸松弛误差小于第一阶段的凸松弛误差，数值试验也验证了这一理论结果；（4）设计求解凸松弛问题的有效收敛算法，提出一种新的具有全局收敛性的变尺度超松弛混合邻近外梯度算法，分析了算法的迭代复杂度和局部线性收敛速度。（5）对张量低秩稀疏分解问题做了初步探讨。该研究已公开发表8篇SCI论文，完成会议报告3次，培养博士生1人、硕士生2人。该研究丰富了低秩稀疏优化和结构非光滑凸矩阵优化的理论，为矩阵低秩稀疏分解提供实际有效的计算工具，并为张量低秩稀疏分解问题提供了一定的基础。