稀疏優(yōu)化問(wèn)題算法研究

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

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

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

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

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

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

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

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

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

實(shí)際上，（4）、（5）和（6）對(duì)于適當(dāng)?shù)膮?shù)、和是等價(jià)的。

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

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

（一）貪婪算法

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

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

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

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

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

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

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

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

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

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

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

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

（三）閾值類算法

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

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

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

其中，。

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

在該算法的基礎(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等提出的。通過(guò)引入目標(biāo)函數(shù)的代理函數(shù)，將問(wèn)題轉(zhuǎn)化為求解代理函數(shù)的優(yōu)化問(wèn)題，利用代理函數(shù)的可分離性質(zhì)，將問(wèn)題轉(zhuǎn)化為單變量?jī)?yōu)化問(wèn)題。當(dāng)時(shí)，由Soft閾值算法得到的迭代點(diǎn)列收斂到問(wèn)題（8）的最小點(diǎn)。Soft閾值算法對(duì)稀疏信號(hào)的重構(gòu)精度低，且收斂速度慢。

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

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

三、結(jié)論

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

參考文獻(xiàn)：

[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

作者簡(jiǎn)介：李蒙，陜西渭南人，渭南師范學(xué)院教師。