非凸稀疏模型中的逼近理论与算法

Nonconvex sparse models are particularly useful in scientific applications, such as signal and image processing, machine learning and artificial intelligence. This project is aimed at the approximation theory and algorithms in nonconvex sparse modeling, including L0 nonconvex approximation theory, optimal solutions of the low rank matrix optimization problems and algorithms for a class of nonconvex sparse models. We anticipate obtaining three main results. Many loss functions arising from applications are not level-bounded functions. One task of this project is investigating the relationship between optimal solutions of the L0 regularization problem and its nonconvex approximation problem, when the loss function satisfies some mild conditions. Many low rank matrix optimization problems arise from clustering analysis and recommendation systems. Another research target of this project is the optimal solutions of the low rank matrix optimization problems, including stability to parameters, that is the solution path, and the relationship between different optimization problems. In applications, there are a class of loss functions, which are convex, continuously differentiable on its domain but the gradients are not globally Lipschitz continuous. We aim to design convergent algorithms for nonconvex sparse problems containing this class of loss functions. This project may tackle several fundamental problems on optimal solution sets and provide applicable algorithms for nonconvex sparse models.

非凸稀疏模型广泛应用于信号与图像处理、机器学习以及人工智能等多个领域。本项目研究非凸稀疏模型中的逼近理论与算法，包括L0正则化模型非凸逼近理论、低秩矩阵优化模型解集理论以及一类非凸稀疏模型的算法。希望达到以下三个研究目标：应用中的很多损失函数不具有有界水平集，项目研究目标之一为分析当损失函数不具有有界水平集，而是满足较弱条件时，L0正则化模型及其一类非凸逼近模型解集之间的关系；聚类分析以及推荐系统等问题出现大量低秩矩阵优化模型，项目另一目标为研究低秩矩阵优化问题解关于参数的稳定性，即解路径，并探讨常用的几种低秩矩阵优化模型解集间的关系；应用中会遇到一类凸损失函数，在定义域上连续可微，但梯度不Lipschitz连续，针对含有此类损失函数的非凸稀疏模型发展收敛算法为项目的第三个研究目标。本项目有希望在理论上解决非凸稀疏模型中关于解集的一些基本问题，并为非凸稀疏模型的应用提供可靠的算法。

本项目研究了非凸稀疏模型的逼近理论和算法。稀疏模型广泛应用于图像处理、信号复原等问题中，其中复合L0函数（即L0函数与线性算子或仿射变换的复合）通常用来作为稀疏正则项。由于L0函数的非凸非光滑性以及与线性算子的复合，使得相应的优化问题难以求解。解决这个困难的方法之一通过引入一个变量，将仿射变换变为等式约束，然后再用罚函数方法放到目标函数之中。而这恰好为将L0函数用帽子的Lp（capped Lp）函数去逼近L0复合函数。我们首先研究了相应优化问题解的存在性，这里，我们不需要假设目标函具有有界水平集，而只需要假设目标函数中的拟合项是渐进水平稳定且有下界。这类的拟合项涵盖了应用中的大部分拟合项，比如最小二乘拟合项，咬链损失拟合项等，尽管不具有有界水平集，但满足渐进水平稳定且有下届的条件。其次，我们证明了帽子Lp正则化问题的解渐进逼近L0复合函数正则化问题的解。最后，我们进一步证明在某些特殊的拟合函数下，帽子Lp正则化模型与L0复合正则化模型当逼近参数足够大时具有相同的解集。稀疏逆协方差复原问题是高斯网络模型中的基础问题，稀疏正则化的负Log似然函数极小化模型为常用的求解方法。尽管凸函数L1范数广泛应用于稀疏正则项，但它往往得不到足够稀疏的解。L0函数是描述稀疏性的最自然的函数，且L0正则化的负对数似然模型也已在实验中证实可以得到更好的解。然而，当样本协方差矩阵不可逆时，L0正则化模型时没有最优解的。我们提出同时使用L0正则化和Tikhonov正则化，这保证了模型解的存在性。我们首先分析了Tikhonov正则项和L0正则项的正则性质。其次提出用罚函数方法求解提出的模型，以克服L0函数及正定约束带来的困难，并证明了罚函数问题对原问题解的渐进逼近性质。对罚函数问题，我们首先用不动点方程刻画其局部极小值点，然后基于该不动点方程发展了算法，并证明了算法的全局收敛性。数值实验结果表明提出的模型与算法比现有方法得到更精确的复原效果。