带稀疏约束不适定问题的算法研究

Ill-posed problem with sparse constraints has been attracted a lot of attentions in signal processing, machine learning, image restoration, statistics and parameter identification in recent years. By sparse regularization, ill-posed problem is transformed into a non-smooth optimization problem. A semi-smooth Newton (or primal dual active set) algorithm is applied to solve it. In each iteration, the active set is defined by the primal variable and its dual variable, then a small size optimization problem on the active set is solved to obtain a new primal variable, and its dual variable is updated. Due to the locally superlinear convergence property of Newton type algorithms, primal dual active set method is very efficient. Combining with continuation strategy on regularization parameter and a discrepancy principle, we can find a good initial guess for Newton method, and choose a proper regularization parameter simultaneously. We will study several typical ill-posed problems with sparse constraints, which include the sparsest solution of a underdetermined linear system, and parameter identification problem with a priori sparse information. The local and global convergences are established. The method can be further applied to real data problem.

具有稀疏先验信息的不适定问题在信号处理，机器学习，图像恢复，高维统计数据分析，微分方程参数识别等领域有着广阔的应用。本项目主要研究带稀疏约束的不适定问题，通过Tikhonov型稀疏正则化将不适定问题转化成为非光滑优化问题，并发展半光滑牛顿（或原始对偶积极集）算法来进行求解。该算法在每一步迭代过程中，通过原始变量和对偶变量定义积极集，然后在积极集上求解一个小规模的优化问题得到新的原始变量，并用它来更新对偶变量。因为牛顿型算法具有局部超线性收敛性，并且每一步迭代仅需要求解一个小规模的最小二乘问题，半光滑牛顿法具有很高的求解效率。为了给半光滑牛顿法提供好的初值，同时选取合适的正则化参数，我们对正则化参数使用连续化技术并配合差异原则进行停机。通过对若干具体问题如求欠定线性系统稀疏解或者带稀疏约束的参数识别问题的研究，我们将分析牛顿型算法的局部和全局收敛性，并将其应用于实际工程问题中。

具有稀疏先验信息的不适定问题在信号处理，机器学习，图像恢复，高维统计数据分析，微分方程参数识别等领域有着广阔的应用。本项目主要研究带稀疏约束的不适定问题，通过Tikhonov 型稀疏正则化将不适定问题转化成为非光滑优化问题，并发展高速有效的算法来进行求解。在该项目的支持下，我们完成了25篇学术论文，这些论文都发表于相关领域的主流SCI期刊中。