1418自动化学报37卷
表1主要贪婪算法的性能比较
Table1Comparisonofperformancesformain
greedyalgorithms
OMP
精确测量运行时间精确重建重建的稳定性
否
是
是
否
是
是
多的测量次数作为精确重建的保证.
4模拟实验
StOMPCoSaMP是
否
ROMP否
SP否
O(mMN)O(mMN)O(log(m)MN)O(MN)O(MN)
否是是否否
为了进一步讨论算法的性能,我们先给出RIC的一个简单性质:
性质2(δm单调性).对任意的整数m,m ,如果有m≤m ,则有δm≤δm .
由性质2,我们有δ3m<δ4m,则若δ4m<0.1,则一定有δ3m<0.1;另一方面,一般情况下因为m表示信号的稀疏度,因此,显然有
√
δ4m<0.01/<0.01成立.从而可以看出ROMP、SP和CoSaMP中ROMP对限制等容常数的要求最高(即限制等容常数最小),而CoSaMP其次,SP最低.因此,在相同测量矩阵的条件下,为达到相同的相对重建误差水平,ROMP需要较多的测量次数来抵消限制等容常数的高要求性.
由于计算一个矩阵的RIC是NP难问题,因此,本文以高斯随机矩阵和部分傅里叶矩阵为测量矩阵,获得精确重建时测量次数M的相关结论来讨论M与RIC之间的逻辑关系:
M×N
1)高斯测,√量矩阵:定义为Φ∈R
Φ(i,j)=φij/其中φij~N(0,1),当M满足:
N
Cmlog
m
(3)M≥
ε2
时,以大小为1 εcM的概率有RIC,δm≤ε成立,这里C,c为正的常数[40].
2)部分傅里叶矩阵:定义为Φ∈RM×N,由随机地从N×N维离散傅里叶变换矩阵中抽取M行构成.当M满足:
为了保证重建算法性能比较的客观性,我们采用绝对稀疏0–1随机信号.模拟实验在CPU为In-telE5300(双核2.60GHz),内存为2.00GB的联想品牌机上运行.首先,假设稀疏信号长度N=512,稀疏度为m=40,测量次数M=256,高斯随机测量矩阵Φ∈RM×N:Φ(i,j)=1φ,其中i,j
φi,j~N(0,1),用算法2~算法7的6种算法进行重建性能验证(见图1),由图1可以看出,在一定的测量次数下,这6种算法都能精确地恢复信号.由于重建中测量矩阵的随机性,为了进一步比较各种算法的重建效果和信号稀疏度以及测量次数之间的关系,我们通过多次的实验来比较上述6种算法的重建性能.比较的标准分别为稀疏度与信号重建概率、测量次数与信号重建概率之间的关系.这里仍然采用绝对稀疏的0–1随机信号,通过假设N=256,M=128,改变信号的稀疏度(从m=20开始),假设N=256,m=30,改变测量次数(从M=60开始),分别进行500次模拟实验,结果如图2和图3所示

.
图1当N=512,m=40,M=256时,贪婪算法OMP,ROMP,CoSaMP,SP,StOMP和IBOOMP的重建结果Fig.1
ReconstructionresultsbasedonOMP,ROMP,
N=512,m=40,andM=256
CoSaMP,SP,StOMP,andIBOOMP,respectively,with
C mlog5N·log(ε 1)M≥
ε2
(4)
时,以大小为1 1/N的概率有RIC,δm≤ε成立,这里C 为正的常数[41].
从式(3)和式(4)中显然看出,RIC常数与测量次数成反比,因此越小的限制等容常数就需要越
由图2可以看出:在测量次数一定的条件下,随着稀疏度的增加,信号重建概率逐渐减小,在信号非常稀疏的情况下,各种算法都以高概率重建原始信号.为了更好地比较各种算法在不同稀疏度的表现,我们让m从20开始,由图2明显可以看出OMP和ROMP成功的概率相对比较小,而CoSaMP和SP
37, No. 12 December, 2011 贪婪算法与压缩感知理论方 红1 杨海蓉 2 摘要 贪婪算法以其重建速度快、 重建方法实现简便的特点在压缩感知 (Compressed sensing, ...
因此,如何设计出计算复 杂度低、稳定且所需观测数较少的重构算法已成为目 前压缩感知理论的一个热点问题 [8]。 Huggins和Zucker等人于2006提出的贪婪基追踪算 法...
和 Candes 等人[1,2]在稀疏表 示和优化理论的基础上提出的一种成像理论。...模型化压缩感知重构算法利用贪婪搜索的方法 寻找最优小波系数子树集,而这些最优...
10.3969/j.issn.1001-2400.2012.03.008 一种贪婪自适应压缩感知重构甘 伟 ...针对 CoSaMP 算法关于信号稀疏度的非自适应性问题, 本文通过采用具有理论保证的...
0.9 9ji n 1 0-4 0.0 2.3.0 s 一种贪婪自适应压缩感知重构甘 伟, ...算法该 采用了具有理论保证的模糊阈值预选方案以 避免预选时使用信号的先验信息,...
压缩感知理论及其重构算法_工学_高等教育_教育专区。压缩感知算法...东莞理 工学院学报 年 匹配跟踪 算法匹 配跟 踪算法是一种迭代贪婪算法 , ...
12压 缩感 知信号表示 . 为 了避 免上 述缺点 ,压缩感知理论不需要获取J ...生QQ 匹配 跟 踪算 法 是一 种迭代贪婪算法 ,它 是通 过对一系列 的单 ...
压缩感知理论(Compressive)_IT/计算机_专业资料。压缩感知理论(Compressive ...(2)贪婪匹配追踪(MP)算法 :从字典中一 个一个挑选向量,每一步都使得信号的...
K X K 如何找到信号最佳的稀疏域?这是压缩感知理论应用的基础和前提,只有选择...由于 l1 最小范数下的算法 速度慢,新的快速贪婪法被逐渐采用,如匹配追踪法(...
连续边缘的图像信号的Curvelet系数等都具有足够的 稀疏性,可以通过压缩感知理论...在稀疏分解算法的设计方面,基于贪婪迭代思想的MP(Matching Pursuit)算法表现出 ...
热门文档