稀疏優化問題算法研究

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

關鍵詞：稀疏優化問題；壓縮感知；信號重構；優化算法

隨著當代社會信息技術的飛速發展，所獲取和需要處理的數據量大幅增多，而基于傳統的香農奈奎斯特采樣定理中要求采樣頻率不得低于信號最高頻率的兩倍才可以精確重構信號。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

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