求解L0最小化問題的幾種方法

求解L0最小化問題的幾種方法一、引言在幾次課程實(shí)驗(yàn)中，以數(shù)獨(dú)問題為例介紹了L0問題的建模和將其松弛為L(zhǎng)1問題的方法。實(shí)際上，L0問題在圖像重建、稀疏信號(hào)恢復(fù)、特征提取、壓縮感知等諸多領(lǐng)域應(yīng)用廣泛,學(xué)界對(duì)該問題的求解也進(jìn)行了深入的研究。由于L0問題是典型的組合優(yōu)化問題，是非凸的，直接對(duì)其求解計(jì)算量太大。因此現(xiàn)有研究集中在對(duì)L0問題進(jìn)行轉(zhuǎn)化，將其松弛后進(jìn)行求解。典型的松弛方法是將其轉(zhuǎn)化為L(zhǎng)1問題⑴。文獻(xiàn)［2］以空間建模的方式說明L1問題是對(duì)L0問題最好的凸近似。前幾次課程實(shí)驗(yàn)中，也均通過求解 L1問題來獲得L0問題的解，從而實(shí)現(xiàn)數(shù)獨(dú)求解。然而使用L1問題來近似L0問題的求解仍存在一些問題：一個(gè)是L1問題與L0問題的等價(jià)性，即某些情況下L0問題近似為L(zhǎng)1問題時(shí)二者最優(yōu)解不相同；另一個(gè)存在于工程應(yīng)用中，即在噪聲環(huán)境下做信號(hào)恢復(fù)時(shí)， L1問題對(duì)噪聲比較敏感。特別針對(duì)數(shù)獨(dú)問題，由于可以確定稀疏水平為 81,這一先驗(yàn)條件也沒能應(yīng)用于優(yōu)化求解中。本文介紹了幾種求解L0范數(shù)最小化問題的方法，在不同程度上能夠避免或改善上述問題。下面分別予以描述。、L0問題概述及其L1近似考慮系統(tǒng)特征為NM的矩陣A，系統(tǒng)方程為Ax=b，其中b為輸出信號(hào)，x為輸入信號(hào)。L0問題即輸入信號(hào)的0范數(shù)最小化，是一種重要的信號(hào)重建的方法。如下所示：minX0s.t.Ax=b然而，直接對(duì)該問題進(jìn)行求解時(shí)NP難的。最典型的求解方法是考慮使用如下的L1問題進(jìn)行近似：minx1s.t.Ax=bL1問題是非凸的且存在一系列的線性優(yōu)化方法進(jìn)行求解。文獻(xiàn)［2］說明，L1問題是對(duì)L0問題最好的凸近似。因此，L1近似成為常用的L0問題求解方法。然而，L1問題與L0的等價(jià)性要求一定的條件，典型的條件包括零空間性質(zhì)( NullSpaceProperty,NSP和受限正交條件(RestrictedIsometryPrinciple,RIP)等⑶。在不滿足上述條件時(shí)，求解得到的 L1問題最優(yōu)解不再滿足0范數(shù)最小化，二者不等價(jià)。因此L1近似在求解此類情況時(shí)無法求解成功。此外，在存在噪聲的情況下進(jìn)行信號(hào)重建時(shí)， L1近似對(duì)方法對(duì)噪聲較為敏感，求

81,當(dāng)使用81,當(dāng)使用L1近似因此近年來又涌現(xiàn)出一大批不同的L0問題求解方法，他們有的是對(duì)L1近似的改進(jìn),有的是使用一種易于求解的函數(shù)去模擬L0問題，有的則根據(jù)L0問題的空間特征進(jìn)行求解。下面分別予以介紹。三、加權(quán)L1近似L1問題與L0問題的主要區(qū)別在于目標(biāo)函數(shù)不同， 分別為輸入分量的L1范數(shù)和L0范數(shù)，如下所示：=0-0|x||Tc,G=J0，Xi11y X.，X=0可以看出，二者的主要區(qū)別在于x各個(gè)分量的尺度不同，L0范數(shù)將尺度統(tǒng)一變?yōu)?后加起來，而L1范數(shù)則保留原來的尺度不變相加，這樣導(dǎo)致了二者目標(biāo)函數(shù)的差距。直觀上看，最好的改進(jìn)方法應(yīng)該是將 L1范數(shù)中大的分量變小，即使用加權(quán)的方法將 L1范數(shù)中各個(gè)分量平均化，轉(zhuǎn)化為如下所示：可以看出，使用與分量大小成反比例的權(quán)值，轉(zhuǎn)化為分量幅度均勻的向量的 L1范數(shù)，即可使L1范數(shù)與L0范數(shù)最大的近似。理想的權(quán)值設(shè)置為:1,*丸wi::,*=0參考加權(quán)L0范數(shù):WXI。，XWXI。，Xj=°〔J"1,X"可以看出，由于Wx0=x0,則相比x1Wx1與x0更為近似F面以圖解的方式來描述加權(quán) L1法的優(yōu)點(diǎn)"2111考慮一個(gè)三維的輸入信號(hào)x0=[010]t,系統(tǒng)特征為&=J ，考慮從輸出112y=?x°二[11]t恢復(fù)*0。如下圖所示，黑線圍成的三維塊內(nèi)表示L1范數(shù)小于等于1的“球”范圍，紅線表示y=&x約束，x0位于二者交點(diǎn)處，為一個(gè)解。從圖 1(b)可以看

出，如果紅線與“球”范圍相交，其相交線上的解均為可行解，此時(shí)取在L1范數(shù)最小值點(diǎn)X*二[1/301/3]t，該值成為L(zhǎng)1問題的解，卻不是對(duì)應(yīng)L0問題的解。在圖1(c)中可知，取權(quán)值矩陣為W二diag[313]t，加權(quán)L1問題由于W使L1范數(shù)“球”范圍得到調(diào)整，使得其與約束條件不再相交，從而得到正確的解。(a) (b) (c)圖1L1最小化問題空間示意圖可以看出，W具有一定的可行取值范圍，只要在這一范圍內(nèi)，均可保證加權(quán) L1問題解的唯一性。當(dāng)然，W仍需滿足與輸入分量大小成反比的規(guī)律。下面給出一種迭代更新的方法來獲得可行的W值。算法步驟如下所示：1、設(shè)迭代次數(shù)m為0,初始權(quán)值為w0=1,i=1川，n；3、根據(jù)上一步求得的最優(yōu)解更新權(quán)值: Wm12、求解Wm加權(quán)L1最小化問題：Xm=argmin||wmx|3、根據(jù)上一步求得的最優(yōu)解更新權(quán)值: Wm1琴|(zhì)+&4、若收斂或達(dá)到最大迭代次數(shù)，停止；否則將m加1后跳至步驟2繼續(xù)執(zhí)行。；的添加是為了加入擾動(dòng)保障得到最優(yōu)的解。 ；的經(jīng)驗(yàn)值一般以略小于最優(yōu)解的最小幅度為佳。以上迭代方法可以隨著迭代的進(jìn)行將大幅度分量找出來并通過加權(quán)將其幅度縮小，以便后續(xù)將小的非零分量也找出來，從而提高信號(hào)恢復(fù)的準(zhǔn)確度。四、平滑近似法平滑近似法[5,6]的主要思想是使用一個(gè)平滑函數(shù)來近似 L0范數(shù)，從而可以使用梯度方法進(jìn)行求解，并且該方法對(duì)噪聲不敏感。下面對(duì)平滑近似法進(jìn)行簡(jiǎn)要介紹。0x=0定義函數(shù)'(X) ，則X的L0范數(shù)可寫作：l1,xH0nX，\"xji—顯然L0范數(shù)的不連續(xù)性主要來源于函數(shù) (x)的不連續(xù)性，因此只要找到對(duì)..(x)的平滑近似，即可得到對(duì)L0范數(shù)的平滑近似?？紤]如下函數(shù)：f;：(x)=exp—x2.2匚2我們得到：因此也f』x)=1—v(x)，定義Fy(X)=Lf/N)，則有所以L0范數(shù)最小化問題可以轉(zhuǎn)化為 x)的最大化問題。其中二取值越小，近似效果越好；匚取值越大，平滑程度越高。在二取值非常小的情況下，L0范數(shù)最小化問題轉(zhuǎn)化為：maxF;_(x)s.tAx=b然而，匚較小時(shí)，F(xiàn)--(x)有很多局部極大值，因此很難直接求解得到最大值。而隨著二變大，F(xiàn)；：?(x)變得越來越平滑，當(dāng)二足夠大時(shí)，F(xiàn)-(x)不再有局部極值。因此，對(duì)limF_(x)最大化問題的求解思路為：首先在足夠大的 -時(shí)使用最速下降法獲得最優(yōu)解，—0然后逐漸減小匚并在上一步最優(yōu)解的附近獲取極值解作為最優(yōu)解。由于 ；「值變化較慢,最速下降法的初始值始終在最大值附近，因此該問題陷入局部極值點(diǎn)的可能性比較小。一種具體的求解步驟如下所示：1、 初始化：選擇Ax=b的最小均方解七作為x的初始值，并為二選擇一個(gè)遞減序列［6,6,川，匚」，其中K為迭代次數(shù)。2、 對(duì)k=1,2,|l|,K循環(huán)：令，x〃心在可行集？：：x|Ax=b｝上使用最速下降法求解R-(x)的最大化問題并迭代J次：對(duì)j=1,2J||,J循環(huán):

令x=令x=%exp—x;2「2山，xexp2匚k;令x：_X-'「X,其中二為較小的正常數(shù);將x投影到可行集？上：x「x_AtAAt一Ax_b。3、令Vk=x。迭代完成后，取VK作為最優(yōu)解。該方法由于使用了另外一種對(duì)L0范數(shù)的近似方法，因此避免了L1近似法中由于等價(jià)條件不滿足導(dǎo)致的求解錯(cuò)誤的問題。此外，平滑近似也提高了對(duì)噪聲的魯棒性。五、正交匹配追蹤法正交匹配追蹤法(OrthogonalMatchingPursuit,OMP)是一種貪婪迭代算法。在該方法中，將系統(tǒng)特征矩陣A的各個(gè)列看作各個(gè)測(cè)量向量，則輸出信號(hào) b為輸入信號(hào)中非零分量對(duì)應(yīng)的各個(gè)測(cè)量向量的線性組合，即只有這些測(cè)量向量對(duì) b的形成做了貢獻(xiàn)。OMP的思想是使用貪婪算法將這些測(cè)量分量找出來。 每個(gè)迭代周期，將對(duì)b的剩余部分貢獻(xiàn)最大的列找出來，然后從該剩余部分中減去它貢獻(xiàn)的部分并在剩余部分中繼續(xù)迭代。考慮輸入信號(hào)的稀疏水平(非零分量的個(gè)數(shù))為d，則算法希望經(jīng)過d次循環(huán)后將正確的列辨識(shí)出來。下面詳細(xì)描述OMP算法的步驟。1、初始化：剩余部分『°二b，非零分量索引集合上。工必，已選定列向量集合Qe,迭代索引為t=1。2、找出對(duì)rtA貢獻(xiàn)最大的列向量的索引三，即求解如下優(yōu)化問題:Nargmax(—訓(xùn)j出ll,M-其中商為矩陣A的第j列。3、更新非零分量索引集合上t=-'町t't』及已選定列向量集合Q二札。4、根據(jù)已選定向量集合求解一個(gè)輸入信號(hào)的最小均方估計(jì)， 即求解如下優(yōu)化問題：舄二argmin|Qtx「b25、 求解已找出的列向量貢獻(xiàn)的分量，得到at二Qtxt；求解剩余分量，得到rt二b-at6、 將t加1,若t::4,返回步驟2。最終得到上m的各個(gè)值即為輸入信號(hào)中非零分量的索引，輸入信號(hào)第 k個(gè)分量的值

即為Xm第k個(gè)分量的值Qt正交，因此，每次迭從步驟3、4、5可知，剩余分量rQt正交，因此，每次迭代均能選出新的非零分量，從而實(shí)現(xiàn)算法的意圖。從文獻(xiàn)［7］的分析可以看出，OMP算法的時(shí)間復(fù)雜度要小于基于線性優(yōu)化的L1近似法，然而，相比于L1近似法，OMP算法缺少可證明的求解性能，無法獲取理論上的正確率。后續(xù)的改進(jìn)包括分段式OMP算法、正規(guī)化OMP算法等，六、總結(jié)六、總結(jié)本文分析了使用線性優(yōu)化方法求解L1近似的L0最優(yōu)化時(shí)存在的問題，并介紹了加權(quán)L1近似法、平滑近似法和匹配追蹤法三種不同思想的L0優(yōu)化問題解法，這三種方法相比線性求解的L1近似法各有優(yōu)點(diǎn)，可應(yīng)用于不同的場(chǎng)景，也為L(zhǎng)0優(yōu)化問題的求解打開了思路，有助于對(duì)L0優(yōu)化問題各個(gè)性質(zhì)的進(jìn)一步研究。參考文獻(xiàn)S.S.Chen,D.L.Donoho,andM.A.Saunders.“AtomicDecompositionbyBasisPursuit,SIAMJournalonScientificComputing,vol.20,pp.33-61,1998.Ramirez,Carlos,VladikKreinovich,andMiguelArgaez."Whyl1isaGoodApproximationtol0:AGeometricExplanation."JournalofUncertainSystems,2013:203-207.HuiZhang,WotaoYin,LizhiCheng."Necessaryandsufficientconditionsofsolutionuniquenessinl1minimization."Journalofoptimizationtheoryandapplications,2015,164(1):109-122.Candes,EmmanuelJ.,MichaelB.Wakin,andStephenP.Boyd."Enhancingsparsitybyreweighted?1minimization."JournalofFourieranalysisandapplications14.5-6(2008):877-905.G.H.Mohimani,M.Babaie-Zadeh,andC.Jutten,“Fastsparserepresentationbasedonsmoothedl0norm,”7thinInternationalConferenceonIndependentComponentAnalysisandSignalSeparation,2007,pp.389-396.Hyder,Mashud,andKaushikMahata."AnapproximateL0normminimizationalgorithmforcompressedsensing."Acoustics,Spee