9
Over the years, numerous algorithms to recover the sparse signals have been proposed. Notable
one among them is a greedy algorithm. By the greedy algorithm, we mean an algorithm to make
a local optimal selection at each time with a hope to find the global optimum solution in the end.
Perhaps the most popular greedy algorithm is the orthogonal matching pursuit (OMP) [16]. In
the OMP algorithm, a column of the matrix H is chosen one at a time using a greedy strategy.
Specifically, in each iteration, a column maximally correlated with the (modified) observation is
chosen. Obviously, this is not necessarily optimal since the choice does not guarantee to pick
the column associated with the nonzero element of s. Let h
π
i
be the column chosen in the i-th
iteration, then the (partial) estimate of s is
ˆ
s
i
= H
†
i
y and the estimate of y is
ˆ
y
i
= H
i
ˆ
s
i
= H
i
H
†
i
y
where H
i
= [h
π
1
h
π
2
··· h
π
i
]. By subtracting
ˆ
y
i
from y, we obtain the modified observation
r
i
= y −
ˆ
y
i
, called the residual, used for the next iteration. By removing the contribution of
ˆ
s
i
from the observation vector y so that we focus on the identification of the rest nonzero elemenets
in the next iteration.
One can observe that when the column selection is right, the OMP algorithm can reconstruct
the original sparse vector accurately. This is because columns corresponding to the zero element
in s that do not contribute to the observation vector y can be removed from the system model
and as a result the underdetermined system can be converted into overdetermined system (see
Fig. 4). As mentioned, LS solution for the overdetermined system generates an accurate estimate
of the original sparse vector. Since the computational complexity is typically much smaller than
that of the LP techniques to solve (7) or (8), the greedy algorithm has received much attention
in recent years. Interestingly, even for the simple greedy algorithm like OMP algorithm, recent
results show that the recovery performance is comparable to the LP technique while requiring
much lower computational overhead [17]. We will discuss more on the sparse recovery algorithm
in Section IV-D.
D. Performance Guarantee
In order to analyze the performance guarantee of the sparse recovery algorithm, many analysis
tools have been suggested. For the sake of completeness, we briefly go over some of these tools
here. First, a simple yet intuitive property is the spark of the matrix H. Spark of a matrix H is
defined as the smallest number of columns of H that are linearly dependent. From this definition,
we see that a vector v in a null space N(H) = {v | Hv = 0} should satisfy kvk
0
≥ spark(H)
December 21, 2016 DRAFT
剩余57页未读，继续阅读
Dreama_CS
- 粉丝: 4
- 资源: 11
我的内容管理
展开
最新资源
- 最优条件下三次B样条小波边缘检测算子研究
- 深入解析：wav文件格式结构
- JIRA系统配置指南：代理与SSL设置
- 入门必备：电阻电容识别全解析
- U盘制作启动盘：详细教程解决无光驱装系统难题
- Eclipse快捷键大全：提升开发效率的必备秘籍
- C++ Primer Plus中文版：深入学习C++编程必备
- Eclipse常用快捷键汇总与操作指南
- JavaScript作用域解析与面向对象基础
- 软通动力Java笔试题解析
- 自定义标签配置与使用指南
- Android Intent深度解析：组件通信与广播机制
- 增强MyEclipse代码提示功能设置教程
- x86下VMware环境中Openwrt编译与LuCI集成指南
- S3C2440A嵌入式终端电源管理系统设计探讨
- Intel DTCP-IP技术在数字家庭中的内容保护
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
