几种压缩感知算法

.1压缩感知部分压缩感知算法主要可分为三类：贪婪迭代算法、凸凸优化（或最优化逼近方法）和基于贝叶斯框架提出的重构算法。由于第三类方法注重信号的时间相关性，不适合图像处理问题，故目前的研究成果主要集中在前两类中。目前已实现6中算法，分别为正交匹配追踪法（OMP）、迭代硬阈值法（IHT）、分段正交匹配追踪法（StOMP）、分段弱正交匹配追踪法（SwOMP）、广义正交匹配追踪（GOMP）、基追踪法（BP）。1.1正交匹配追踪法（OMP）在正交匹配追踪OMP中，残差是总与已经选择过的原子正交的。这意味着一个原子不会被选择两次，结果会在有限的几步收敛。OMP的算法如下（1）用x表示你的信号，初始化残差eO二x；（2）选择与eO内积绝对值最大的原子，表示为e1；（3）将选择的原子作为列组成矩阵①t,定义①t列空间的正交投影算子为产二叫（到国尸呼通过从eO减去其在①t所张成空间上的正交投影得到残差e1；%二%—尸/二（『一P）.（4）对残差迭代执行（2）、（3）步;其中I为单位阵。需要注意的是在迭代过程中①t为所有被选择过的原子组成的矩阵，因此每次都是不同的，所以由它生成的正交投影算子矩阵P每次都是不同的。（5）直到达到某个指定的停止准则后停止算法。OMP减去的Pem是em在所有被选择过的原子组成的矩阵①t所张成空间上的正交投影，而MP减去的Pem是em在本次被选择的原子em所张成空间上的正交投影。经OMP算法重构后的结果如下所示：算法的使用时间如下:

探查摘要基于Ferformanc总时间于25-Jan-2018/4:3S;39生成r国数名称调用次教总时间西时间图（:深色条口=自用时问）11-007s。和7sOMP-Grn口512197.926s151.802EI门166346.124s46.124sim-hcw41.321sD.119£I41.032sD.030smcwvgui4u.574sD.965s\中,尸口巴r210.96230230s用3「220.490sD.4S9£10.210sD.Q29s4u.193s0.039s迭代硬阈值法（IHT）目标函数为C认,z）=IIX-蚓._|阳_*z|lz+l|y一可修ll0lb<1这里中的M应该指的是M-sparse,S应该指的是Surrogate。这里要求：-之后我们利用式C«（y.z）a][货一2yt（zt+ —湄㈣].对目标函数进行变形。接着便是获得极值点：利用该式进行迭代可以得到极值点，我们需要的是最小值。此时目标函数的最小值就得到了。此时便得到我们需要的公式：c需（广Z））/一2k值+婢x-婢中明=£-产

i i我们要保证向量y的稀疏度不大于M，即一二二"二，为了达到这一目标，要保留最大的M项（因为是平方，所以要取绝对值absolutevalue），剩余的置零（注意这里有个负号，所以要保留最大的M项）。IHT算法结果：

口nq『ale* RosloredImageIHT算法使用时间如下:探封商要ffTperformwn3鸵间于25■丽-20?5r8:29:07函函名罚■ 鞫用次数日用1时间*总时1亘国（浜色条带=自用时间）IHT15.543s0.915£im的口坦22591$0.220sIHTysJht5121.496?1.496simnq虫DMLyP3r口心20.941s0.040s■sif~北匕岛北魏-皿1E6如0.060s■imageDi$口ImyMm1id /2662340.5195■…i: ripuF0rSrstialReF虐「白门亡沁g20.528a0.526s■in'6欣20.4S9s0.058s1EQ「pho口4C.4S9s0.12Ss■imdl占悒3口144350.037s■分段正交匹配追踪法（StOMP）分段正交匹配追踪（StagewiseOMP）也是由OMP改进而来的一种贪心算法，与CoSaMP、SP算法类似，不同之处在于CoSaMP、SP算法在迭代过程中选择的是与信号内积最大的2K或K个原子，而StOMP是通过门限阈值来确定原子。此算法的输入参数中没有信号稀疏度K，因此相比于ROMP及CoSaMP有独到的优势。StOMP的算法流程：输入；（DMkN的传感矩阵』维观测向量下迭代次数S,默认为10（4*1限参敕勺，默认为工5输出；⑴信号稀疏表示系凝估计台⑵却xi雉残差产§=”4&以下流程中：咛表示残差，上表示迭代校数，0表示空集：品表示母次迭代找到的索弓1（列序号），4表示上初迭代的索引（列序号）集合（注意；谀元素个数为&,一般有以#九因为语次迭代找到的索引为一般并非只含一个到序号），勺表示矩阵/的第/列，4表示搜索引4选出的矩阵幺的列集合，用为力外的列向堂，符号U表示集合并运算，9•）表示求向堂内积，港小］表示球模值逸对值）.。期始代电=%4=0，4=0/=*,（仃计箕"二"$£'「专_JI：即计蹩（1「%）J N■卜选辉ii中大于门限窗的值.将这些值对应力的列序号J的成集合/（列序号篥合工⑶令4=居=勺（forall/已为）：若4=47（即无断列被选中）则停止迭代进入第（7）步】（4建>=.4网的最小二乘解；=argmm||>-4^|HiX,Ar：4y「⑶更新残差门=尸-Afi^=，-一4।父ztJ4yj侍）上=£+1,如果£VS则返回第⑵步继续迭代，如果£>S或残差4=。则停止迭代进入第（7）步,。・重构所得6在4处有非零项，其值分别为最后一次迭代所得&・

注1:得到6后，利用稀疏矩阵可得重利信号£二田讥注*从输入参数中可以知道本舞法并不需要已知信号稿跻度总；（文献◎中32节第二段中提到”QNIP算法对稀疏度K依赖性很大，只有正瑜佶计了信号的稀确度，才能精确重构原始信号％本人对此观点保留意见）注3,在测量矩阵为随机高斯矩阵的懵况下，第0步中的门腹河二勺?，其中与取信范围一段为2当。，弓:|卜儿/4露，弓表示上次迭代计尊出的残差，.也表示上范血注4；随机高斯测量矩阵如文献⑶的2.2.1节式仁-。所示，这里注意力差一定要是1/M（标准差为1/J57）,即卜Mah生成代码为nndnQL*的卬2，这是因为第12步的原子选择是将传感矩阵列向量与残差的内积向量元素与残差向量2范数的某倍数相比较，对于前面的几篇介绍的其它重构算法此处无所谓，为保持一致此后尽量全部以r组曲（Vgsqrtn。来生成测型矩阵.经StOMP算法重构后的结果如下所示该算法的用时情况如下:

探查摘要基于perform如时司于f9-配用「-2。7822;2及26生成廖威名称总时间自用时间*■■己对同图〔深色赛宙=臼尾时同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）可以说是StOMP的一种修改算法，它们的唯一不同是选择原子时的门限设置，这可以降低对测量矩阵的要求。我们称这里的原子选择方式为〃弱选择〃（WeakSelection），StOMP的门限设置由残差决定，这对测量矩阵（原子选择）提出了要求，而SWOMP的门限设置则对测量矩阵要求较低（原子选择相对简单、粗糙）。SWOMP的算法流程：输入1於的传感矩阵V二侬犷⑵剧维湿测向量y0）迭代技数S,默认为（4）门限参数），默认为。.5输出，［1）信号稀疏表示系数估计。⑵Nxl维残差/工¥-4用以下流程中；「表示残差，上表示迭代次数，。表示空第，4表示每次迭代找到的索弓列序号卜儿表示士汶送代的索弓列序号）集合〔注意：设元素个数为心，一般科打工人因为每次送代找到的索引4一股井江只含一个列序号），啊表示矩阵』的第」列，段表示搜索引儿选出的矩阵力的列集合，8,为口句的列向量।符噜u表示集合并运茸.（小表示求向।量内积，口加［■］表示求模值（绝对值）.

(I)初始化e=丸4)=0，4=0£=1靠浒算"必［万工小即计售仁1巴).1=”可)，选择"中大于门限裔的值，将这些值对匣幺的列序号j构成集合/(列序号集合门13)令4=4-154，A-4-idorallyJJ))；若4=44(即无新列被选中)则停止迭代进入第U沙，(4)求y-郎才的晨小二乘解：9.-arg］口血1忸—A^|=14A'1>1(5)更新残差弓=/-Aflt-y-Aj\^Ai1s(6)/=£+1,如果£WS则返回第Q)步维续迭代，如果』>£或残差门=0则停止迭代进入第(7)步；⑺重构所得占在4处有豌零项，其值分别为最后一枚迭代所得用.注1：得到。后，利用稀疏矩阵可得重利信号登=5自注2：文献［1］中给出了第⑵步中的门限窗=erm淞5加(■)),其中a取值范围一般为0<a<l；文献R］中式(13)与此门隈设置不同.本人对此观点保留意见.经SwOMP算法重构后的结果如下所示：垠蜡图像 愫复的图像该算法的用时情况如下:基于打已行二「esn匚已时间于19-f^ar-20f822:22:42生成国教■名称调用次数总崛自用时谕息用同图（深色条市=自用时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每次只选择与残差相关最大的一个，而gOMP则是简单地选择最大的S个。之所以这里表述为〃简单地选择〃是相比于ROMP之类算法的，不进行任何其它处理，只是选择最大的S个而已。GOMP算法流程如下：输入；口）服xM的传感矩阵』=学/⑵班xl维观测向里1（3）信号的稀疏度K（4）每次选择的原子个数k默认取值为K」，若氏国则默认取1输出：（1）信号稀疏表示系数估计3⑵Mxl维我差勺=/—4瓦以下流程中：4表示残差，£表示迭代次数，0表示空集，4表示2次迭代的索弓1（列序号）集合，4表示第拧欠迭代找到的索弓I列序号）勺表示矩阵』的第J列，4表示搜案引几选出的矩阵旦的列集合［大小为肱吊£的矩阵），珞为"1的列向量，符号U表示集合并运算，〈・,・）表示求向量内积1

些值对应，的列序号J沟成集合册（列序号集合上131号,=4_]L_J?=4= L_J♦；.[fCt t/.J;〔4〕些值对应，的列序号J沟成集合册（列序号集合上131号,=4_]L_J?=4= L_J♦；.[fCt t/.J;〔4〕求r=Afit的最小二乘解：色=argliiin||j?-441|=j4X।14y;⑸更新残差=7—4@=尸―41年411父,；@:£十1,如果£W武四返回第⑵步，否则停止迭代进入第步：（“重构所得，在4处有非零项，其值分别为最后一次迭代所得自H①初始化?=,，4=0，4W1；(2)计算&=0bs4七_J（即计算选择期中最入的S个值，将这注1；得到。后，利用稀疏矩阵可得重构信号京=刀;经GOMP算法重构后的结果如下所示:该算法的用时情况如下:探世摘要基于perfaE曰开匚巳肿间T19-Mw-2。fS22;33rfeS?。函颜名林调用次数总时间白生时（H*总司司图，:深色条带==用区问:，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）除匹配追踪类贪婪迭代算法之外，压缩感知重构算法另一大类就是凸优化算法或最优化逼近方法，这类方法通过将非凸问题转化为凸问题求解找到信号的逼近，其中最常用的方法就是基追踪（BasisPursuit,BP），该方法提出使用l1范数替代l0范数来解决最优化问题，以便使用线性规划方法来求解。经BP算法重构后的结果如下所示：原始网帆 快封的园也该算法的用时情况如下:

探宜摘要基于pIoEMts时间于。5,E匕q01gf9：他-加圭龙总时间自用时回*忘时回闺［深色条带=自用时间）BP1436.857s0.129sE口：■■日pjjnarog512485557s0715s」npfqqS12484.642s0.330s口不甘m u百tuVi口与ol5124B3.S49s23.6173QptiE\p