摘要：稀疏優(yōu)化問題發(fā)展至今，已經(jīng)廣泛應(yīng)用于壓縮感知、圖像處理、復雜網(wǎng)絡(luò)、指數(shù)追蹤、變量選擇等領(lǐng)域，并取得了令人矚目的成就。稀疏優(yōu)化問題的求解算法種類繁多，根據(jù)算法設(shè)計原理的不同，可將其大致分為三類：貪婪算法、凸松弛方法和閾值類算法。本文主要介紹稀疏優(yōu)化問題算法研究進展及各類算法的優(yōu)缺點。

關(guān)鍵詞：稀疏優(yōu)化問題；壓縮感知；信號重構(gòu)；優(yōu)化算法

隨著當代社會信息技術(shù)的飛速發(fā)展，所獲取和需要處理的數(shù)據(jù)量大幅增多，而基于傳統(tǒng)的香農(nóng)奈奎斯特采樣定理中要求采樣頻率不得低于信號最高頻率的兩倍才可以精確重構(gòu)信號。2006年，Donoho、Candes等人針對稀疏信號或可稀疏表示的信號提出了新的采集和編解碼理論，即壓縮感知理論。該理論使得通過少量采樣即可準確或近似重構(gòu)原始信號。信號重構(gòu)問題是一個非凸稀疏優(yōu)化問題（問題）。該問題是一個NP-hard問題，所以出現(xiàn)了多種不同的處理模型近似地或在一定條件下等價地求解問題。以下就從壓縮感知的信號重構(gòu)理論出發(fā)，分析研究稀疏優(yōu)化問題的模型和求解算法。

一、壓縮感知重構(gòu)問題

在壓縮感知理論中，若信號本身是稀疏的，則原始信號和觀測信號之間的表達式為：；若信號本身不是稀疏的，但在基底下具有稀疏表示，即，其中是一個稀疏向量，則原始信號和觀測信號之間的表達式為：，此時，重構(gòu)原始信號只需要得到滿足該等式約束的稀疏解，便可通過得到原始信號，其中為測量矩陣，為變換矩陣，為感知矩陣。

在壓縮感知理論中，感知矩陣是一個很重要的組成部分，感知矩陣的好壞會直接影響原始信號的重構(gòu)質(zhì)量。壓縮感知理論中的稀疏信號重構(gòu)問題旨在通過低維觀測數(shù)據(jù)最大程度恢復出原始的高維信號，其本質(zhì)為求一個欠定方程組的稀疏解，即 （1）

壓縮感知的重構(gòu)問題也可通過下述模型來求解：（2）

Donoho和Chen證明了當觀測矩陣和變換矩陣不相關(guān)時，（1）和（2）的解等價，并將（2）稱為基追蹤（Basis Pursuit，BP）問題。該模型在有噪聲情形下可推廣為基追蹤去噪（Basis Pursuit Denoise，BPDN）問題（3）

其中，是噪聲水平。也可推廣為統(tǒng)計學領(lǐng)域的約束優(yōu)化問題LASSO（Least Absolute Shrinkage and Selection Operator）（4）或者（5）

實際上，（4）、（5）和（6）對于適當?shù)膮?shù)、和是等價的。

二、非凸稀疏優(yōu)化問題算法

稀疏問題發(fā)展至今，已經(jīng)提出了多種不同的處理模型和求解算法。根據(jù)算法設(shè)計原理的不同，可將其大致分為三類：貪婪算法、凸松弛方法和閾值類算法。下面就按該分類展開對稀疏優(yōu)化問題求解算法的討論，并分析每種算法的優(yōu)越性及不足。

（一）貪婪算法

貪婪算法主要包括各類匹配追蹤類算法，用于求解問題（1）。

1993年，Mallat和Zhang提出匹配追蹤（Matching Pursuit， MP）算法，該算法最初應(yīng)用于信號稀疏分解問題。MP算法的主要思想是：每一步迭代中，選擇感知矩陣中與信號殘差的內(nèi)積絕對值最大的列進入指標集，更新信號殘差。該算法思想簡單，但重構(gòu)精度不高。

1993年，Pati等人提出正交匹配追蹤（Orthogonal Matching Pursuit，OMP）算法。2007年，Tropp和Gilbert將該算法應(yīng)用于壓縮感知領(lǐng)域。OMP算法在MP算法的基礎(chǔ)上增加了正交化處理，使得在當前指標集下得到的解是最優(yōu)的。OMP算法幾乎對所有的稀疏信號都可以實現(xiàn)精確重構(gòu)，且如果信號是稀疏的，通過OMP算法只需迭代次就可以確定出信號非零項的位置。

2009年，Needell和Tropp提出壓縮采樣匹配追蹤（Compress Sample Matching Pursuit， CoSaMP）算法。該算法通過在每步迭代中把貢獻較小的項從指標集中移除，克服了StOMP算法中對支撐集的過估計問題。如果測量矩陣滿足限制等距同構(gòu)性質(zhì)，通過CoSaMP算法即可重構(gòu)原始信號。

2012年，Donoho和Tsaig等提出分段正交匹配追蹤（Stagewise Orthogonal Matching Pursuit， StOMP）算法。該算法通過設(shè)定閾值來確定進入指標集中的元素， OMP算法每次迭代指標集只增加一項，而StOMP算法每次迭代會選擇多個元素進入指標集。StOMP算法提高了收斂速度，但是對解的支撐集的探測存在過估計的問題，且閾值的設(shè)定是難點。

除此之外，還有很多求解問題（1）的匹配追蹤類算法，比如弱匹配追蹤（Weak Matching Pursuit， W-MP）算法、正則化正交匹配追蹤（Regularizaed Orthogonal Matching Pursuit， ROMP）算法、分段弱正交匹配追蹤（Stagewise Weak Orthogonal Matching Pursuit， SWOMP）算法等。

（二）凸優(yōu)化方法

通過將問題松弛為問題，信號重構(gòu)問題則轉(zhuǎn)化為凸優(yōu)化問題。

1997年，Gorodnisky和Rao針對問題（1）提出FOcal欠定系統(tǒng)求解算法（Focal Underdetermined System Solver， FOCUSS）。該算法利用迭代重加權(quán)最小二乘方法用一個加權(quán)范數(shù)代替范數(shù)。對于任意初始點，通過FOCUSS算法得到的迭代點列漸進收斂到一個不動點。

1998年，Chen和Donoho針對問題（2）提出基追蹤算法（Basis Pursuit， BP）。該算法的思想是：引入正部負部概念，將問題（2）等價轉(zhuǎn)化為線性規(guī)劃（Linear Programming， LP）問題，通過線性規(guī)劃的方法來求解。

2004年，Efron、Tibshirani等針對問題（4）提出最小角回歸算法（Least Angle Regression， LARS）。最小角回歸算法不僅計算量小，而且精度高，適用于小規(guī)模問題。

2005年，Adeyemi和Davies針對問題（4）提出收縮迭代加權(quán)最小二乘算法（Iterative Reweighed Least Squares-Based Shrinkage， IRLS- Based Shrinkage）。該算法基于IRLS算法通過引入權(quán)重項將非范數(shù)項轉(zhuǎn)化為范數(shù)項，將問題（4）轉(zhuǎn)化為一個簡單二次函數(shù)的極小化問題，利用不動點迭代方法，即可建立迭代收縮算子。

（三）閾值類算法

閾值類算法的思想是：在迭代過程中設(shè)定一個閾值參數(shù)，通過該閾值參數(shù)控制信號非零元素的個數(shù)，保留信號中絕對值大于該閾值參數(shù)的項，而剩余項則置零，最終使得信號滿足稀疏性約束。閾值類算法算法思想簡單，對滿足一定條件的信號重構(gòu)效果很好，且大多都有理論保證。缺點是對感知矩陣要求較高，且收斂速度較慢。這里主要討論Hard閾值算法、Soft閾值算法和Half閾值算法。

Hard閾值算法（Iterative Hard Thresholding，IHT）用于處理如下優(yōu)化模型：（6）

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

其中，。

Blumensat和Davies在2008年證明了如果，則由（7）產(chǎn)生的迭代點列收斂到問題（6）的局部最小點。

在該算法的基礎(chǔ)上還發(fā)展出了稀疏Hard閾值算法（Sparse Iterative Hard Thresholding， ）、Hard閾值追蹤算法（Hard Thresholding Pursuit， HTP）和快速Hard閾值追蹤算法（Fast Hard Thresholding Pursuit， FHTP）等。

Soft閾值算法（Iterative Soft Thresholding， IST）用于處理如下優(yōu)化模型：（8）

該算法是在2004年由Daubechies等提出的。通過引入目標函數(shù)的代理函數(shù)，將問題轉(zhuǎn)化為求解代理函數(shù)的優(yōu)化問題，利用代理函數(shù)的可分離性質(zhì)，將問題轉(zhuǎn)化為單變量優(yōu)化問題。當時，由Soft閾值算法得到的迭代點列收斂到問題（8）的最小點。Soft閾值算法對稀疏信號的重構(gòu)精度低，且收斂速度慢。

Half閾值算法（Iterative Half Thresholding）用于處理如下優(yōu)化模型：（9）

該算法是在2010年由徐宗本等提出的。徐宗本等針對稀疏性問題提出了一個全新的框架：正則化，建立了一般非凸正則化理論。與正則化相比，正則化不僅可以保證快速求解，而且具有更好的稀疏性和穩(wěn)健性，擁有廣泛的應(yīng)用價值。將Half閾值算法應(yīng)用于Sar圖像重構(gòu)，可實現(xiàn)在遠低于奈奎斯特采樣速率采樣下對典型稀疏大場景的非模糊成像，其所需要的采樣速率比Soft閾值算法所需要的采樣速率少一半。

三、結(jié)論

通過壓縮感知理論的重要組成部分——信號重構(gòu)，引入稀疏問題，因為原始信號重構(gòu)模型是一個NP-Hard問題，難以求解，所以給出不同的信號重構(gòu)模型。從壓縮感知的信號重構(gòu)問題的角度出發(fā)討論稀疏優(yōu)化問題的求解算法，基于不同的算法設(shè)計原理，將算法大致分為三類：貪婪算法、凸松弛方法和閾值類方法。對比算法之間設(shè)計的差異性及表現(xiàn)效果的不同，分析算法的優(yōu)點和不足，從整體上了解稀疏優(yōu)化問題求解算法的研究進展。

參考文獻：

[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

作者簡介：李蒙，陜西渭南人，渭南師范學院教師。