文档介绍：该【几种压缩感知算法 】是由【1338909****】上传分享，文档一共【11】页，该文档可以免费在线阅读，需要了解更多关于【几种压缩感知算法 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。.1压缩感知部分压缩感知算法主要可分为三类:贪婪迭代算法、凸凸优化(或最优化逼近方法)和基于贝叶斯框架提出的重构算法。由于第三类方法注重信号的时间相关性,不适合图像处理问题,故
目前的研究成果主要集中在前两类中。目前已实现6中算法,分别为正交匹配追踪法(0MP)、迭代硬阈值法(IHT)、分段正交匹配追踪法(StOMP)、分段弱正交匹配追踪法(SwOMP)、广义正交匹配追踪(GOMP)、基追踪法(BP)。
(OMP)
在正交匹配追踪OMP中,残差是总与已经选择过的原子正交的。这意味着一个原子不会被选择两次,结果会在有限的几步收敛。OMP的算法如下
用x表示你的信号,初始化残差e0=x;
选择与e0内积绝对值最大的原子,表示为©1;
将选择的原子作为列组成矩阵①t,定义①t列空间的正交投影算子为
P二會(时屯尸时
通过从e0减去其在①t所张成空间上的正交投影得到残差el;
便]二%—P%=P)坯
对残差迭代执行(2)、(3)步;
%1二耳-戸耳=W_叽
其中I为单位阵。需要注意的是在迭代过程中①t为所有被选择过的原子组成的矩阵,因此每次都是不同的,所以由它生成的正交投影算子矩阵P每次都是不同的。
直到达到某个指定的停止准则后停止算法。
OMP减去的Pem是em在所有被选择过的原子组成的矩阵①t所张成空间上的正交投影,而MP减去的Pem是em在本次被选择的原子©m所张成空间上的正交投影。
经OMP算法重构后的结果如下所示:
算法的使用时间如下:
探查摘要
基于performance肘间于25-Jan-2018/4:3S;39生或■>
国戦呂称
翔用次麴
思测
自用时间*
总旳闫團
(深色条匚二亡老盯问1
OMP
1
?C1-Q07s
OMPiomo
512
vi'aMt'mes
IE1663
:
irnshcw
4
£
1
initSi'z^
斗
moveciui
4
wienerZ
1
0230s
filters
2
£
^h^naeClass
1
moriahoEJ
4
(IHT)
目标函数为
磴(戸)=||嵩-①儒一||如一Mi+liy一疇・
、、、、、、、、、ll^h<1
这里中的M应该指的是M-sparse,S应该指的是Surrogate。这里要求:"
之后我们利用式
C^(y,z)oc乙员-2丹(;,■+毎X-0仁d>z)].
对目标函数进行变形。接着便是获得极值点:
y;=石十婷兀一時①盘
利用该式进行迭代可以得到极值点,我们需要的是最小值。此时目标函数的最小值就得到了。此时便得到我们需要的公式:
C沐*z)ocg呼-2歼匕+沪璇-护仇)]=力-yf.
ii
我们要保证向量y的稀疏度不大于M,即:为了达到这一目标,要保留最大的M项(因为是平方,所以要取绝对值absolutevalue),剩余的置零(注意这里有个负号,所以要保留最大的M项)。
IHT算法结果:
IHT算法使用时间如下:
探圏商要
:07生碇
函我呂称闕用次釵
总时1亘長
俸色祭带=自用时何)
IHT
1
£
im曲ow
2
2591s
IHT>csiht
512
imacieDisplavPareelnuuts
2
■
stnglifvIakeDiskStrel
1
■
imsqeDisplevValidateParann5
2
■
...tpreParse)nputaForSp^tib\Refenencima
2
0S23s
■
ini(Size
2
1
morphop
4
■
m
■
(StOMP)
分段正交匹配追踪(StagewiseOMP)也是由OMP改进而来的一种贪心算法,与CoSaMP、SP算法类似,不同之处在于CoSaMP、SP算法在迭代过程中选择的是与信号内积最大的2K或K个原子,而StOMP是通过门限阈值来确定原子。此算法的输入参数中没有信号稀疏度K,因此相比于ROMP及CoSaMP有独到的优势。
StOMP的算法流程:
ere^seretsea
输入;
CDMxy的恃感拒阵A-砂
(2)时幻维观测向壘尸
(3}选代汝数默认为10
(4)n服参数f昇默认为加
输出;
⑴信母稱疏表示系数怙计3
[2)JVxl维残差尸严厂地成
以下流程中=与表示残差,诜示送代空数,®表示空集:仏恚示每谀迭代找到朗索引(列疥号卜儿表示处选代的索引(列序号);入表示按翕引儿选出的矩阵虫的列集合,您沏心幻的列向莹,符号U表示集合并运算,£•)表示求向窒內积,於计・]表示永模值凰对值=
(I诙始^4=^=1>
(打计算ii=d加川「号_]|即计篡(j®,1益JW选择《中犬于门限恥的倉将
送些值对应月的列序号丿构咸集合几(列序号昊合);
⑶令儿=人-2几,耳=42幻(forall丿巨爲):若人=人国(即无新列被选中)则停止迭代进入第(7)^
(4}求y=-4禺的最小二乘孵;=argluul||>-4^||=14FA1(Ayf
⑸更新磯差弓二y-舛g=丿-时]老』s
⑹"(十1,如果L<S^l返回第⑵"£或残差斤,则停止迭代进入藹⑴步'
A应
⑺重构所得日在儿处有非零项,耳值分别齿最后一诙迭代所得目・
A„一_..一…•--…A
注1:得到日届利用稀疏拒阵可得重构信号x=^e
注・从输入参数中可讯知道本算法芥不需要已知信号稀蹴度庄;(文獻[2]中3丄节第二段中提到临谆法对稀疏度k依赖性很尢,只有正确儘计了信号的稀疏彥,才能稻确重构原始信号3車人对此视点保留意见)
注二在测显矩阵衙随机高商矩阵的情况下・第⑴步中的门踐也二弓込,且中◎取憤范围一隈为2宅门,巧二帆|屛顶,q表示上浹选代计算出的残差,|比恚示2范熱
注4;施机鬲厨测重矩阵如文献⑶}所和这里注意方差一定要是
(标谁^^)1/4m),即Matab生成代码齿randnfl;\LN:.旳皿\[),这是因芮第I二涉餉瘵子选择是将传感矩阵列向童与歿差闌內祀向重元素马残差向童2范甑的某倍数相比较,对于前面的几篇介绍的其它重构畀法此处无所谓』)sqrttAfi来生咸测量矩阵.
经StOMP算法重构后的结果如下所示:
该算法的用时情况如下:
探査摘要
慕于曲托肘闫于1r-201S主成,
觀陷称调用次数品时间曰用珂同*忌曲叵图
〔深色釜肯=白臣时匠]丿
;
imEhow
2
nevvplot
4
newplot^Obi:ervfeFiqursNentPlot
4
dr
2
morphop
4
■
strel>MakeD'skStrel
1
£
■
imdiate
3
■
in'tSize
2
■
imopen
1
■
(SwOMP)
分段弱正交匹配追踪(StagewiseWeakOMP)可以说是StOMP的一种修改算法,它们的唯一不同是选择原子时的门限设置,这可以降低对测量矩阵的要求。我们称这里的原子选择方式为〃弱选择〃(WeakSelection),StOMP的门限设置由残差决定,这对测量矩阵(原子选择)提出了要求,而SWOMP的门限设置则对测量矩阵要求较低(原子选择相对简单、粗糙)。
SWOMP的算法流程:
输入
Mx附的传煎矩阵M=歯皆
^x1维呗测向童卩
迭代塗数默认?UK)
门$艮秦数4,默认沖丄吕输出’
信号稀疏表示系数估计0
⑵“冥1维残差皆厂锻
為下新程中'农表示残差,儼示迭代伏熱0恚示空為%表示每復选代痔!I的索
引例呼号h巩寰示廿史注代的索引(列序号)集合〔注貶设元素个数为Z"—般有九"
因沟轲衣选代找到旳索引几一股并菲只舍一个列序号卜吟表示矩阵A的第』列,舛表示
・〈・"表
示求向量內秧血卜]表示求模値储对值h
Q)初始1社心==0「41=0/=1;
⑵计算u-abs月1_]](即计算心_严;)」兰丿黑时),选择w中大于门礙27?的值,将这些值对应卫的列宇号丿构成集合%(列序号集合b
⑶習人二人A,=A_idorallyeJJ));若A=4-j(即无新列按选中)叫停止迭代进入第卩涉,
(4烬y-Afit的最小二乗解:&二ar^mm加一舛引二N£「挖,j
⑸更新残差斗-y-Afit-y-Aj\^Ai1s
{6)Z=/+IS如卑(玄£则返回第C)步继续迭代,如果"£或残差zj=O则停it迭代进入第⑺步;
{门重构所簿日在儿处有非零项*具值分别为最后一谀谨代所簿4・注1:得封歹后,利用稀疏矩阵可得重构信号丘二晌
注2:文献⑴中给出了第,丄)步中的门限珞=亘申处取•值范围一般为0<a<l;文献[2]中式(13)导此门限设置不同』本人对此观点保留意思
经SwOMP算法重构后的结果如下所示:
垠強罔惟怖盘的阳iSi
该算法的用时情况如下:
基于p已!胡匸已Si垣厅19-f^ar-20f822:22:^2生■或
画数名称
诟用次数
自用时间*
启屁间图
(深色条带=口,^irtr=]j
SWOMP
1
^
SWOMP^CSSWOMP
51?
1/72e
2569
imshow
2
■
initSize
2
■
moveaui
2
■
union
3080
■
uninn>uri0nR2C12a
3000
■
morohci^
儿
1
strel>MakeD'skScrcl
1
1
(GOMP)
广义正交匹配追踪(GeneralizedOMP,gOMP)算法可以看作为OMP算法的一种推广。OMP每次只选择与残差相关最大的一个,而gOMP则是简单地选择最大的S个。之所以这里表述为〃简单地选择〃是相比于ROMP之类算法的,不进行任何其它处理,只是选择最大的S个而已。
GOMP算法流程如下:
输的传感矩阵A=羽
⑵屁1维观测向my
口)信号的稀疏度K
(斗)每欢选择的原子牛数氐默认取值曲K丄若K<4认取1输出=
《1)信号稀蔬表示系数估计&
(2)对灯维残差孩=$_A血
以下流程中=与表示残差,{表示迭代次数,3表示空隼,儿表示圻欠迭代的索引(列序号〕集合,咎表示第总次选代找到的索引(列序号】幻表示拒阵/的第』列,珂表示按索引几选出的矩阵卫的列集合〔幷卜曲的矩阵》也“1的列向壘符号U表示集合并运算,(・,・〉表示求向量内积-
些值对应』的列序号j构戚M合人(列序号集合》
[3」■芳1■=4一11£:i‘=亠兔一]1一」盘『让・:比41』匕人」'
(4〕求y=Afit的最小二乘解:&=argmin||>?_441|=!44114P;
⑤更新殛差jj=y-At&t=y-At^A^;
何f二f十1,如果上庄则返回第⑵歩,否则停止迭代进入第〔7涉:
W重构所得8在人处有非零项,其值分别为最后一次迭代所得旨H
⑴初始化佥
=”4)=0,4)=1;
(2)计算施=abs
fj](即计算如_")1勺兰叭选择&中最入的E个值,将这
注1:得到◎后
利用稀疏矩阵可得重构信号金=财;
经GOMP算法重构后的结果如下所示:
该算法的用时情况如下:
探査摘要
基于Rerfamanu亡时闻~r19018fS生眩
调用次数
目用时「费
E、对间图
{遛色槩芾=色用冈问)
GCMP
1
£
GOMP>CSqOMP
512
-.6535
viaMt'tries
532
■
imshow
2
■
im'tSize
2
■
movequi
2
■
union
2042
■
union>unionR2012a
2042
■
morphop
4
£
■
unique
2042
1
(BP)
除匹配追踪类贪婪迭代算法之外,压缩感知重构算法另一大类就是凸优化算法或最优化逼近方法,这类方法通过将非凸问题转化为凸问题求解找到信号的逼近,其中最常用的方法就是基追踪(BasisPursuit,BP),该方法提出使用ll范数替代10范数来解决最优化问题,以便使用线性规划方法来求解。
经BP算法重构后的结果如下所示:
廉始圉忖恢址的罔说
该算法的用时情况如下: