没有合适的资源?快使用搜索试试~ 我知道了~
首页gOMP算法:压缩感知中的高效信号重构
gOMP算法:压缩感知中的高效信号重构
需积分: 9 1 下载量 20 浏览量
更新于2024-07-18
收藏 447KB PDF 举报
广义 Orthogonal Matching Pursuit (gOMP) 是一种在压缩感知领域中备受关注的贪婪算法,它是在传统 Orthogonal Matching Pursuit (OMP) 算法基础上发展起来的一种扩展。OMP 是一种用于从压缩测量数据中重构稀疏信号的有效方法,通过逐次选择与当前残差最匹配的原子来逼近原信号。然而,gOMP 的核心创新在于每次迭代不仅选择一个,而是同时识别多个(N个)"正确"的索引,从而显著减少了所需的迭代次数。 gOMP 的提出旨在提高重构效率,尤其是在处理高维、多稀疏度信号时。相比于原始的 OMP,其性能优势体现在能够使用更少的迭代次数达到同样的重建精度。该算法的关键理论支撑是 Restricted Isometry Property (RIP),即 sensing matrix 必须满足 δ_{NK} < √(N/√(K+3√N)) 条件,这意味着即使信号具有多个非零元素(K>1),gOMP 也能保证完美重建。 实验结果表明,gOMP 在实际应用中的恢复性能非常出色,能够与著名的 l1-minimization 技术相媲美,而且在处理速度上具有明显的优势。由于其快速的计算速度和竞争力的计算复杂度,gOMP 成为了处理大规模稀疏数据的有效工具,特别适合实时应用或者对时间敏感的场景。此外,gOMP 的设计灵活,易于实现,使得它在实际工程中得到了广泛应用,如无线通信、信号处理和机器学习等领域。gOMP 算法的出现,为压缩感知问题的解决提供了一个高效且高效的解决方案,对于推动相关技术的发展具有重要意义。
资源详情
资源推荐
3
It is worth mentioning that the residual r
k
of the gOMP is
orthogonal to the columns of Φ
Λ
k since
Φ
Λ
k , r
k
=
Φ
Λ
k , P
⊥
Λ
k
y
(4)
= Φ
′
Λ
k
P
⊥
Λ
k
y (5)
= Φ
′
Λ
k
P
⊥
Λ
k
′
y (6)
=
P
⊥
Λ
k
Φ
Λ
k
′
y = 0 (7)
where (6) follows from the symmetry of P
⊥
Λ
k
(P
⊥
Λ
k
=
P
⊥
Λ
k
′
)
and (7) is due to
P
⊥
Λ
k
Φ
Λ
k = (I − P
Λ
k ) Φ
Λ
k = Φ
Λ
k −Φ
Λ
k Φ
†
Λ
k
Φ
Λ
k = 0.
Here we note that this property is satisfied when Φ
Λ
k has
full column rank, which is true if k ≤ m/N in the gOMP
operation. It is clear from this observation that indices in
Λ
k
cannot be re-selected in the succeeding iterations and the
cardinality of Λ
k
becomes simply kN. When the iteration loop
of the gOMP is finished, therefore, it is possible that the final
support set Λ
s
contains indices not in T . Note that, even in
this situation, the final result is unaffected and the original
signal is recovered because
ˆ
x
Λ
s
= Φ
†
Λ
s
y (8)
= (Φ
′
Λ
s
Φ
Λ
s
)
−1
Φ
′
Λ
s
Φ
T
x
T
(9)
= (Φ
′
Λ
s
Φ
Λ
s
)
−1
Φ
′
Λ
s
(Φ
Λ
s
x
Λ
s
)
−(Φ
′
Λ
s
Φ
Λ
s
)
−1
Φ
′
Λ
s
Φ
Λ
s
−T
x
Λ
s
−T
(10)
= x
Λ
s
, (11)
where (10) follows from the fact that x
Λ
s
−T
= 0. From
this observation, we deduce that as long as at least one
correct index is found in each iteration of the gOMP, we can
ensure that the original signal is perfectly recovered within K
iterations. In practice, however, the number of correct indices
being selected is usually more than one so that the required
number of iterations is much smaller than K.
In order to observe the empirical performance of the gOMP
algorithm, we performed computer simulations. In our ex-
periment, we use the testing strategy in [16], [22] which
measures the effectiveness of recovery algorithms by checking
the empirical frequency of exact reconstruction in the noiseless
environment. By comparing the maximal sparsity level of
the underlying sparse signals at which the perfect recovery
is ensured (this point is often called critical sparsity [16]),
accuracy of the reconstruction algorithms can be compared
empirically. In our simulation, the following algorithms are
considered.
1) LP technique for solving ℓ
1
-minimization problem
(http://cvxr.com/cvx/).
2) OMP algorithm.
3) gOMP algorithm.
4) StOMP with false alarm control (FAC) based threshold-
ing (http://sparselab.stanford.edu/).
1
5) ROMP algorithm
(http://www.cmc.edu/pages/faculty/DNeedell).
1
Since FAC scheme outperforms false discovery control (FDC) scheme, we
exclusively use FAC scheme in our simulation.
10 20 30 40 50 60 70
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
Sparsity
Frequency of Exact Reconstruction
gOMP (N=3)
gOMP (N=6)
gOMP (N=9)
OMP
StOMP
ROMP
CoSaMP
LP
Fig. 1. Reconstruction performance for K-sparse Gaussian signal vector as
a function of sparsity K.
10 20 30 40 50 60 70
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
Sparsity
Frequency of Exact Reconstruction
gOMP (N=3)
gOMP (N=6)
gOMP (N=9)
OMP
StOMP
ROMP
CoSaMP
LP
Fig. 2. Reconstruction performance for K-sparse PAM signal vector as a
function of sparsity K.
6) CoSaMP algorithm
(http://www.cmc.edu/pages/faculty/DNeedell).
In each trial, we construct m ×n (m = 128 and n = 256)
sensing matrix Φ with entries drawn independently from
Gaussian distribution N(0,
1
m
). In addition, we generate a
K-sparse vector x whose support is chosen at random. We
consider two types of sparse signals; Gaussian signals and
pulse amplitude modulation (PAM) signals. Each nonzero
element of Gaussian signals is drawn from standard Gaussian
剩余14页未读,继续阅读
tongzs2017
- 粉丝: 2
- 资源: 3
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- 构建Cadence PSpice仿真模型库教程
- VMware 10.0安装指南:步骤详解与网络、文件共享解决方案
- 中国互联网20周年必读:影响行业的100本经典书籍
- SQL Server 2000 Analysis Services的经典MDX查询示例
- VC6.0 MFC操作Excel教程:亲测Win7下的应用与保存技巧
- 使用Python NetworkX处理网络图
- 科技驱动:计算机控制技术的革新与应用
- MF-1型机器人硬件与robobasic编程详解
- ADC性能指标解析:超越位数、SNR和谐波
- 通用示波器改造为逻辑分析仪:0-1字符显示与电路设计
- C++实现TCP控制台客户端
- SOA架构下ESB在卷烟厂的信息整合与决策支持
- 三维人脸识别:技术进展与应用解析
- 单张人脸图像的眼镜边框自动去除方法
- C语言绘制图形:余弦曲线与正弦函数示例
- Matlab 文件操作入门:fopen、fclose、fprintf、fscanf 等函数使用详解
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功