幾種壓縮感知算法

.1壓縮感知部分壓縮感知算法主要可分為三類：貪婪迭代算法、凸凸優(yōu)化（或最優(yōu)化逼近方法）和基于貝葉斯框架提出的重構(gòu)算法。由于第三類方法注重信號的時間相關(guān)性，不適合圖像處理問題，故目前的研究成果主要集中在前兩類中。目前已實現(xiàn)6中算法，分別為正交匹配追蹤法（OMP）、迭代硬閾值法（IHT）、分段正交匹配追蹤法（StOMP）、分段弱正交匹配追蹤法（SwOMP）、廣義正交匹配追蹤（GOMP）、基追蹤法（BP）。1.1正交匹配追蹤法（OMP）在正交匹配追蹤OMP中，殘差是總與已經(jīng)選擇過的原子正交的。這意味著一個原子不會被選擇兩次，結(jié)果會在有限的幾步收斂。OMP的算法如下（1）用x表示你的信號，初始化殘差e0=x；（2）選擇與e0內(nèi)積絕對值最大的原子，表示為e1；（3）將選擇的原子作為列組成矩陣①t，定義①t列空間的正交投影算子為產(chǎn)二尊（型'叫尸呼通過從e0減去其在①t所張成空間上的正交投影得到殘差e1；%二%-P%=（『-產(chǎn)）區(qū)口（4）對殘差迭代執(zhí)行（2）、（3）步；—%一尸4="尸），其中I為單位陣。需要注意的是在迭代過程中①t為所有被選擇過的原子組成的矩陣，因此每次都是不同的，所以由它生成的正交投影算子矩陣P每次都是不同的。（5）直到達到某個指定的停止準(zhǔn)則后停止算法。OMP減去的Pem是em在所有被選擇過的原子組成的矩陣①t所張成空間上的正交投影，而MP減去的Pem是em在本次被選擇的原子@m所張成空間上的正交投影。經(jīng)OMP算法重構(gòu)后的結(jié)果如下所示：算法的使用時間如下：

探查摘要基于口erforrnance時間于25-Jan-201S14:38:39生成■1由數(shù)名稱調(diào)用次數(shù)總時間，用3rT上總時間圖（:深色條帶=自用時間i0Mp1?C1.00750A97sOMP>0rn口512197.926s151.802s5aMTin10156346.124g46.124sirii2liow41.321sD.119sI41.03230.030smcwvgui40.974sD.965s,fnert10.962sD.230sfig「22C.490sD.459s10210s0.029sEirrhG口40.193sD.039s迭代硬閾值法（IHT）目標(biāo)函數(shù)為c認(rèn),z）=IIX-蚓.一|陽一切后+lly一司修||4>||?<1這里中的M應(yīng)該指的是M-sparse,S應(yīng)該指的是Surrogate。這里要求："k二之后我們利用式C?（y.z）a][貨一2yt（zt+?[x—湄㈣].對目標(biāo)函數(shù)進行變形。接著便是獲得極值點：利用該式進行迭代可以得到極值點，我們需要的是最小值。此時目標(biāo)函數(shù)的最小值就得到了。此時便得到我們需要的公式：c需（廣Z）5E[靖一2片儲+婢X—婢中明=￡->12-

i i我們要保證向量y的稀疏度不大于M,即"ylbWM,為了達到這一目標(biāo)，要保留最大的M項（因為是平方，所以要取絕對值absolutevalue）,剩余的置零（注意這里有個負(fù)號,所以要保留最大的M項）。IHT算法結(jié)果：

IHT算法使用時間如下:探封商要基于『Km麗a時間于18T 生成總時間日用1時間*總時1亙國（浜色鐫帶-自用時間）函函名珞鞫用次數(shù)IHT15.543s0.915￡im前22.591$0.220sIHTysJht5121.496?1.496simnq蟲DMLyP3r口心20.941s0.040s■stFA切石此埼CiskStr皿1E65450.060s■imageDi$口13yMm1idatePardm/2662840.519s■」ri口uF□rSrstialReF虐rmndrg20.52350.5269■in':■勺欣20.4S3s0.058s■EQfph叩40.489s0.126s■imdil自悒3口144350.037s■分段正交匹配追蹤法（StOMP）分段正交匹配追蹤（StagewiseOMP）也是由OMP改進而來的一種貪心算法，與CoSaMP、SP算法類似，不同之處在于CoSaMP、SP算法在迭代過程中選擇的是與信號內(nèi)積最大的2K或K個原子，而StOMP是通過門限閾值來確定原子。此算法的輸入?yún)?shù)中沒有信號稀疏度K，因此相比于ROMP及CoSaMP有獨到的優(yōu)勢。StOMP的算法流程：輸入：(1)〃＞＜朋的傳感矩陣/=0/(2)Hx1維觀測向量7(3)迭代次數(shù)S,默認(rèn)為10(4g限參數(shù)與,默認(rèn)為2.5輸出:(1)信導(dǎo)桶疏表示系數(shù)估計。(2)"xl推殘差飛=了-力色以下流程中：與表示殘差，：表示迭代次數(shù)，0表示空集，4表示每次迭代找到的索引(列序號)，人表示E次迭代的索引(列序號)集合(注意：設(shè)元素個數(shù)為&,一般有以工￡,因為每次迭代找到的索引分一般并非只含一個列序號)，勺表示矩陣/的第J列，4表示搜索引4選出的矩陣幺的列集合，名為必幻的列向量，符號」表示集合并運算，〈,,?)表示求向量內(nèi)積，。兒［?］表示求模值(絕對值).(1期始化e=月4=。，4=0/=1；⑵計皙〃=a加［K*］(即計菖選擇〃中大于門限77?的值,將這些值對應(yīng)力的列序號j構(gòu)成集合4(列序號集合)；(3向4=4.=4，4=4_］kJ,(forall/e〃)：若4=4_】(即無圻列被選中)則停止迭代進入第(7)步；(4)求y=48,的最小二乘解：1 m4-4町=14r4j'看產(chǎn)；，(5)更新殘差rt-y-Aj0j-y- \ ；(6)Z=2+1,如果MS則返回第⑵步繼續(xù)迭代，如果」＞￡或殘差/;二0則停止迭代迸入第⑺步；(7)重構(gòu)所得。在4處有其零項，其值分別為最后一次迭代所得8,經(jīng)StOMP經(jīng)StOMP算法重構(gòu)后的結(jié)果如下所示星始用就強年的圖續(xù)注i；得到&后，利用稀疏矩陣可得重構(gòu)信號x=注*從輸入?yún)?shù)中可以知道密算法并不需要已知信號稀疏度4；（文獻口］中32節(jié)第二段中提到"tOIlP苴法對稀疏度K依賴性很大，只有正濡估計了信號的稀琉鹿，才能耦碑重構(gòu)原始信號卻，本人對此觀點保留意見）注主在測鬢矩陣為隨機高斯矩陣的懵況下,第0步中的門腹落二勺丐，其中工,取信范圍一般為2Mg￡3,q= "，4表示上次送代計苴出的殘差,.M表示2范藪;注4；隨機高a測量矩陣如文獻⑶的in節(jié)式己-。所示，這里注意方差一定要是1/城（標(biāo)準(zhǔn)差為1/g7）,即XiaEab生成代碼為randru；XLXi網(wǎng)rt（XI）,這是因為第Q茜的痍子選釋是將傳感矩陣列向量與殘差的內(nèi)積向量元素與殘?差向量1范數(shù)的某倍數(shù)相比莪，對于前面的幾篇介紹的其它重構(gòu)售法此處無所謂，為保持一致此后盡量全浮原r俎?（乂2網(wǎng)仇。。來生成測筵矩陣.探查摘要基于peCmqncG時間于f 01S22,2328由散名稱總時間目用時間*.日時同圖〔深色條帶=自用時同「-TCiMP11.815sC.129￡imnhw21.23Ss0.09054D.866sC.030sn2*wdI凸。匕工白rvEFiqu「rrxiE)ttPl凸t40.789￡C.074￡elf20.715303255mor口hip40.322sC.O65s■strel『M自kEDibkLlr同1D.266s0.014s■imdi就匕30.255sC.0055■in'tSize20.180sC.018s■imopen1□J45M0.007s■分段弱正交匹配追蹤法（SwOMP）分段弱正交匹配追蹤（StagewiseWeakOMP）可以說是StOMP的一種修改算法，它們的唯一不同是選擇原子時的門限設(shè)置，這可以降低對測量矩陣的要求。我們稱這里的原子選擇方式為"弱選擇"（WeakSelection），StOMP的門限設(shè)置由殘差決定，這對測量矩陣（原子選擇）提出了要求，而SWOMP的門限設(shè)置則對測量矩陣要求較低（原子選擇相對簡單、粗糙）。SWOMP的算法流程：輸A（l）MxV的傳感矩陣A二造⑵Nxl維觀溯向量y選代很數(shù)￡,默認(rèn)為10（4）門陽參數(shù)a,欲認(rèn)為0.5輸出，U）信號稀疏表示系數(shù)估計?⑵mu維殘差個土尸-4&以下流程中；齊表示殘差，上表示迭代次數(shù)，。表示空篥，4表示每次迭代找到的索弓1（列序號），兒表示上次迭代的索弓1（列序號）集合〔注意：設(shè)元素個數(shù)為心，一般有二N3因為每飲迭代找到的索引4一殷并非只含一個列序號），》表示矩陣乂的第J列，4表示搜索引兒選出的矩陣力的列集合，同為口句的列向量，符號u表示集合并運苒,表示求向?堡內(nèi)積,口加卜］表示求模值（絕對值）.該算法的用時情況如下：該算法的用時情況如下：(1)初始化q=丸4==。，上-1s⑵計算"血(即計茸仁選擇用中大于門限容加值，將這些值對應(yīng)幺的列序號j構(gòu)成集合/(列序號集合卜(3)令4=4T2外4=41allyeJG)；若〃=41(即無新列被選中)則停止迭代進入第0停，(4)求尸二郎才的晨小二乘解：自"arg］njQi|卜一4可|二?34?衛(wèi)jG)更新殘差器-y--y-\A\1iS”=￡+l,如果￡MS則返回第Q)步雒續(xù)迭代，如果』＞￡或殘差門=0則停止選代進入第(7)步j(luò)0)重構(gòu)所得占在乙處有非零項，具值分別為最后一次迭代所得q.注h得到營后，利用稀疏矩陣可得重枸信號定二刀：注21文獻［1］中給出了第?②步中的11明窗二理max^bsO)),其中Q取值范圍一般為文獻⑶中式(13)與此門限設(shè)置不同，本人對此觀點保留意見.經(jīng)SwOMP算法重構(gòu)后的結(jié)果如下所示鼠也用攫甚于二FEmn匚已時間亍19-幅ar-2。，822:22:42生成函俄名稱調(diào)用次數(shù)總崛自用時第］,后時同圖條TfT=自用時l同）14.860s0.777s5122.957s1.172s一由kltiTiTW25691.369s1.369s'mshow20.845e0.055s■20.595s0.027e■mcvEgui20.513s0.596s■union30300.415s6075s■ujicnAU「icj「iR?二：『月30000.34150J13sRmerRhop40.246s0.050s11D.241s0.016s1廣義正交匹配追蹤法（GOMP）廣義正交匹配追蹤（GeneralizedOMP,gOMP）算法可以看作為OMP算法的一種推廣。OMP每次只選擇與殘差相關(guān)最大的一個，而gOMP則是簡單地選擇最大的S個。之所以這里表述為"簡單地選擇"是相比于ROMP之類算法的，不進行任何其它處理，只是選擇最大的S個而已。GOMP算法流程如下：輸入：口）血乂方的傳感矩陣』=中/⑵取xl維現(xiàn)測向量,信號的稀疏度K6）每次選擇的原子個數(shù)k默認(rèn)取值為K4若KB則默認(rèn)取1輸出:（1）信號稀疏表示系數(shù)估計3⑵NkI維殘差八二y-A亶句以下流程中；4表示殘差，￡表示迭代欷數(shù)，0表示空集，4表示上次迭代的索弓1（列序號）集合，4表示第泊欠迭代找到的索引（列序號。勺表示矩陣』的第J列，4表示搜索引兒選出的矩陣/的列集合［大小為MS的矩陣），珞為戰(zhàn)1的列向量，符號u表示集合并運算，〈?,?〉表示求向量內(nèi)積1

(D初始化勺==0，4=0/=L些值對應(yīng)，的列序號j溝成M合冊（列序號集合上(.3」(D初始化勺==0，4=0/=L些值對應(yīng)，的列序號j溝成M合冊（列序號集合上(.3」~4tuJ*f-<4j- u視j[f0fHl/Em14〕求不二月用的最小二乘解：舟二argm如小尸一耳引二?年4?1吊尸；⑸更新殘差號一4@二？一4111封",；⑹公￡十1,如果￡0尤則返回第⑷步，否則停止迭代進入第?！坎?；（“重構(gòu)所得，在4處有非零項，具值分別為最后一次迭代所得同B(2)計算"=abs（即計算《工『勺）1%/三曾），選擇口中最入的S個值，將這注1：得到臺后,利用稀疏矩陣可得重構(gòu)信號￡=W。經(jīng)GOMP算法重構(gòu)后的結(jié)果如下所示:該算法的用時情況如下：探查摘要基于pBfbEan匚e時間于13-Mw-201822333rfesf。里州空林調(diào)用次數(shù)總時間白手時「市13■時可圖，:深色條帶=自用時間）GUMP13.024s0.513500MpMc￡_」OMP5121.553sC.733sviaMtmes15320.620s0.620sinn51mM20.59250.056s■in'tti四20.431sC.013￡■rrwYegui20.393sC391s■uni^n20420.30030.053s■unionAunioriRW2占20420.24750.076s■mcirph口口40.242sC.Q48￡■unique20420.171sU.100s11.6基追蹤法（BP）除匹配追蹤類貪婪迭代算法之外，壓縮感知重構(gòu)算法另一大類就是凸優(yōu)化算法或最優(yōu)化逼近方法，這類方法通過將非凸問題轉(zhuǎn)化為凸問題求解找到信號的逼近，其中最常用的方法就是基追蹤（BasisPursuit,BP）,該方法提出使用11范數(shù)替代10范數(shù)來解決最優(yōu)化問題，以便使用線性規(guī)劃方法來求解。經(jīng)BP算法重構(gòu)后的結(jié)果如下所示：原始圖森 恢亞的阿保該算法的用時情況如下：

探直摘要尋于戶&廣砧E3c3時間于05-Feb-2018fS.-f8:49.旬%詆用儺g總時間日用時可*忘時回圉［深色條帶=自用時間）BP1486.857s0.129s即下日Rjina2g512485,557s0715s」ry些坦512AS4.84250.33Qseptimgiuetm1i口皿51223.617^optiE\priu/td：1ip&H》q巳tpu82693^8,566s398.0905口ptim\p