图像复原中非凸稀疏优化问题的快速算法

Image restoration is one of the fundamental and important areas of the imaging science. Recently, sparse representation based image restoration approaches are widely spread and achieve great success. Solving the corresponding sparse optimization problems becomes a very crucial issue in the sparse based image restoration methods and is now a hot research topic in the applied and computational mathematics. In this project, we study three categories of nonconvex sparse optimization problems arising from image restoration. The first category of problems comes from the sparsity based approaches for non-blind image restoration. The problems are nonconvex due to the nonconvex sparse promoting functions involved. For example, the L0 or Lp（0<p<1）norm. The second category of problems mainly comes from the sparsity based methods for blind image deconvolution. The problems are nonconvex since the fidelity terms involve the convolution of two variables. The third category of problems is large scale nonconvex sparse optimization problems which involve high dimensional images or large scale matrices We aim at developing fast and accurate optimization algorithms for these three classes of problems.

图像复原是图像处理学科最基本与最重要的领域之一。近年来，基于稀疏表示的图像复原方法广泛地应用在图像复原问题中，并取得了很大的成功。快速求解对应的稀疏优化问题是基于稀疏表示的图像复原方法中的核心，也是目前国内外应用与计算数学界研究的热点问题。在本项目中，我们研究图像复原中三类非凸稀疏优化问题的快速算法，这三类优化问题均不能由现有的算法很好地求解。第一类优化问题产生基于稀疏表示的图像非盲复原问题，其特点是含有非凸稀疏度量函数，如L0模或Lp（0<p<1）模；第二类优化问题来自基于稀疏表示的图像盲复原方法，其非凸性是由于数据拟合项含有两个变量的卷积；第三类是大规模图像复原非凸稀疏问题，其问题的特点在于含有高维图像或者大规模矩阵。本项目的目标在于对这三类优化问题提出快速而准确的优化算法。

近年来，基于稀疏表示的图像复原方法广泛地应用在图像复原问题中，并取得了很大的成功。非凸稀疏优化问题的求解是基于稀疏表示图像复原方法的核心问题之一。本项目主要研究图像复原应用背景下若干类常见的非凸稀疏优化问题，研究内容包括这些非凸稀疏优化问题的理论，算法及应用。我们的研究结果可分为两部分。第一部分主要研究图像复原中常见的以零范数为目标函数的约束优化问题。我们对其罚函数方法进行了深入研究，给出了构造精确罚函数方法的充分条件。并提出了一类精确罚函数方法，其罚函数问题可以被直接而快速求解。第二部分主要研究图像复原领域中的复合零范数稀疏优化问题。该优化问题由两部分组成，一部分为数据拟合项，另一部分为复合了仿射变换的零范数。针对这种类型的优化问题，我们提出了一种新的求解算法。首先，将仿射变换与L0函数分离，转换为一个线性约束。其次，使用平方函数为罚函数，把问题转化为无约束优化问题。我们证明了，只要数据拟合项满足一定条件，当罚因子趋近于无穷时，罚问题的最优函数值收敛至原问题的最优函数值，罚问题的最优解趋向于原问题的最优解。特别地，当数据拟合项为零函数或者有界闭集上的示性函数时，只要罚因子充分大，罚问题的最优解集就严格等于原问题的最优解集。这些结果说明我们的算法是可靠而稳定的。