于春梅

YU Chunmei

西南科技大學(xué)信息工程學(xué)院,四川 綿陽，621010

Southwest University of Science and Technology, Mianyang, 621010, Sichuan, China

引言

Nyquist采樣定理表明：要精確重建信號(hào)，采樣頻率必須大于等于信號(hào)最高頻率的兩倍.由于很多信號(hào)在時(shí)域、頻域或空域是稀疏的；也就是說在大多數(shù)情況下，信息存在冗余，即可以通過正交變換的方法進(jìn)行壓縮.那么，是否可以直接獲取信號(hào)的壓縮表示，而非冗余表示，使其在信息不損失的前提下，用低于Nyquist采樣定理的要求對(duì)信號(hào)或者圖像進(jìn)行采樣，同時(shí)又可以完全重構(gòu)信號(hào)？這就是近年來吸引了從數(shù)學(xué)領(lǐng)域到信號(hào)處理、圖像處理、測(cè)量、控制等各個(gè)工程領(lǐng)域科技人員的壓縮感知問題，或壓縮傳感問題.該問題最核心的概念在于試圖使壓縮和采樣同時(shí)進(jìn)行，從而極大降低測(cè)量成本.

近年來美國著名學(xué)者Donoho 和Candès等根據(jù)信號(hào)的分解和逼近理論提出了壓縮感知理論,為該問題提供了可能的解決方案.Candès等[1,2]從數(shù)學(xué)上證明：可以從部分傅立葉變換系數(shù)中精確重構(gòu)原始信號(hào)，而Donoho[3]則以Nyquist-Shannon-Whittaker定理、Heisenberg測(cè)不準(zhǔn)原理、Fourier投影以及優(yōu)化理論為基礎(chǔ)，提出了壓縮感知的概念.Candès和Donoho證明：如果原始信號(hào)或圖像的某一正交變換是稀疏的，則可以通過合適的優(yōu)化算法，由少量采樣值或測(cè)量值來重構(gòu)信號(hào)或圖像.該理論是傳統(tǒng)信息論的延伸，使得信息理論進(jìn)入了一個(gè)新的研究階段.本文試圖對(duì)稀疏求解算法做一個(gè)梳理，從最基本的優(yōu)化問題到一些變形和適用范圍，然后側(cè)重對(duì)稀疏優(yōu)化算法進(jìn)行分類和分析，并給出最新的發(fā)展現(xiàn)狀.

1 壓縮感知的基本問題

傳統(tǒng)的和基于壓縮感知的信號(hào)采樣、傳輸和恢復(fù)過程框架分別如圖 1a和圖 1b所示。

在圖1b中，只需測(cè)量信號(hào)x的少量采樣 y，因而無需壓縮和解壓縮環(huán)節(jié).圖 1b中各環(huán)節(jié)關(guān)系如下：y=Φx，其中y：M維測(cè)量信號(hào)，Φ：M*N測(cè)量矩陣,x：N維原始信號(hào)；s=Ψx，s：n維稀疏變換信號(hào)，Ψ:稀疏變換矩陣；稀疏反變換x=Ψ-1s，則y=Φx=ΦΨ-1s=Ds，s中只有k個(gè)非零元素，稱為k稀疏的，D稱為字典矩陣.

圖1 信號(hào)采樣、傳輸和恢復(fù)過程框圖Fig.1 Signal sampling, transmission and recovery

基于壓縮感知的思路是：在測(cè)量矩陣Φ和稀疏變換矩陣Ψ已知的情況下，由信號(hào)的 M個(gè)測(cè)量y來重構(gòu)原始N維信號(hào)x，這里的關(guān)鍵是：如果信號(hào)s足夠稀疏，那么對(duì)于y的M個(gè)測(cè)量就可以重構(gòu)N維原始信號(hào)。這個(gè)問題可以由以下的優(yōu)化問題來描述：這里 l0范數(shù)指向量中非零元素的個(gè)數(shù).求解該優(yōu)化問題也即根據(jù)測(cè)量向量y求解滿足測(cè)量關(guān)系（x與 y之間）和稀疏變換關(guān)系（x與s之間）的最稀疏向量s.一旦稀疏向量s求出，即可以由稀疏反變換重構(gòu)原始信號(hào)x.根據(jù)以上的思路，我們可以得出壓縮感知理論包含的主要內(nèi)容：測(cè)量矩陣的設(shè)計(jì)；信號(hào)的稀疏表示；稀疏重構(gòu)問題，即滿足一定數(shù)目的測(cè)量值的條件下尋求最稀疏解的過程.

限于篇幅，本文側(cè)重于第3個(gè)問題，即式（1）優(yōu)化問題的求解，這也是壓縮感知理論的核心內(nèi)容.式(1)是一個(gè)典型的 NP難問題，需要窮舉s中所有非零項(xiàng)位置的種排列的可能，這是相當(dāng)困難的.Donoho和Chen[4,5,6]證明了在變換矩陣與觀測(cè)矩陣不相關(guān)的條件下l0范數(shù)和l1范數(shù)的解等價(jià)，這樣NP難的優(yōu)化問題可以轉(zhuǎn)化為l1范數(shù)最小化問題，或稱之為基追蹤（Basis Pursu it，BP）問題

也正是基于此，l1范數(shù)優(yōu)化問題成為解決稀疏求解問題的主要方法.對(duì)于對(duì)有噪聲情形，該問題推廣為基追蹤去噪（Basis Pursuit Denoise，BPDN）問題

其中，σ為數(shù)據(jù)的噪聲水平.或者在統(tǒng)計(jì)學(xué)領(lǐng)域的 l1范數(shù)約束下的優(yōu)化問題 LASSO（Least Absolute Shrinkage and Selection Operator）[7]

或者

實(shí)際上，（3）、（4）和（5）在適當(dāng)λ、σ和q參數(shù)下是等價(jià)的[7]，不少文獻(xiàn)并未區(qū)分二者.式（4）中l(wèi)2范數(shù)項(xiàng)稱為保真項(xiàng)，l1范數(shù)項(xiàng)稱為正則項(xiàng).

除了松弛為 l1范數(shù)，Gorodnitsky等[8]還提出用lp范數(shù)（0＜p＜1）代替l0范數(shù)來進(jìn)行重構(gòu)，非凸但結(jié)果比l1范數(shù)更稀疏.

2 與基本問題相關(guān)的稀疏優(yōu)化問題

可以看出，信號(hào)重構(gòu)問題即對(duì)信號(hào)的l0范數(shù)、l1范數(shù)或者 lp（0＜p＜1）范數(shù)的最小化問題.不少學(xué)者針對(duì)一些具體問題，又在上述基本優(yōu)化問題的基礎(chǔ)上，提出了適合各類不同問題的優(yōu)化問題.Candes和 Tao[9]提出LASSO的稍許變化版本Dantzig selector

以適應(yīng)變量數(shù)p遠(yuǎn)大于觀測(cè)n時(shí)的情形.與LASSO不同的是，該優(yōu)化模型最小化誤差平方梯度向量的最大值，而不是誤差的平方,其對(duì)變量選擇問題特別有效.

全變分（total variation, TV）模型可以看成是對(duì)一維情形的推廣，其最初由Rudin等[12]提出用于圖像去噪，后被推廣到其他圖像處理問題，該問題也通常稱作ROF問題.

其中，TV有兩種定義，一種為各向同性TV（isotropic TV）

另一種為各向異性TV（anisotropic TV）

這兩種模型在圖像去噪的同時(shí)又能保持圖像邊緣，因而在圖像修復(fù)、重構(gòu)等方面都有良好表現(xiàn).各向異性TV適合圖像特征明顯的區(qū)域，但對(duì)于平滑區(qū)域容易產(chǎn)生階梯效應(yīng)而影響效果；各向同性TV則適合圖像特征不明顯的區(qū)域.

以TV為基礎(chǔ)，He等[13]提出

與Tibshirani等[14]提出融合LASSO（fused LASSO）

類似，使不僅系數(shù)稀疏，其差也盡量稀疏，適于特征排列有序的情形.Zou等[15]則提出彈性網(wǎng)（elastic net）

使強(qiáng)相關(guān)的預(yù)測(cè)子傾向于同時(shí)在模型中出現(xiàn)或消失，適用于預(yù)測(cè)子的數(shù)量比觀測(cè)數(shù)量大得多的情形，并提出LARS-EN算法求解該問題.

歸納起來，稀疏優(yōu)化問題如圖 2所示.至于選擇何種類型的優(yōu)化則依賴于具體問題.對(duì)于一般的信號(hào)重構(gòu)問題，基本的BPDN或者LASSO就可以；對(duì)于變量數(shù)大于觀測(cè)數(shù)的情形，Dantzig selector更適合；對(duì)于圖像的修復(fù)或者重構(gòu)問題，全變分模型可作為首選；如果數(shù)據(jù)類型呈現(xiàn)組相關(guān)，采用分組 LASSO就比較適合；融合 LASSO則適合特征排列有序的情形.如果想得到比l1范數(shù)更稀疏的結(jié)果，可以將這些問題中的l1范數(shù)以 lp范數(shù)（0＜p＜1）代替.讀者還可以根據(jù)問題特點(diǎn)設(shè)計(jì)特定的優(yōu)化目標(biāo)函數(shù).

圖2 稀疏優(yōu)化問題Fig.2 Sparse optimization problems

3 典型的優(yōu)化算法和定性比較

由于稀疏優(yōu)化算法種類繁多，對(duì)其分類并非十分容易.即便如此，還是有不少作者試圖對(duì)其進(jìn)行總結(jié)，文獻(xiàn)[16]將其分為l0范數(shù)下的非凸、l1范數(shù)和lp范數(shù)下的松弛；文獻(xiàn)[17]分為最小l1范數(shù)法、匹配追蹤系列算法、迭代閾值法以及專門處理二維圖像問題的最小全變分法；文獻(xiàn)[18]則將重構(gòu)算法分為貪婪算法、凸優(yōu)化方法和組合算法.文獻(xiàn)[19]基追蹤算法、貪婪算法和迭代閾值法.但筆者認(rèn)為，這些分類有些過于籠統(tǒng)，有些則不夠全面.本文從不同的角度，將重構(gòu)算法分為活動(dòng)集方法、迭代投影算子法和經(jīng)典凸規(guī)劃法，各方法的特點(diǎn)如圖3所示.

圖3 典型優(yōu)化算法及定性比較Figure3 Optimization algorithms and qualitative comparison

3.1 活動(dòng)集方法

活動(dòng)集方法是一種逐步構(gòu)造最優(yōu)解的方法，即逐步選擇解集合，最終逼近最優(yōu)解.與傳統(tǒng)的單純型法、內(nèi)點(diǎn)法等從稠密解開始，迭代求最優(yōu)解的方法不同，一般這類算法都是從空集開始，逐步得到稀疏解.活動(dòng)集方法分為兩種，一種是求解特定正則參數(shù)下的最優(yōu)解，主要有貪婪算法；一種是序貫方法，有同倫算法和LARs.

貪婪算法是解決優(yōu)化問題的一種基本方法，它將全局優(yōu)化問題轉(zhuǎn)化為逐步構(gòu)造最優(yōu)解的過程；在每一步都求出一個(gè)在當(dāng)前階段的最優(yōu)解，而不考慮這種選擇在全局看來是否最優(yōu).貪婪算法主要包括各類匹配追蹤（Matching Pursuit ，MP）算法.

MP算法的基本思想是在每一次的迭代過程中，從過完備原子庫里(即字典矩陣D中)選擇與信號(hào)殘差最為接近的原子作為匹配原子來構(gòu)建稀疏逼近，經(jīng)過一定次數(shù)的迭代，信號(hào)可以表示為部分原子的線性組合.由于在這些原子組成的子空間上，信號(hào)的投影并非正交，因此可能需要迭代多次算法才能收斂.針對(duì)此，文獻(xiàn)[20]提出了正交匹配追蹤(Orthogonal Matching Pursuit，OMP)算法，該算法與MP算法采用相同的原子選擇準(zhǔn)則，不同之處在于每一步迭代中都增加了對(duì)所選原子進(jìn)行正交化處理的步驟，以減少迭代次數(shù).

MP和OMP算法在每步迭代中都要計(jì)算信號(hào)殘差在字典矩陣中的每一列上的投影，計(jì)算量大，收斂速度也比較慢.Donoho等[21]于2006年提出的逐步正交匹配追蹤(Stagewise Orthogonal Matching Pursuit，StOMP)算法，改善了這一狀況，收斂速度有所提高.

正則化OMP(Regularized OMP,ROMP)[22]是第一個(gè)用約束等距性條件 RIP界進(jìn)行分析的貪婪技術(shù)；文獻(xiàn)[23]則每次迭代選擇多列.壓縮采樣匹配追蹤(Compressive sampling matching pursuit,CoSaMP)[24]提供了比 OMP、ROMP更全面的理論保證, 并且能在采樣過程中對(duì)噪聲魯棒；除了極端稀疏的情形CoSaMP比OMP更快更有效.Dai等[25]基于回溯策略提出一個(gè)相似的算法叫子空間追蹤(subspace pursuit, SP)，但該算法不是自適應(yīng)于信號(hào)稀疏度的，因此其重構(gòu)精度仍然不夠理想.為了進(jìn)一步提高重構(gòu)精度,文獻(xiàn)[26]提出了稀疏自適應(yīng)匹配追蹤(sparsity adaptive matching pursuit, SAMP)算法.該算法自適應(yīng)于信號(hào)稀疏度，重構(gòu)精度也得到了相應(yīng)提高.

在這些貪婪算法中，MP、OMP、ROMP以及StOMP算法的支撐集都是在迭代過程中不斷增加且不會(huì)剔除已選原子；但SP、CosaMP算法在迭代過程中為保證支撐集大小的不變必須剔除一部分原子.

序貫方法沿整個(gè)正則化路徑求解，常用的有同倫（homotopy）和最小角回歸（Least angle regression，LARs）.同倫是指隨著λ增大，LASSO的目標(biāo)函數(shù)從l2約束轉(zhuǎn)為l1約束.對(duì)于LASSO問題，式（4）λ≥0或式（5）q≥0的解路徑是多邊形的，而且，解路徑的頂點(diǎn)對(duì)應(yīng)解子集.子集為分段常數(shù)，為λ或q的函數(shù)，僅在λ或q的關(guān)鍵值（對(duì)應(yīng)解路徑的頂點(diǎn)）發(fā)生變化.這個(gè)演變的子集（evolving subset）叫做有效集（active set），基于此提出的同倫算法沿著解路徑從一個(gè)頂點(diǎn)跳到另一個(gè)頂點(diǎn)，開始于空的有效集在每個(gè)頂點(diǎn)，通過添加或移出變量來更新有效集.對(duì)于k稀疏問題，同倫算法在k步找到最優(yōu)解[27].

從算法的角度講，LARs可以看成去除了符號(hào)限制的同倫算法，不同之處在于同倫算法允許進(jìn)入也允許離開有效集，這點(diǎn)不同使其可以嚴(yán)格求解全局最優(yōu)問題；但這也意味著同倫算法所需的步數(shù)比LARs要多.但有證據(jù)表明，在很多情況下，同倫算法與LARs和OMP同樣快[28].

LARs與OMP結(jié)構(gòu)相似，區(qū)別在于OMP每一步迭代求解最小二乘問題，LARs則求解線性懲罰的最小二乘問題.事實(shí)上，LARs和同倫，在每次迭代中都采用了一種貪婪選擇策略.LARs的成功除了它漂亮的幾何性質(zhì)之外，還有它的快速算法.

3.2 迭代投影算子法

迭代投影算子法形式上均表現(xiàn)為迭代求解過程，同時(shí)增加了在可行集的投影.迭代投影算子法由于計(jì)算簡單，適用于高維大規(guī)模問題而深受廣大學(xué)者的青睞，成為求解稀疏優(yōu)化問題最有效的算法類，這其中包括閾值迭代法和各種算子分離法等.

閾值迭代法分為軟閾值迭代（iterative soft-thresholding）和硬閾值迭代（iterative hard-thresholding）兩種.二者均通過非線性算子進(jìn)行迭代，軟閾值迭代通過一個(gè)閾值參數(shù)來確定迭代中保留的項(xiàng)；而硬閾值迭代通過一個(gè)固定閾值進(jìn)行迭代，每次迭代中保留相同數(shù)目的項(xiàng).Blumensath等[29]提出了求解近似l0問題的硬閾值迭代算法.硬閾值的性能在一定條件下有很強(qiáng)的理論保證，但一旦某些條件不滿足，則性能明顯下降，甚至算法不收斂.文獻(xiàn)[30]提出改進(jìn)的硬閾值算法，保證算法的收斂性，速度更快且理論保證與原算法類似.Daubechies等[31]提出了求解l1問題的軟閾值迭代算法，并給出了收斂性證明.文獻(xiàn)[32]提出了軟閾值迭代的快速算法FISTA.除此之外，軟迭代閾值方法還常用于較復(fù)雜優(yōu)化問題的子過程.這些復(fù)雜的問題通?？梢苑纸鉃橐恍┖唵蔚淖訂栴}，其中的一個(gè)基本子問題LASSO可由軟迭代閾值方法求解.

除了軟閾值和硬閾值迭代，徐宗本團(tuán)隊(duì)[32-36]提出了求解l1/2問題的迭代閾值法，Half和Chalf閾值迭代算法，并將l1/2范數(shù)用于Sar圖像重構(gòu)，所需采樣速率比l1范數(shù)低一半[37]，他們[38]還對(duì)目前已知的五大類閾值迭代算法Hard，Soft，SCAD，Half，Chalf，進(jìn)行了分析比較，得出了很多有益的結(jié)論.文獻(xiàn)[39]則結(jié)合Bregman迭代由p收縮算子求解lp范數(shù)問題，.

前向后向算子分離法（Forward backward splitting, FBS）將優(yōu)化問題分解為簡單子問題的迭代求解，每一次迭代分解為僅對(duì)保真項(xiàng)的前向(顯式)步與僅對(duì)正則項(xiàng)的后向(隱式)步，無需求解整個(gè)目標(biāo)函數(shù)的鄰近算子，同時(shí)能夠有效利用隱式方法的優(yōu)點(diǎn)，從而大幅度降低計(jì)算復(fù)雜性，是凸分析中一種有效的折中方法，具有很好的收斂性[40].固定點(diǎn)（fixed-point）迭代和Bregman迭代均屬于前后向分離算法，不同之處在于Bregman迭代用Bregman距離代替了優(yōu)化目標(biāo)中的正則項(xiàng).

固定點(diǎn)迭代和線性Bregman迭代非常有效，但只能求解目標(biāo)函數(shù)為l1范數(shù)+ l2范數(shù)的基本問題，對(duì)含TV的問題、含多個(gè)l1范數(shù)的問題以及其它更復(fù)雜的優(yōu)化問題無法求解.針對(duì)此，不少作者使用分離算子，將Bregman迭代、接近點(diǎn)算子與軟閾值算子結(jié)合使用，將研究不斷向前推進(jìn).文獻(xiàn)[41]用線性濾波和迭代軟閾值兩個(gè)簡單子過程求解ROF模型對(duì)兩類TV均可解；文獻(xiàn)[42]用算子分離方法求解l1范數(shù)、l2范數(shù)、l∞范數(shù)正則以及l(fā)1/lq混合范數(shù)正則；Ma等[43]應(yīng)用算子分離方法解決式（11），將優(yōu)化條件分離為兩部分，對(duì)其變形，并用固定點(diǎn)迭代fixed-point iterations算法求解[44]；文獻(xiàn)[45]采用序貫方法加速計(jì)算過程.與原-對(duì)偶算法比較，結(jié)果差不多，但速度快3倍[46].

分離Bregman（split Bregman）算法引入新變量來實(shí)施約束并松弛，并增加關(guān)于新增變量的迭代步驟，可求解更為廣泛的問題.文獻(xiàn)[47]基于Bregman迭代提出分離Bregman迭代方法，取得了較好的效果，但沒有給出收斂性證明.文獻(xiàn)[48]將算法用于全變分優(yōu)化問題，并給出了算法的收斂性分析和證明.變量分離方法與分離Bregman迭代非常相似，也引入新變量，不同之處在于用增廣拉格朗日乘子來松弛目標(biāo)函數(shù).文獻(xiàn)[49]用變量分離方法求解式（11）的優(yōu)化問題，比分離Bregman迭代計(jì)算代價(jià)低，迭代次數(shù)少.文獻(xiàn)[50]用變量分離方法，比傳統(tǒng)的非線性共軛梯度法和分離Bregman迭代收斂快.

算子分離算法中的第二個(gè)子步需要確定稀疏性懲罰函數(shù)的鄰近算子，對(duì)于大多數(shù)稀疏優(yōu)化問題，軟閾值迭代簡單有效，在優(yōu)化求解中得到了廣泛應(yīng)用.坐標(biāo)下降法（coordinate descent）也常用來求解算子分離算法的子問題，其基本思路是一次優(yōu)化一個(gè)參數(shù)（坐標(biāo)），輪流循環(huán)，將復(fù)雜優(yōu)化問題分解為簡單的子問題，進(jìn)而得出形式簡單的分步迭代算法，比傳統(tǒng)方法更易計(jì)算.該算法是迄今為止求解LASSO問題最快的算法，通常也稱為FFT（Friedman + Fortran +Tricks）算法[51].

除了以上提到的算法，我們還經(jīng)常看到鄰近算子法、增廣拉格朗日法、交錯(cuò)投影法等.這些算法也可以看成一類投影算子方法，他們之間在一些條件下相互聯(lián)系或具有等價(jià)性[52].鄰近算子為凸投影算子的推廣，凸投影算子和軟閾值算子均為鄰近算子[53]；增廣拉格朗日與線性約束的 Bregman迭代等價(jià)，又與對(duì)偶的鄰近算子法聯(lián)系；交錯(cuò)投影法與線性約束下的分離 Bregman迭代法等價(jià)，在某些條件下也與梯度投影法等價(jià)，且都可以歸結(jié)為框架收縮方法[52].需要說明的是，雖然梯度投影法顯然可以歸于該類，但是由于習(xí)慣上將其看成傳統(tǒng)梯度法的推廣，因而本文將其歸于經(jīng)典的凸規(guī)劃方法；而坐標(biāo)下降法實(shí)際也是一種經(jīng)典無約束優(yōu)化方法，希望不至引起混淆.實(shí)際上從這一點(diǎn)也可以看出，各種方法之間存在著千絲萬縷的聯(lián)系，這也是導(dǎo)致稀疏優(yōu)化算法分類困難的原因之一.

3.3 經(jīng)典凸規(guī)劃方法

凸優(yōu)化問題是指目標(biāo)函數(shù)為凸函數(shù)，約束變量取值于凸集中的優(yōu)化問題.經(jīng)典的用于解決該問題的方法包括內(nèi)點(diǎn)法、牛頓法、梯度法，以及由梯度法推廣而來的次梯度法和梯度投影法、次梯度投影法.內(nèi)點(diǎn)法通過使用牛頓法求解一系列無約束優(yōu)化問題來得到凸優(yōu)化問題的解，在迭代的每一步中解總是可行的，因此稱為內(nèi)點(diǎn)法.一般來說，如果可以將優(yōu)化問題轉(zhuǎn)化為線性規(guī)劃 LP、二次型規(guī)劃QP、二階錐規(guī)劃SOCP或者半正定規(guī)劃SDP，則很容易由這些經(jīng)典的方法等求解.正是基于這樣的思路，文獻(xiàn)[54]將LASSO變形為二次規(guī)劃問題，用內(nèi)點(diǎn)法求解LASSO的對(duì)數(shù)障礙(log-barrier)形式，每一個(gè)搜索步由預(yù)調(diào)共軛梯度加速.文獻(xiàn)[55]和[56]則化為二階錐問題，由內(nèi)點(diǎn)法或牛頓法求解 BPDN問題.文獻(xiàn)[57-59]對(duì) LASSO或BP問題用內(nèi)點(diǎn)法在每一步的迭代中用共軛梯度 CG或最小二乘求解線性方程.文獻(xiàn)[60]提出的用于稀疏重構(gòu)的梯度追蹤GPSR(Gradient Pursuit for Sparse Reconstruction)算法先將 LASSO問題轉(zhuǎn)化為邊界約束的二次規(guī)劃問題 BCQP(bound-constrained quadratic programming)，再執(zhí)行梯度投影迭代來重構(gòu)圖像.文獻(xiàn)[61]采用迭代加權(quán)梯度投影算法恢復(fù)稀疏信號(hào)來求解大規(guī)模問題，速度快，且對(duì)原始信號(hào)的稀疏度不敏感.文獻(xiàn)[62]則提出了梯度投影算法的快速分解算法.文獻(xiàn)[63]采用子梯度尋找算法SFA來求解融合LASSO問題，并設(shè)計(jì)重啟動(dòng)技術(shù)來加速算法的收斂.

總之，對(duì)于稀疏優(yōu)化的基本問題BPDN或者 LASSO，軟閾值迭代和活動(dòng)集方法應(yīng)用最為廣泛，而對(duì)于比較復(fù)雜的優(yōu)化問題，雖然可以有其他的解決方案，但通常借助于算子分離方法簡化計(jì)算，其中的子問題通常包括LASSO和可微子問題.軟閾值迭代特別適合于算子分離方法的迭代過程，因而應(yīng)用特別廣泛.不僅如此，軟閾值迭代還可以推廣到求解lp范數(shù)的優(yōu)化問題，因而其應(yīng)用前景十分廣闊.也有不少學(xué)者嘗試將幾種不同的方法混合使用，文獻(xiàn)[64]在牛頓法迭代過程中用活動(dòng)集策略.文獻(xiàn)[65]先用共軛梯度法求解再用Bregman迭代優(yōu)化以求解式（11）,得到較好的MR重構(gòu)圖像.文獻(xiàn)[66]用同倫和坐標(biāo)下降法求解BPDN問題，文獻(xiàn)[67]采用遞歸自適應(yīng)算法求解分組LASSO問題，結(jié)合同倫方法降低計(jì)算復(fù)雜度.

實(shí)際上，正如文獻(xiàn)[16]所述，這些方法也可以分為直接求解 l0范數(shù)問題的貪婪追蹤法、閾值法和同倫算法，以及松弛為求解l1范數(shù)和lp范數(shù)的方法.一般來說，直接求解l0范數(shù)的方法速度很快，特別在極端稀疏的情形；而對(duì)于更廣泛的情形，比如信號(hào)不是特別稀疏、觀測(cè)噪聲較大等，凸松弛方法在處理稀疏逼近的問題上更有效.

4 總結(jié)與展望

本文將稀疏優(yōu)化算法大概分成3類，實(shí)際上，這3類方法在實(shí)際應(yīng)用時(shí)有時(shí)界限并不明顯.或者說幾種方法的綜合也通常是解決較復(fù)雜問題的有效方法.如迭代法與序貫方法結(jié)合，迭代法與梯度投影法結(jié)合，分離Bregman迭代與凸規(guī)劃和迭代閾值結(jié)合，內(nèi)點(diǎn)法結(jié)合共軛梯度、預(yù)調(diào)共軛梯度，或者增廣拉格朗日法結(jié)合坐標(biāo)下降法等等.在稀疏優(yōu)化問題上，結(jié)合最廣泛的要算閾值迭代法，因?yàn)榇蠖喾蛛x算法其中的一個(gè)迭代歸結(jié)為LASSO問題，而閾值迭代法作為一種簡單實(shí)用的求解算法而得到廣泛應(yīng)用.

隨著近幾年的迅猛發(fā)展，稀疏優(yōu)化問題已經(jīng)取得了令人矚目的成果，但尚有一些問題亟待改進(jìn)和完善，概括為以下幾個(gè)方面：（1）如何設(shè)計(jì)適用于噪聲情形下大尺度問題的快速優(yōu)化算法.眾所周知，噪聲廣泛存在于現(xiàn)實(shí)世界，抗噪性能的好壞關(guān)系到算法能否可靠應(yīng)用于實(shí)際問題；而高效、快速的優(yōu)化算法也是其廣泛應(yīng)用的前提；因而，如何設(shè)計(jì)計(jì)算復(fù)雜度較低、能有效處理大尺度問題且對(duì)噪聲不敏感的優(yōu)化算法是其能否有效應(yīng)用于實(shí)際的關(guān)鍵問題.（2）如何設(shè)計(jì)適應(yīng)特定應(yīng)用環(huán)境的優(yōu)化問題.壓縮感知在信號(hào)處理尤其是圖像重構(gòu)領(lǐng)域得到了廣泛的應(yīng)用，但在其他具有潛在應(yīng)用前景的領(lǐng)域如故障診斷、系統(tǒng)辨識(shí)以及其它與矩陣降秩相關(guān)的應(yīng)用領(lǐng)域似乎缺乏有力的例證.作者認(rèn)為這當(dāng)中要解決的首要問題是對(duì)于優(yōu)化目標(biāo)函數(shù)的設(shè)計(jì)，使其不僅適應(yīng)于具體問題、具有明確的物理含義，且能夠找到普適的、全局最優(yōu)的算法.（3）基于lp范數(shù)的稀疏優(yōu)化理論.目前，多數(shù)優(yōu)化算法是松弛為求解l1范數(shù)問題而設(shè)計(jì)的，對(duì)lp范數(shù)的優(yōu)化問題研究甚少；已有的研究表明[8,37]，lp范數(shù)可以得到更加稀疏的結(jié)果，所需采樣速率比l1范數(shù)低.但由于 lp范數(shù)數(shù)學(xué)性質(zhì)的非凸性使得對(duì)該問題的研究一直沒有突破性進(jìn)展.

[1]Candés E, Romberg J, Tao T.Robust uncertainty principles:Exact signal reconstruction from highly incomplete frequency information.IEEE Transactions on Information Theory, 2006,52(2):489-509

[2]Candés E.Compressive sampling.In:Proceedings of International Congress of Mathematicians. Zürich,Switzerland:European Mathematical Society Publishing House,2006.1433-1452

[3]Donoho D L.Compressed sensing.IEEE Transactions on Information Theory, 2006, 52(4):1289-1306

[4]Donoho,D.L., Huo,X.Uncertainty principles and ideal atomic decomposition.IEEE Transaction on Information Theory,2001, 47:2845-2862.

[5]Donoho,D.L., Elad,E.Maximal sparsity representation via l1minimization.In:Proceedings of the National Academy of Sciences.2003, 100:2197-2202.

[6]Chen,S., Donoho, D.L.,Saunders,M..Atomic decomposition by basis pursuit. SIAM J. on Scientific Computing,1998,20(1):33-61.

[7]Tibshirani, R..Regression shrinkage and selection via the Lasso.J.Royal Statist.Soc., B ,1996, 58 ,267-288.

[8]I.F.Gorodnitsky and B.D.Rao.Sparse signal reconstruction from limited data using focuss:A re-weighted norm minimization algorithm.IEEE Trans.On Signal Processing,1997, 45(3):600-616.

[9]Candes E, Tao T.The Dantzig selector:statistical estimation when p is much larger than n.Annals of Statistics.2007,35(6):2313–2351.

[10].Yuan M, Lin Y.Model selection and estimation in regression with grouped variables.Journal of the Royal Statistical Society, Series B.2006,68(1):49–67.

[11]Meier L, van de Geer S, Bühlman P.The group lasso for logistic regression.Journal of the Royal Statistical Society B.2008 ,70(1):53-71

[12]L.I.Rudin, S.J.Osher, and E.Fatemi, Nonlinear total variation based noise removal algorithms, Physica D, 1992,60:259-268.

[13]L.He, T.-C.Chang, S.Osher, T.Fang, P.Speier.MR image reconstruction by using the iterative refinement method and nonlinear inverse scale space methods.UCLA CAM Report 06-35, 2006.

[14]Robert Tibshirani and Michael Saunders, Saharon Rosset,, Ji Zhu and Keith Knight.Sparsity and smoothness via the fused lasso.J.R.Statist.Soc.B ,2005, 67(1):91-108

[15]Hui Zou and Trevor Hastie.Regularization and variable selection via the elastic net.J.R.Statist.Soc.B,2005, 67(2)Part 2:301–320

[16]焦李成,楊淑媛,劉芳,侯彪.壓縮感知回顧與展望, 電子學(xué)報(bào), 2011,39(7):1651-1662

[17]李樹濤,魏丹.壓縮傳感綜述.自動(dòng)化學(xué)報(bào),2009,35(11):1369-1377

[18]楊海蓉,張成,丁大為,韋穗.壓縮傳感理論與重構(gòu)算法, 電子學(xué)報(bào),2011,39(1):142-148

[19]戴瓊海,付長軍,季向陽.壓縮感知研究.計(jì)算機(jī)學(xué)報(bào),2011,34(3):425-434

[20]Tropp J, Gilbert A.Signal recovery from random measurements via orthogonal matching pursuit.Transactions on Information Theory, 2007, 53(12):4655-4666

[21]D.Donoho, Y.Tsaig, I.Drori, and J.C.Starck, Sparse solution of under determined(systems of) linear equations by stagewise orthogonal matching pursuit, IEEE Transactions on Information Theory,2012,58(2):1094-1121(2006preprint)

[22]Needell D, Vershynin R.Greedy signal recovery and uncertainty principles.In:Proceedings of the SPIE.Bellingham,WA:SPIE, 2008:68140J-12

[23]Joel A.Tropp, Stephen J.Wright.Computational Methods for Sparse Solution of Linear Inverse Problems.In:Proceedings of the IEEE, SPECIAL ISSUE ON APPLICATIONS OF SPARSE REPRESENTATION AND COMPRESSIVE SENSING, NewYork, USA:IEEE 2010,98(6):948-958

[24]Needell D, Tropp J A.CoSaMP:Iterative signal recovery from incomplete and inaccurate samples.Applied and Computational Harmonic Analysis,2009, 26(3):301-321.

[25]Dai W, Milenkovic O.Subspace pursuit for compressive sensing closing the gap between performance and complexity[EB/OL].2008-01-08.http:∥ www.dsp.rice.edu/cs

[26]Thong T D, Gan L.Sparsity adaptive matching pursuit algorithm for practical compressed sensing, In:42th Asilomar Conference on Signals, Systems and Computers, Pacific Grove ,USA,2008:581-587.

[27]David L.Donoho and Yaakov Tsaig.Fast Solution of l1-norm Minimization Problems When the Solution May be Sparse.IEEE transactions on information theory ,2008, 54(11)4789-4812

[28]B.Efron, T.Hastie, I.Johnstone, and R.Tibshirani, Least angle regression, Annals of Statistics, 2004, 32(2):407-499.

[29]Blumensath T and Davies M.Iterative Hard Thresholding for Compressed Sensing.Appl.Comp.Harm.Anal,2009.,27(3):265-274

[30]Blumensath T., Davies M.E.Normalized Iterative Hard Thresholding:Guaranteed Stability and Performance.IEEE Journal of Selected Topics in Signal Processing,2010,4(2):298-309

[31]Daubechies I, Mefrise M, and Mol C.An iteative thresholding algorithm for linear inverse problems with a sparse constraint.Communication on Pure and Applied Mathematics.2004, 57(11):1413-1457.

[32]Beck, Teboulle.A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems.SIAM Journal on Imaging Sciences,2009,2(1):183-202

[33]Zongben Xu, Xiangyu Chang, Fengmin Xu and Hai Zhang.l1/2Regularization :An iterative half thresholding algorithm,Thechnical Report, 2010:No.1001.Submitted to IEEE Trans,Image Processing.

[34]Xiangyu Chang, Zongben Xu, Jinshan Zeng and Chen Xu.Modified l1/2Regularization :An iterative chalf thresholding algorithm, Thechnical Report, 2010:No.1002.Submitted to IEEE Trans, Neural Networks.

[35]Zongben Xu, Hai Zhang, Yao wang, Xiangyu Chang.l1/2regularization.Sci China Ser F, 2010, 40(3):1-11。

[36]Zongben Xu.Data Modeling:Visual Psychology Approach and l1/2Regularization Theory.In:Proceedings of the International Congress of Mathematicians Hyderabad, India,Switzerland:European Mathematical Society Publishing House ,2010

[37]Jinshan Zeng, Zongben Xu,Hai Jiang, Bingchen Zhang, Wen Hong, Yirong Wu.SAR imaging from compressed measurements based on l1/2regularization.In:IEEE International Geoscience and Remote Sensing Symposium(IGARSS), 24-29 July 2011，Vancouver, BC，pp 625 - 628

[38]常象宇, 饒過, 吳一戎, 徐宗本.如何在壓縮感知中正確使用閾值迭代算法.中國科學(xué)2010,40(1)

[39] Rick Chartrand. FAST ALGORITHMS FOR NONCONVEX COMPRESSIVE SENSING:MRI RECONSTRUCTION FROM VERY FEW DATA.In:IEEE International Symposium on Biomedical Imaging(ISBI), From Nano to Macro June 28 2009-July 1 2009:262-265

[40]Combettes P L, Wajs V R.Signal recovery by proximal forward-backward splitting.Multiscale Modeling and Simulation,2006, 4(4):1168-1200

[41]Michailovich, O.V.An Iterative Shrinkage Approach to Total-Variation Image Restoration.IEEE Transactions on Image Processing, 2011,20(5):1281-1299

[42]John Duchi, Yoram Singer.Efficient Online and Batch Learning Using Forward Backward Splitting.Journal of Machine Learning Research, 2009,10():2899-2934

[43]S.Ma, W.Yin, Y.Zhang, and A.Chakraborty, An efficient algorithm for compressed MR imaging using total variation and wavelets, In:IEEE Conference on Computer Vision and Pattern Recognition, 2008, pp.1-8

[44]P.L.Lions and B.Mercier.Splitting algorithms for the sum of two nonlinear operators.SIAM Journal on Numerical Analysis,1979,16:964–979

[45]E.Hale, W.Yin, and Y.Zhang.A fixed-point continuation method for l1-regularization with application to compressed sensing. Rice University CAAM Technical Report TR07-07,2007

[46]Rick Chartrand, Brendt Wohlberg.TOTAL-VARIATION REGULARIZATION WITH BOUND CONSTRAINTS,Acoustics Speech and Signal Processing(ICASSP), In:IEEE International Conference on, Dallas, TX, 14-19 March 2010 766-769

[47]TOM GOLDSTEIN, STANLEY OSHER.THE SPLIT BREGMAN METHOD FOR L1REGULARIZED PROBLEMS.SIAM Journal on Imaging Sciences,2009,2(2):323-343.

[48]李亞峰,馮象初.L1投影問題的分裂 Bregman方法.電子學(xué)報(bào),2010,38(11):2471-2475

[49]Xiaojing Ye, Yunmei Chen, Feng Huang.Computational Acceleration for MR Image Reconstruction in Partially Parallel Imaging. IEEE Transactions on Medical Imaging,2011,30(5):1055-1063

[50]Ramani, S.，F(xiàn)essler, J.A.A Splitting-Based Iterative Algorithm for Accelerated Statistical X-Ray CT Reconstruction.IEEE Transactions on Medical Imaging,2012,31(3):677-688

[51]Friedman J, Hastie T, Hoefling H, Tibshirani R.Pathwise coordinate optimization. Annals of Applied Statistics.2007,2(1):302–332.

[52]S.Setzer.Split bregman algorithm,Douglas Rachford splitting and Frame Shrinkage,In:SSVM '09 Proceedings of the Second International Conference on Scale Space and Variational Methods in Computer Vision, Springer-Verlag Berlin,Heidelberg,2009,464-476

[53]PATRICK L.COMBETTES AND VAL′ERIE R.WAJS.SIGNAL RECOVERY BY PROXIMAL FORWARD-BACKWARD SPLITTING, Multiscale Model.Simul.2005,4(4):1168-1200

[54]Kim S, K Koh, M Lustig, S Boyd, and D Gerinvesky.A method for large-scale l1-regularized least squares problems with applications in signal processing and statistics.Tech.Report,Dept.of Electrical Engineering, Stanford University,2007 Available at www.stanford.edu/?boyd/l1_ls.html.

[55]E.J.Candes, J.Romberg, and T.Tao.Robust uncertainty principles:Exact signal reconstruction from highly incomplete frequency information.IEEE Trans.Inform.Theory, 2006,52:489- 509.

[56]E.Candes, J.Romberg and T.Tao.Stable signal recovery from incomplete and inaccurate information, Communications on Pure and Applied Mathematics, 2005,59, pp.1207–1233.

[57]B.Turlach, W.N.Venables, and S.J.Wright.Simultaneous variable selection, Technometrics, 2005, 27:349-363,.

[58]C.Paige and M.A.Saunders, LSQR:An algorithm for sparse linear equations and sparse least squares, ACM Transactions on Mathematical Software, 1982,8:43–71,

[59]S.J.Wright.Primal-Dual Interior-Point Methods,Philadelphia, PA,USA:SIAM Publications, 1997.

[60]M.Figueiredo, R.Nowak, and S.J.Wright, Gradient Projection for Sparse Reconstruction:Application to Compressed Sensing and Other Inverse Problems.IEEE Journal of Selected Topics in Signal Processing, 2007,1(4):586-597.

[61]Jun Deng, Guanghui Ren, Yansheng Jin and Wenjing Ning.Iterative Weighted Gradient Projection for Sparse Reconstruction. Information Technology Journal,2011,10(7):1409-1414

[62]Dan Wei, Shutao Li, Mingkui Tan, Fast Decomposed Gradient Projection Algorithm for Sparse Representation,JDCTA:International Journal of Digital Content Technology and its Applications, 2012, 6(2):76-84

[63]Jun Liu, Lei Yuan, Jieping Ye.An Efficient Algorithm for a Class of Fused Lasso Problems.In:KDD’10, July 25-28, 2010,Washington, DC, USA.

[64]Benedetta Morini, Margherita Porcelli, Raymond H.Chan.A reduced Newton method for constrained linear least-squares problems.Journal of Computational and Applied Mathematics,2010,233(9):2200-2212

[65]T C.Chang, L.He, T.Fang.MR Image Reconstruction from Sparse Radial Samples Using Bregman Iteration, Proc.Intl.Soc.Mag.Reson.Med.2006,14():696

[66]Chunshan Liu，Zakharov, Y.V，Teyan Chen.Broadband Underwater Localization of Multiple Sources Using Basis Pursuit De-Noising.IEEE Transactions on Signal Processing,2012,60(4):1708-1717

[67]Chen Y.，Hero A.Recursive l1,∞Group lasso.IEEE Transactions on Signal Processing,2012(preprint)