稀疏优化问题算法研究

摘要：稀疏优化问题发展至今，已经广泛应用于压缩感知、图像处理、复杂网络、指数追踪、变量选择等领域，并取得了令人瞩目的成就。稀疏优化问题的求解算法种类繁多，根据算法设计原理的不同，可将其大致分为三类：贪婪算法、凸松弛方法和阈值类算法。本文主要介绍稀疏优化问题算法研究进展及各类算法的优缺点。

关键词：稀疏优化问题；压缩感知；信号重构；优化算法

随着当代社会信息技术的飞速发展，所获取和需要处理的数据量大幅增多，而基于传统的香农奈奎斯特采样定理中要求采样频率不得低于信号最高频率的两倍才可以精确重构信号。2006年，Donoho、Candes等人针对稀疏信号或可稀疏表示的信号提出了新的采集和编解码理论，即压缩感知理论。该理论使得通过少量采样即可准确或近似重构原始信號。信号重构问题是一个非凸稀疏优化问题（问题）。该问题是一个NP-hard问题，所以出现了多种不同的处理模型近似地或在一定条件下等价地求解问题。以下就从压缩感知的信号重构理论出发，分析研究稀疏优化问题的模型和求解算法。

一、压缩感知重构问题

在压缩感知理论中，若信号本身是稀疏的，则原始信号和观测信号之间的表达式为：；若信号本身不是稀疏的，但在基底下具有稀疏表示，即，其中是一个稀疏向量，则原始信号和观测信号之间的表达式为：，此时，重构原始信号只需要得到满足该等式约束的稀疏解，便可通过得到原始信号，其中为测量矩阵，为变换矩阵，为感知矩阵。

在压缩感知理论中，感知矩阵是一个很重要的组成部分，感知矩阵的好坏会直接影响原始信号的重构质量。压缩感知理论中的稀疏信号重构问题旨在通过低维观测数据最大程度恢复出原始的高维信号，其本质为求一个欠定方程组的稀疏解，即 （1）

压缩感知的重构问题也可通过下述模型来求解：（2）

Donoho和Chen证明了当观测矩阵和变换矩阵不相关时，（1）和（2）的解等价，并将（2）称为基追踪（Basis Pursuit，BP）问题。该模型在有噪声情形下可推广为基追踪去噪（Basis Pursuit Denoise，BPDN）问题（3）

其中，是噪声水平。也可推广为统计学领域的约束优化问题LASSO（Least Absolute Shrinkage and Selection Operator）（4）或者（5）

实际上，（4）、（5）和（6）对于适当的参数、和是等价的。

二、非凸稀疏优化问题算法

稀疏问题发展至今，已经提出了多种不同的处理模型和求解算法。根据算法设计原理的不同，可将其大致分为三类：贪婪算法、凸松弛方法和阈值类算法。下面就按该分类展开对稀疏优化问题求解算法的讨论，并分析每种算法的优越性及不足。

（一）贪婪算法

贪婪算法主要包括各类匹配追踪类算法，用于求解问题（1）。

1993年，Mallat和Zhang提出匹配追踪（Matching Pursuit， MP）算法，该算法最初应用于信号稀疏分解问题。MP算法的主要思想是：每一步迭代中，选择感知矩阵中与信号残差的内积绝对值最大的列进入指标集，更新信号残差。该算法思想简单，但重构精度不高。

1993年，Pati等人提出正交匹配追踪（Orthogonal Matching Pursuit，OMP）算法。2007年，Tropp和Gilbert将该算法应用于压缩感知领域。OMP算法在MP算法的基础上增加了正交化处理，使得在当前指标集下得到的解是最优的。OMP算法几乎对所有的稀疏信号都可以实现精确重构，且如果信号是稀疏的，通过OMP算法只需迭代次就可以确定出信号非零项的位置。

2009年，Needell和Tropp提出压缩采样匹配追踪（Compress Sample Matching Pursuit， CoSaMP）算法。该算法通过在每步迭代中把贡献较小的项从指标集中移除，克服了StOMP算法中对支撑集的过估计问题。如果测量矩阵满足限制等距同构性质，通过CoSaMP算法即可重构原始信号。

2012年，Donoho和Tsaig等提出分段正交匹配追踪（Stagewise Orthogonal Matching Pursuit， StOMP）算法。该算法通过设定阈值来确定进入指标集中的元素， OMP算法每次迭代指标集只增加一项，而StOMP算法每次迭代会选择多个元素进入指标集。StOMP算法提高了收敛速度，但是对解的支撑集的探测存在过估计的问题，且阈值的设定是难点。

除此之外，还有很多求解问题（1）的匹配追踪类算法，比如弱匹配追踪（Weak Matching Pursuit， W-MP）算法、正则化正交匹配追踪（Regularizaed Orthogonal Matching Pursuit， ROMP）算法、分段弱正交匹配追踪（Stagewise Weak Orthogonal Matching Pursuit， SWOMP）算法等。

（二）凸优化方法

通过将问题松弛为问题，信号重构问题则转化为凸优化问题。

1997年，Gorodnisky和Rao针对问题（1）提出FOcal欠定系统求解算法（Focal Underdetermined System Solver， FOCUSS）。该算法利用迭代重加权最小二乘方法用一个加权范数代替范数。对于任意初始点，通过FOCUSS算法得到的迭代点列渐进收敛到一个不动点。

1998年，Chen和Donoho针对问题（2）提出基追踪算法（Basis Pursuit， BP）。该算法的思想是：引入正部负部概念，将问题（2）等价转化为线性规划（Linear Programming， LP）问题，通过线性规划的方法来求解。

2004年，Efron、Tibshirani等針对问题（4）提出最小角回归算法（Least Angle Regression， LARS）。最小角回归算法不仅计算量小，而且精度高，适用于小规模问题。

2005年，Adeyemi和Davies针对问题（4）提出收缩迭代加权最小二乘算法（Iterative Reweighed Least Squares-Based Shrinkage， IRLS- Based Shrinkage）。该算法基于IRLS算法通过引入权重项将非范数项转化为范数项，将问题（4）转化为一个简单二次函数的极小化问题，利用不动点迭代方法，即可建立迭代收缩算子。

（三）阈值类算法

阈值类算法的思想是：在迭代过程中设定一个阈值参数，通过该阈值参数控制信号非零元素的个数，保留信号中绝对值大于该阈值参数的项，而剩余项则置零，最终使得信号满足稀疏性约束。阈值类算法算法思想简单，对满足一定条件的信号重构效果很好，且大多都有理论保证。缺点是对感知矩阵要求较高，且收敛速度较慢。这里主要讨论Hard阈值算法、Soft阈值算法和Half阈值算法。

Hard阈值算法（Iterative Hard Thresholding，IHT）用于处理如下优化模型：（6）

该算法在2007年由Blumensat和Davies提出。该算法解的迭代格式为：（7）

其中，。

Blumensat和Davies在2008年证明了如果，则由（7）产生的迭代点列收敛到问题（6）的局部最小点。

在该算法的基础上还发展出了稀疏Hard阈值算法（Sparse Iterative Hard Thresholding， ）、Hard阈值追踪算法（Hard Thresholding Pursuit， HTP）和快速Hard阈值追踪算法（Fast Hard Thresholding Pursuit， FHTP）等。

Soft阈值算法（Iterative Soft Thresholding， IST）用于处理如下优化模型：（8）

该算法是在2004年由Daubechies等提出的。通过引入目标函数的代理函数，将问题转化为求解代理函数的优化问题，利用代理函数的可分离性质，将问题转化为单变量优化问题。当时，由Soft阈值算法得到的迭代点列收敛到问题（8）的最小点。Soft阈值算法对稀疏信号的重构精度低，且收敛速度慢。

Half阈值算法（Iterative Half Thresholding）用于处理如下优化模型：（9）

该算法是在2010年由徐宗本等提出的。徐宗本等针对稀疏性问题提出了一个全新的框架：正则化，建立了一般非凸正则化理论。与正则化相比，正则化不仅可以保证快速求解，而且具有更好的稀疏性和稳健性，拥有广泛的应用价值。将Half阈值算法应用于Sar图像重构，可实现在远低于奈奎斯特采样速率采样下对典型稀疏大场景的非模糊成像，其所需要的采样速率比Soft阈值算法所需要的采样速率少一半。

三、结论

通过压缩感知理论的重要组成部分——信号重构，引入稀疏问题，因为原始信号重构模型是一个NP-Hard问题，难以求解，所以给出不同的信号重构模型。从压缩感知的信号重构问题的角度出发讨论稀疏优化问题的求解算法，基于不同的算法设计原理，将算法大致分为三类：贪婪算法、凸松弛方法和阈值类方法。对比算法之间设计的差异性及表现效果的不同，分析算法的优点和不足，从整体上了解稀疏优化问题求解算法的研究进展。

参考文献：

[1] Donoho DL. Compressed sensing[J]. IEEE Transactions on Information Theory， 2006， 52（4）： 1289-1306

[2] Candès E J. Compressive sampling[C]//Proceedings of the international congress of mathematicians. 2006， 3： 1433-1452

[3] Donoho D L， Huo X. Uncertainty principles and ideal atomic decomposition[J]. IEEE transactions on information theory， 2001， 47（7）： 2845-2862

[4] Donoho DL. Maximal sparsity representation via l1 minimization[J]. Proceedings of the National Academy of Sciences， 2003， 100： 2197-2202

[5] Tibshirani R. Regression shrinkage and selection via the Lasso[J]. Journal of the Royal Statistical Society. Series B（Methodological）， 1996， 58： 267-288

[6] Chen S S， Donoho D L， Saunders M A. Atomic decomposition by basis pursuit[J]. SIAM review， 2001， 43（1）： 129-159

[7] Mallat S， Zhang Z. Matching pursuit with time-frequency dictionaries[J]. IEEE Transactions on Signal Processing， 1993， 41（12）： 3397-3415

[8] Tropp JA， Gilbert AC. Signal recovery from random measurements via orthogonal matching pursuit[J]. IEEE Transactions on Information Theory， 2007， 53（12）： 4655-4666

[9] Needell D， Tropp JA. CoSaMP： Iterative signal recovery from incomplete and inaccurate samples[J]. Applied and Computational Harmonic Analysis， 2009， 26（3）： 301-321

[10] Donoho DL， Tsaig Y， Drori I， et al. Sparse solution of underdetermined systems of linear equations by stagewise orthogonal matching pursuit[J]. IEEE Transactions on Information Theory， 2012， 58（2）： 1094-1121

[11] Gorodnisky IF， Rao BD. Sparse signal reconstruction from limited data using FOCUSS： A re-weighted norm minimization algorithm[J]. IEEE Transactions on Signal Processing， 1997， 45（3）： 600-616

[12] Efron B， Hastie T， Johnstone IM， et al. Least angle regression[J]. The Annals of Statistics， 2004， 32（2）： 407-499

[13] Adeyemi T， Davies M. Sparse representations of images using overcomplete complex wavelets[C]//Statistical Signal Processing， 2005 IEEE/SP 13th Workshop on. IEEE， 2005： 865-870

[14] Blumensath T， Yaghoobi M， Davies ME. Iterative hard thresholding and l0 regularization[C]. Honolulu： IEEE International Conference on Acoustics， Speech and Signal Processing（ICASSP）， 2007， 3： 877-880

[15] Blumensath T， Davies ME. Iterative thresholding for sparse approximations[J]. Journal of Fourier Analysis and Applications， 2008， 14（5-6）： 629-654

[16] Daubechies I， Defrise M， De MC. An iterative thresholding algorithm for linear inverse problems with a sparsity constraint[J]. Communications on Pure and Applied Mathmatics， 2004， 57（11）： 1413-1457

[17] Xu Z， Zhang H， Wang Y， et al. L 1/2 regularization[J]. Science China Information Sciences， 2010， 53（6）： 1159-1169.

[18] Zeng JS， Xu ZB， Jiang H， et al. SAR imaging from compressed measurements based on L1/2 regularization[C]. IEEE International Geoscience and Remote Sensing Symposium（IGARSS）， 2011： 625-628

作者簡介：李蒙，陕西渭南人，渭南师范学院教师。