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

探查摘要基于Ferformanc總時(shí)間于25-Jan-2018/4:3S;39生成r國(guó)數(shù)名稱調(diào)用次教總時(shí)間西時(shí)間圖（:深色條口=自用時(shí)問(wèn)）11-007s。和7sOMP-Grn口512197.926s151.802EI門(mén)166346.124s46.124sim-hcw41.321sD.119￡I41.032sD.030smcwvgui4u.574sD.965s\中,尸口巴r210.96230230s用3「220.490sD.4S9￡10.210sD.Q29s4u.193s0.039s迭代硬閾值法（IHT）目標(biāo)函數(shù)為C認(rèn),z）=IIX-蚓._|陽(yáng)_*z|lz+l|y一可修ll0lb<1這里中的M應(yīng)該指的是M-sparse,S應(yīng)該指的是Surrogate。這里要求：-之后我們利用式C?（y.z）a][貨一2yt（zt+ —湄㈣].對(duì)目標(biāo)函數(shù)進(jìn)行變形。接著便是獲得極值點(diǎn)：利用該式進(jìn)行迭代可以得到極值點(diǎn)，我們需要的是最小值。此時(shí)目標(biāo)函數(shù)的最小值就得到了。此時(shí)便得到我們需要的公式：c需（廣Z））/一2k值+婢x-婢中明=￡-產(chǎn)

i i我們要保證向量y的稀疏度不大于M，即一二二"二，為了達(dá)到這一目標(biāo)，要保留最大的M項(xiàng)（因?yàn)槭瞧椒?，所以要取絕對(duì)值absolutevalue），剩余的置零（注意這里有個(gè)負(fù)號(hào)，所以要保留最大的M項(xiàng)）。IHT算法結(jié)果：

口nq『ale* RosloredImageIHT算法使用時(shí)間如下:探封商要ffTperformwn3鴕間于25■麗-20?5r8:29:07函函名罰■ 鞫用次數(shù)日用1時(shí)間*總時(shí)1亙國(guó)（浜色條帶=自用時(shí)間）IHT15.543s0.915￡im的口坦22591$0.220sIHTysJht5121.496?1.496simnq蟲(chóng)DMLyP3r口心20.941s0.040s■sif~北匕島北魏-皿1E6如0.060s■imageDi$口ImyMm1id /2662340.5195■…i: ripuF0rSrstialReF虐「白門(mén)亡沁g20.528a0.526s■in'6欣20.4S9s0.058s1EQ「pho口4C.4S9s0.12Ss■imdl占悒3口144350.037s■分段正交匹配追蹤法（StOMP）分段正交匹配追蹤（StagewiseOMP）也是由OMP改進(jìn)而來(lái)的一種貪心算法，與CoSaMP、SP算法類似，不同之處在于CoSaMP、SP算法在迭代過(guò)程中選擇的是與信號(hào)內(nèi)積最大的2K或K個(gè)原子，而StOMP是通過(guò)門(mén)限閾值來(lái)確定原子。此算法的輸入?yún)?shù)中沒(méi)有信號(hào)稀疏度K，因此相比于ROMP及CoSaMP有獨(dú)到的優(yōu)勢(shì)。StOMP的算法流程：輸入；（DMkN的傳感矩陣』維觀測(cè)向量下迭代次數(shù)S,默認(rèn)為10（4*1限參敕勺，默認(rèn)為工5輸出；⑴信號(hào)稀疏表示系凝估計(jì)臺(tái)⑵卻xi雉殘差產(chǎn)§=”4&以下流程中：嚀表示殘差，上表示迭代校數(shù)，0表示空集：品表示母次迭代找到的索弓1（列序號(hào)），4表示上初迭代的索引（列序號(hào)）集合（注意；諛元素個(gè)數(shù)為&,一般有以#九因?yàn)檎Z(yǔ)次迭代找到的索引為一般并非只含一個(gè)到序號(hào)），勺表示矩陣/的第/列，4表示搜索引4選出的矩陣幺的列集合，用為力外的列向堂，符號(hào)U表示集合并運(yùn)算，9?）表示求向堂內(nèi)積，港?。荼硎厩蚰Ｖ狄輰?duì)值）.。期始代電=%4=0，4=0/=*,（仃計(jì)箕"二"$￡'「專_JI：即計(jì)蹩（1「%）J N■卜選輝ii中大于門(mén)限窗的值.將這些值對(duì)應(yīng)力的列序號(hào)J的成集合/（列序號(hào)篥合工⑶令4=居=勺（forall/已為）：若4=47（即無(wú)斷列被選中）則停止迭代進(jìn)入第（7）步】（4建>=.4網(wǎng)的最小二乘解；=argmm||>-4^|HiX,Ar：4y「⑶更新殘差門(mén)=尸-Afi^=，-一4?父ztJ4yj侍）上=￡+1,如果￡VS則返回第⑵步繼續(xù)迭代，如果￡>S或殘差4=。則停止迭代進(jìn)入第（7）步,。?重構(gòu)所得6在4處有非零項(xiàng)，其值分別為最后一次迭代所得&?

注1:得到6后，利用稀疏矩陣可得重利信號(hào)￡二田譏注*從輸入?yún)?shù)中可以知道本舞法并不需要已知信號(hào)稿躋度總；（文獻(xiàn)◎中32節(jié)第二段中提到”QNIP算法對(duì)稀疏度K依賴性很大，只有正瑜佶計(jì)了信號(hào)的稀確度，才能精確重構(gòu)原始信號(hào)％本人對(duì)此觀點(diǎn)保留意見(jiàn)）注3,在測(cè)量矩陣為隨機(jī)高斯矩陣的懵況下，第0步中的門(mén)腹河二勺?，其中與取信范圍一段為2當(dāng)。，弓:|卜兒/4露，弓表示上次迭代計(jì)尊出的殘差，.也表示上范血注4；隨機(jī)高斯測(cè)量矩陣如文獻(xiàn)⑶的2.2.1節(jié)式仁-。所示，這里注意力差一定要是1/M（標(biāo)準(zhǔn)差為1/J57）,即卜Mah生成代碼為nndnQL*的卬2，這是因?yàn)榈?2步的原子選擇是將傳感矩陣列向量與殘差的內(nèi)積向量元素與殘差向量2范數(shù)的某倍數(shù)相比較，對(duì)于前面的幾篇介紹的其它重構(gòu)算法此處無(wú)所謂，為保持一致此后盡量全部以r組曲（Vgsqrtn。來(lái)生成測(cè)型矩陣.經(jīng)StOMP算法重構(gòu)后的結(jié)果如下所示該算法的用時(shí)情況如下:

探查摘要基于perform如時(shí)司于f9-配用「-2。7822;2及26生成廖威名稱總時(shí)間自用時(shí)間*■■己對(duì)同圖〔深色賽宙=臼尾時(shí)同1i.siss0.129simshow21.238s0.090snevvnat40.866sC.030￡口白*”口10匚「ObM9rvEFiqu「rNc*tPlot40.789占C.074$elf20.715s0.5255m口午hop40.322sC.O65s■￡tr「lrM自kgEi'skL匚「白110.266￡0.014s■imdidte30.255s0.0055■in'tSize20.1SOsC.013s■imopen10.145s0.007s■分段弱正交匹配追蹤法（SwOMP）分段弱正交匹配追蹤（StagewiseWeakOMP）可以說(shuō)是StOMP的一種修改算法，它們的唯一不同是選擇原子時(shí)的門(mén)限設(shè)置，這可以降低對(duì)測(cè)量矩陣的要求。我們稱這里的原子選擇方式為〃弱選擇〃（WeakSelection），StOMP的門(mén)限設(shè)置由殘差決定，這對(duì)測(cè)量矩陣（原子選擇）提出了要求，而SWOMP的門(mén)限設(shè)置則對(duì)測(cè)量矩陣要求較低（原子選擇相對(duì)簡(jiǎn)單、粗糙）。SWOMP的算法流程：輸入1於的傳感矩陣V二儂獷⑵劇維濕測(cè)向量y0）迭代技數(shù)S,默認(rèn)為（4）門(mén)限參數(shù)），默認(rèn)為。.5輸出，［1）信號(hào)稀疏表示系數(shù)估計(jì)。⑵Nxl維殘差/工￥-4用以下流程中；「表示殘差，上表示迭代次數(shù)，。表示空第，4表示每次迭代找到的索弓列序號(hào)卜兒表示士汶送代的索弓列序號(hào)）集合〔注意：設(shè)元素個(gè)數(shù)為心，一般科打工人因?yàn)槊看嗡痛业降乃饕?一股井江只含一個(gè)列序號(hào)），啊表示矩陣』的第」列，段表示搜索引兒選出的矩陣力的列集合，8,為口句的列向量?符嚕u表示集合并運(yùn)茸.（小表示求向?量?jī)?nèi)積，口加［■］表示求模值（絕對(duì)值）.

(I)初始化e=丸4)=0，4=0￡=1靠滸算"必［萬(wàn)工小即計(jì)售仁1巴).1=”可)，選擇"中大于門(mén)限裔的值，將這些值對(duì)匣幺的列序號(hào)j構(gòu)成集合/(列序號(hào)集合門(mén)13)令4=4-154，A-4-idorallyJJ))；若4=44(即無(wú)新列被選中)則停止迭代進(jìn)入第U沙，(4)求y-郎才的晨小二乘解：9.-arg］口血1忸—A^|=14A'1>1(5)更新殘差弓=/-Aflt-y-Aj\^Ai1s(6)/=￡+1,如果￡WS則返回第Q)步維續(xù)迭代，如果』>￡或殘差門(mén)=0則停止迭代進(jìn)入第(7)步；⑺重構(gòu)所得占在4處有豌零項(xiàng)，其值分別為最后一枚迭代所得用.注1：得到。后，利用稀疏矩陣可得重利信號(hào)登=5自注2：文獻(xiàn)［1］中給出了第⑵步中的門(mén)限窗=erm淞5加(■)),其中a取值范圍一般為0<a<l；文獻(xiàn)R］中式(13)與此門(mén)隈設(shè)置不同.本人對(duì)此觀點(diǎn)保留意見(jiàn).經(jīng)SwOMP算法重構(gòu)后的結(jié)果如下所示：垠蠟圖像 愫復(fù)的圖像該算法的用時(shí)情況如下:基于打已行二「esn匚已時(shí)間于19-f^ar-20f822:22:42生成國(guó)教■名稱調(diào)用次數(shù)總崛自用時(shí)諭息用同圖（深色條市=自用時(shí)I同）1^1.860s0.777sMVVOMP〉匚WJWOMP51?2.957s1/72e―訪MtiT啟E25691.369s1.369s'mshow20.845s0.055s■20.595s0.027e■mcvegui20.51330.59bs■union30800.415s0.075s■Lini：~inTU「g】R"⑵30000.34150.113s.merahc：］公0.246s0.050s1式「回＞M3k白口'MkS『九10.241s0.016s11.5廣義正交匹配追蹤法（GOMP）廣義正交匹配追蹤（GeneralizedOMP,gOMP）算法可以看作為OMP算法的一種推廣。OMP每次只選擇與殘差相關(guān)最大的一個(gè)，而gOMP則是簡(jiǎn)單地選擇最大的S個(gè)。之所以這里表述為〃簡(jiǎn)單地選擇〃是相比于ROMP之類算法的，不進(jìn)行任何其它處理，只是選擇最大的S個(gè)而已。GOMP算法流程如下：輸入；口）服xM的傳感矩陣』=學(xué)/⑵班xl維觀測(cè)向里1（3）信號(hào)的稀疏度K（4）每次選擇的原子個(gè)數(shù)k默認(rèn)取值為K」，若氏國(guó)則默認(rèn)取1輸出：（1）信號(hào)稀疏表示系數(shù)估計(jì)3⑵Mxl維我差勺=/—4瓦以下流程中：4表示殘差，￡表示迭代次數(shù)，0表示空集，4表示2次迭代的索弓1（列序號(hào)）集合，4表示第擰欠迭代找到的索弓I列序號(hào)）勺表示矩陣』的第J列，4表示搜案引幾選出的矩陣旦的列集合［大小為肱吊￡的矩陣），珞為"1的列向量，符號(hào)U表示集合并運(yùn)算，〈?,?）表示求向量?jī)?nèi)積1

些值對(duì)應(yīng)，的列序號(hào)J溝成集合冊(cè)（列序號(hào)集合上131號(hào),=4_]L_J?=4= L_J?；.[fCt t/.J;〔4〕些值對(duì)應(yīng)，的列序號(hào)J溝成集合冊(cè)（列序號(hào)集合上131號(hào),=4_]L_J?=4= L_J?；.[fCt t/.J;〔4〕求r=Afit的最小二乘解：色=argliiin||j?-441|=j4X?14y;⑸更新殘差=7—4@=尸―41年411父,；@:￡十1,如果￡W武四返回第⑵步，否則停止迭代進(jìn)入第步：（“重構(gòu)所得，在4處有非零項(xiàng)，其值分別為最后一次迭代所得自H①初始化?=,，4=0，4W1；(2)計(jì)算&=0bs4七_(dá)J（即計(jì)算選擇期中最入的S個(gè)值，將這注1；得到。后，利用稀疏矩陣可得重構(gòu)信號(hào)京=刀;經(jīng)GOMP算法重構(gòu)后的結(jié)果如下所示:該算法的用時(shí)情況如下:探世摘要基于perfaE曰開(kāi)匚巳腫間T19-Mw-2。fS22;33rfeS?。函顏名林調(diào)用次數(shù)總時(shí)間白生時(shí)（H*總司司圖，:深色條帶==用區(qū)問(wèn):，13.024sC.513m512■.6535C.733sviaMtmes5320.620s0.620s■20.59250.056s■20.431、0.013m■rrwYrgui20.3985C.391s■union20420.300s0.053s■unicuiAunicinR201『日20420.24750.076s■40.242sC.04S￡■uniqui20420.171sU.100s11.6基追蹤法（BP）除匹配追蹤類貪婪迭代算法之外，壓縮感知重構(gòu)算法另一大類就是凸優(yōu)化算法或最優(yōu)化逼近方法，這類方法通過(guò)將非凸問(wèn)題轉(zhuǎn)化為凸問(wèn)題求解找到信號(hào)的逼近，其中最常用的方法就是基追蹤（BasisPursuit,BP），該方法提出使用l1范數(shù)替代l0范數(shù)來(lái)解決最優(yōu)化問(wèn)題，以便使用線性規(guī)劃方法來(lái)求解。經(jīng)BP算法重構(gòu)后的結(jié)果如下所示：原始網(wǎng)帆 快封的園也該算法的用時(shí)情況如下:

探宜摘要基于pIoEMts時(shí)間于。5,E匕q01gf9：他-加圭龍總時(shí)間自用時(shí)回*忘時(shí)回閨［深色條帶=自用時(shí)間）BP1436.857s0.129sE口：■■日pjjnarog512485557s0715s」npfqqS12484.642s0.330s口不甘m u百tuVi口與ol5124B3.S49s23.6173QptiE\p