基于松弛函数结构分解的非凸非光滑稀疏信息恢复算法研究

In the last decade, information recovery problems based on sparse signal recovery and low rank matrix recovery is a hot topic in many scientific research fields, such as information science, applied mathematics, statistics, machine learning, computer vision. Traditional convex relaxation models for solving sparse information recovery problems have obtained a lot of achievements in both theoretical analysis and design of algorithm. In contrast, non-convex sparse recovery models need a systematic and in-depth study in both theory and algorithm. This project mainly studies the design problem of algorithm for non-convex sparse restoration models. An important reason for the difficulty of solving non-convex sparse recovery models is the non-convexity and non-smoothness of relaxation functions, especially the non-smoothness, which prevents the use of traditional smoothing methods such as gradient methods and Newton methods. The project uses the decomposition properties of a large class of non-convex relaxation functions and Moreau envelopes of non-smooth convex functions to construct a smooth function, proves that non-convex sparse recovery models are equivalent to the corresponding smooth optimization problems, and then constructs new and efficient non-convex sparse optimization algorithms.

近十多年，以稀疏信号恢复和低秩矩阵恢复为主的信息恢复问题是信息科学，应用数学，统计学，机器学习，计算机视觉等许多科学研究领域关注的前沿话题。传统求解稀疏信息恢复问题的凸松弛模型在理论分析和算法设计方面都获得了非常多的成果。相比之下，非凸稀疏恢复模型在理论和算法方面还需要系统而深入的研究。本项目主要研究非凸稀疏恢复模型的算法设计问题。非凸稀疏恢复模型难以求解的一个重要原因是松弛函数的非凸非光滑性，尤其是非光滑性阻止了诸如梯度法、牛顿法等传统光滑型方法的使用。本项目通过利用一大类非凸松弛函数的分解性质和非光滑凸函数的Moreau包络来构造光滑函数，证明非凸稀疏恢复模型和相应的光滑优化问题是等价的，进而构建新的有效非凸稀疏优化算法。

非凸非光滑稀疏信息优化问题是最近十多年信号和图像处理，应用数学，统计学和机器学习等领域重点研究的基础应用科学问题。本项目主要研究了非凸非光滑稀疏信息优化问题的等价光滑优化模型及其相关问题的算法设计和应用，获得了如下的三类重要的研究结果：其一，给出了常见非凸稀疏惩罚函数遵循的两类分解规则并提出了一个满足第一类分解规则的新的非凸稀疏惩罚函数，构建了相应的非凸非光滑稀疏信息优化问题的等价光滑优化模型。其二，针对图像复原问题，利用图像非局部低秩先验信息，建立了低秩正则化优化模型，提出了被称为PARM的求解算法并利用著名的KL不等式证明了算法收敛性。所提算法在图像去模糊和图像填充等图像复原问题上获得了很好的效果。其三，针对测量稀疏信号的不相干矩阵的设计问题，建立了矩阵秩约束的半定无穷范数极小化模型，给出了与秩有关的部分非凸约束集的凸差表示，提出了上述模型的部分惩罚模型并设计了被称为DCACO的求解不相干矩阵的算法。在项目的支持下，撰写了3篇高水平论文，其中，已经在线发表论文2篇，正在进行一轮审稿后修改的论文1篇。