《压缩感知技术研究进展..pdf》由会员分享，可在线阅读，更多相关《压缩感知技术研究进展..pdf（13页珍藏版）》请在三一文库上搜索。
1、压缩感知技术研究进展 摘要：信号采样是联系模拟信源和数字信息的桥梁. 人们对信息的巨量需求 造成了信号采样、传输和存储的巨大压力. 如何缓解这种压力又能有效提取承 载在信号中的有用信息是信号与信息处理中急需解决的问题之一. 近年国际上 出现的压缩感知理论(Compressed Sensing,CS) 为缓解这些压力提供了解决方 法. 本文综述了 CS 理论框架及关键技术问题, 并介绍了仿真实例、应用前景, 评述了其中的公开问题 , 对研究中现存的难点问题进行了探讨, 最后对 CS 技术做 了一下总结和展望 . 关键词：压缩感知；稀疏表示；观测矩阵；编码；解码 Advances in Theor
2、y and Application of Compressed Sensing Abstract：Sampling is the bridge between analog source signal and digital signal. With the rapid progress of information technologies, the demands for information are increasing dramatically. So the existing systems are very difficult to meet the challenges of
3、high speed sampling, large volume data transmission and storage. How to acquire information in signal efficiently is an urgent problem in electronic information fields. In recent year s, an emerging theory of signal acquirement. compressed sensing(CS) provides a golden opportunity for solving this p
4、roblem. This paper reviews the theoretical framework and the key technical problems of compressed sensing and introduces the latest developments of signal sparse representation, design of measurement matrix and reconstruction algorithm. Then this paper also reviews several open problems in CS theory
5、 and discusses the existing difficult problems. In the end, the application fields of compressed sensing are introduced. Key words: compressed sensing;sparse representation; the observation matrix; coding;decoding 一、 引言 在过去的半个世纪里，奈奎斯特采样定理几乎支配着所有的信号或图像等 的获取、处理、存储以及传输。它要求采样频率必须大于或等于信号带宽的两 倍，才能不失真的重构原始
6、信号。在许多实际应用中，例如高分辨率的数码装 置及超带宽信号处理，高速采样产生了庞大的数据，为了降低存储，处理或传 输成本，只保留其中少量的重要数据。由于采样后得到的大部分数据都被丢弃 了，所以这种方式造成了采样资源的严重浪费。设想如果在采样的同时直接 提取信号的少量重要信息，就可以大大降低采样频率，节约资源，提高效率而 且仍能够精确重构原始信号或图像。这就是 Donoho 、Candes 以及Tao等人提出压 缩感知（ Compressed Sensing、Compressive Sampling或Compressive Sensing， CS ）理论的主要思想。压缩感知理论指出：如果信号在
7、某个变换域是稀疏的或 可压缩的，就可以利用一个与变换基不相关的观测矩阵将变换所得的高维信号 投影到一个低维空间上，根据这些少量的观测值，通过求解凸优化问题就可以 实现信号的精确重构。 在传统理论的指导下， 信号X 的编解码过程如图 1 所示：编码端首先获得 X 的N 点采样值，经变换后只保留其中K 个最大的投影系数并对它们的幅度和位 置编码，最后将编得的码值进行存储或传输。解压缩仅是编码过程的逆变换。 实际上，采样得到的大部分数据都是不重要的，即K 值很小，但由于奈奎斯特 采样定理的限制， 采样点数 N 可能会非常大， 采样后的压缩是造成资源浪费的根 本所在。 CS 很好的解决了这一问题， 它
8、将信号的采样、 压缩及编码合并在了同一步 骤中，不经过 N 点采样的中间过程而直接得到信号的表示，其编解码过程如图 2 所示。可压缩信号 X 通过一个线性观测过程获得M 个观测值后直接进行存储或传 输。在满足一定的条件下接收端可以根据这M 个观测值通过一个非线性优化过 程恢复出原信号 X。 二、压缩感知的基本理论及核心问题 假设有一信号)( N Rff，长度为 N ，基向量为),.,2, 1(Ni i ，对信号进 行变换： faf i N i i 或 1 显然 f 是信号在时域的表示，是信号在域的表示。信号是否具有稀疏 性或者近似稀疏性是运用压缩感知理论的关键问题，若(1) 式中的只有 K 个
9、是 非零值)(KN者仅经排序后按指数级衰减并趋近于零，可认为信号是稀疏 的。信号的可稀疏表示是压缩感知的先验条件。在已知信号是可压缩的前提下， 压缩感知过程可分为两步： (1) 设计一个与变换基不相关的 )(NMNM 维测量矩阵对信号进行观 测，得到 M 维的测量向量。 (2) 由 M 维的测量向量重构信号。 2.1 信号的稀疏表示 文献 4 给出稀疏的数学定义：信号X 在正交基下的变换系数向量为 X T ，假如对于20p和0R，这些系数满足： R pp i ip /1 )|(| 则说明系数向量在某种意义下是稀疏的 文献1 给出另一种定义： 如果 变换系数 ii X, 的支撑域 0; i i
10、的势小于等于 K ， 则可以说信号 X 是 K 项稀疏。 如何找到信号最佳的稀疏域?这是压缩感知理论应用的基础和前提，只有选择合 适的基表示信号才能保证信号的稀疏度，从而保证信号的恢复精度。在研究信 号的稀疏表示时，可以通过变换系数衰减速度来衡量变换基的稀疏表示能力。 Candes 和Tao研究表明，满足具有幂次(power-law) 速度衰减的信号，可利用压 缩感知理论得到恢复。 最近几年，对稀疏表示研究的另一个热点是信号在冗余字典下的稀疏分 解这是一种全新的信号表示理论：用超完备的冗余函数库取代基函数，称之 为冗余字典，字典中的元素被称为原子字典的选择应尽可能好地符合被逼近 信号的结构，其
11、构成可以没有任何限制从从冗余字典中找到具有最佳线性组 合的K项原子来表示一个信号，称作信号的稀疏逼近或高度非线性逼近 13,12 。 目前信号在冗余字典下的稀疏表示的研究集中在两个方面：(1) 如何构造一 个适合某一类信号的冗余字典；(2) 如何设计快速有效的稀疏分解算法这两个 问题也一直是该领域研究的热点，学者们对此已做了一些探索，其中以非相干 字典为基础的一系列理论证明得到了进一步改进西安电子科技大学的石光明 教授也对稀疏表示问题进行了认真研究，并基于多组正交基级联而成的冗余字 典提出一种新的稀疏分解方法 17 。 2.2 信号的观测矩阵 用一个与变换矩阵不相关的 )(NMNM 测量矩阵对
12、信号进行线性投 影，得到线性测量值y ： fy 测量值 y 是一个 M 维向量，这样使测量对象从N 维降为 M 维。观测过程 是非自适应的即测量矩阵少的选择不依赖于信号f。测量矩阵的设计要求信号 从f转换为 y 的过程中，所测量到的K 个测量值不会破坏原始信号的信息，保 证信号的精确重构。 由于信号f是是可稀疏表示的，上式可以表示为下式： fy 其中是一个NM矩阵。上式中，方程的个数远小于未知数的个数，方 程无确定解，无法重构信号。但是，由于信号是K稀疏，若上式中的满足有限 等距性质 (Restricted Isometry Property ，简称RIP)，即对于任意 K稀疏信号f 和常数)
13、1 ,0( k ，矩阵满足： kk f f 1 | | 1 2 2 2 2 则K个系数能够从 M 个测量值准确重构。 RIP性质的等价条件是测量矩阵和 稀疏基不相关。目前，用于压缩感知的测量矩阵主要有以下几种：高斯随机 ，傅立叶随机矩阵，哈达玛矩阵，一致球矩 压缩感知理论能够通过对上式的逆问题先求解稀 的信号 范数下求解的最优化问题： l | 0 从而得到稀疏系数的估计。由于上式的求解是个 化问题与信号的稀疏分解十分类似，所以有学者从信号稀疏分解的相关理论中 寻找更有效的求解途径。 文献10 表明， 1 l最小范数下在一定条件下和 0 l最小范 数具有等价性，可得到相同的解。那么上式转化为 1
14、 l最小范数下的最优化问题： yts l .| 1 min 1 l最小范数下最优化问题又称为基追踪(BP)，其常用实现算法有：内点法 和梯度投影法。内点法速度慢， 但得到的结果十分准确： 而梯度投影法速度快， 但没有内点法得到的结果准确 14 。二维图像的重构中，为充分利用图像的梯度 结构。可修正为整体部分(Total Variation，TV)最小化法。由于 1 l最小范数下 的算法速度慢，新的快速贪婪法被逐渐采用，如匹配追踪法(MP)和正交匹配追 踪法(OMP) 。此外，有效的算法还有迭代阈值法以及各种改进算法。 三、压缩感知仿真实例 对256256大小的 8bit 灰度lena 图像进行
15、仿真计算，由于数据量过大，将图像 分为1616大小的分块进行计算， 稀疏矩阵采用 DCT 矩阵，观测矩阵采用高斯随 机矩阵，重构算法采用 OMP （正交匹配追踪）算法。 MATLAB 代码如下： 在MATLAB R2001b 中的计算结果如下： 采样率 0.7 0.5 评价重构后的图像质量。 不同采样率下的计算时间与计算误差如下图所示： 能从少量的非相关观测值中高效获取可压缩信号的信息，CS 的这一特点决 定了其应用的广泛性。 CS 的应用领域涉及数据压缩、模拟/ 信息的转换、 压缩 成像、信道编码、信道估计、生物传感、语音识别、雷达成像、雷达遥感、学 习理论及模式识别等诸多领域。 在压缩成像
16、方面， RICE 大学已成功研制了“单像素”压缩数码照相机，该 相机不像传统相机那样获取原始信号的N 个像素值，而是直接获取 M 个随机线性 观测值，在实践中为取代传统相机迈出了实质性的一步。在通信领域，压缩感 知也有着强大的生命力，由于无线多径信道一般情况下是稀疏的，即使在时延 扩展很大时，大幅度的径的个数也很少，因此利用少量的导频就能获取未知信 道的频域响应估计。此外压缩感知理论还可用于通信信道的错误检测、传感网 络的分布式信源编码、认知无线电中的频谱感知等。 五、 研究的公开问题 5.1 p2 范数优化问题 压缩感知理论在图像压缩编码等方面也应该有很广泛的前景, 但由于信号 的恢复方法是
17、建立在 12范数意义下 , 数据之间还有很大的冗余性没有去除, 相 比传统的小波变换编码 , 压缩感知理论应用于图像压缩的效果还不理想. p2 范 数的优化是提高基于压缩感知理论的压缩算法效果的必经之路. p2 范数的优化 方法是一个公开问题 ( open problem) , 对它的研究将推动压缩感知理论在压 缩方面的应用 , 具有很深远的意义 . p2 范数意义下的优化问题是一个凸函数优 化问题 , 目前已有一些成熟的算法 , 但p2范数的优化是一个非凸函数的优化问 题, 其中有很多数学问题有待解决. 有关p2范数非凸函数优化问题 , 也有一些 学者开展研究 . 如RickChartran
18、d用典型的合成数据做了一些实验, 表明在一 定的稀疏误差范围内, 可以得到最小值 . 在文献 19 中, 他进一步给出了变换 基空间内的系数严格的等距条件(restricted isometry) , 由于有了严格的约 束, 完全适合于大多数实际的信号. 笔者期望通过借用自然优化计算以及将p2 范数非凸函数转换为近似凸函数优化等方法, 提出一种新的求解 p2范数范数的 优化问题 , 以实现在 p2范数意义下的压缩感知理论的信号恢复, 最大可能减少 信号的冗余 . 该思路正在研究之中 . 5.2 观测矩阵与恢复性能关系 前面提到 , 观测矩阵与稀疏变换基的不相干特性是压缩感知理论具有良好 性能的
19、基础 . 由于随机高斯分布的观测矩阵具有与其它固定基都不相关的特性 而被广泛采用 . 但在实际的应用中, 这种观测矩阵存在存储矩阵元素容量巨 大、计算复杂度高的缺点 . 文献 20 提出一种部分傅立叶变换采样的方法. 它首先对信号进行傅立叶变换再对变换系数进行随机抽取. 这种随机抽取使得 各观测值具有随机不相关的特性. 由于变换时可以采用快速算法而使得计算量 大大降低 . 但由于傅立叶基仅与在空域稀疏的信号不相干, 故这种观测矩阵的 应用范围受到很大的限制. 此外, 采用随机滤波器滤波也是一种有效的观测 方法 , 不过目前仍缺乏理论基础, 也缺少对其性能的详细分析. 文献 21将 伪高斯矩阵和
20、部分傅立叶方法巧妙的结合在一起, 提出了一种结构化的随机观 测矩阵设计方法 , 这种观测矩阵具有与所有基不相干的特性, 同时也有较快的 计算速度 . 总结以上的工作可以得出如下结论: 观测矩阵的随机不相关特性是正确恢 复信号的一个充分条件 , 观测矩阵和信号的高度不相干是有效恢复信号的保证. 但是, 现在仍然无法确定随机不相关特性是否是最优恢复信号的必要条件, 这 仍是一个公开问题 . 另外, 如何衡量观测矩阵的不相干特性, 以及它们与恢复 性能之间的关系也是一个尚未解决的问题. 另外, 自适应的观测矩阵设计也是观测矩阵设计的一个重要方面. 在众 多有关压缩感知理论的文献中, 大部分的观测矩阵
21、都是预先设计好的, 不需要 根据观测信号而自适应变化. 实际上 , 如果能够进行自适应的观测, 压缩感知 的压缩性能可以得到进一步的提高. 在文献 22 中, 作者用 Bayes 估计的观 点对压缩感知做出了一种全新的解释. 在文献中 , 压缩感知的解的可信度可以 通过微分熵来衡量 , 这样在已有观测的基础上, 下一次最优的观测向量应该使 问题解的微分熵下降最快, 它可以由已有的观测向量和观测值唯一确定. 而 且, 幸运的是这一特性在编码端和解码端是同样的. 由于对观测矩阵的最优化 设计 ,Bayesian CS 与使用普通的随机观测矩阵相比, 在同等观测次数的情况 下, 性能得到了很大的提高
22、 . 当然这也付出了一定的代价, 计算最优观测向量 需要很大的计算量 , 所以能够简捷有效地确定最优观测向量仍是这方面的一个 有待解决的问题 . 5.3 分布式压缩感知理论 ( Distr ibuted CompressedSensing, DCS) 目前, 针对单个信号的压缩感知的研究和应用已经开展得比较深入, 但是 对分布式信号的处理仍然研究得不够. 例如, 对于一个包含大量传感器节点的 传感器网络 , 每个传感器都会采集大量的数据, 这些数据将会传输到一个控制 中心, 也会在各个节点之间传输. 显然, 在这种分布式传感器网络中, 数据传 输对功耗和带宽的需求非常大, 那么, 如何对分布式
23、信号进行压缩以减少通信 压力成为非常紧迫的需求. 2006年,Haupt 和Nowak 将压缩感知理论应用到多个信号的环境中 , 然而 他们的方法仅研究了多个信号的互相关性, 却没有考虑单个信号的内相关性. Baron等人在压缩感知理论的基础上提出了分布式压缩感知(DCS) 18 , 进一 步扩展了压缩感知理论的应用, 将单信号的压缩采样扩展到了信号群的压缩采 样, 它着重研究如何利用信号内相关性和互相关性对多个信号进行联合重构. 这种联合重构的重要意义在于, 相对于压缩感知 , 分布式压缩感知可节约相当 可观的观测数目 . 文献 18 中的实验结果表明对于两个相关的信号可节约的 观测数目大约
24、为 30%. DCS 理论建立在一个称之为信号群的/ 联合稀疏 ( JSM) 0 概念上 . 它指出 , 如果多个信号都在某个基下稀疏, 并且这些信号彼此有关 , 那么每个信号都能 够通过利用另一个不相关基( 例如一个随机矩阵 ) 进行观测和编码 , 得到远少 于信号长度的编码 . 将每个编码后的少量数据传输到解码端, 那么在适当的条 件( 如JSM21) 下, 解码端利用接收到的少量数据就能够精确重建每一个信号. 文献 18 系统地阐述了 DCS 理论及其应用 , 提出了相应的压缩感知方法 及恢复算法 , 并采用稀疏的随机投影矩阵作为观测矩阵, 详细分析了分布式压 缩感知理论的观测过程 ,
25、而文献 23 则从重构误差估计的角度对分布式压缩 感知理论进行了研究 . DCS 理论为分布式信号的处理提供了新的方法, 目前的热点和难点主要集 中在如何将其应用到各种复杂的实际传感器网络中. 在某种意义上 , DCS 是一 种分布式信源压缩的框架, 它在很长时间内都将是一个具有挑战性的公开难 题. 六 总结与展望 压缩感知理论利用了信号的稀疏特性, 将原来基于奈奎斯特采样定理的信 号采样过程转化为基于优化计算恢复信号的观测过程. 也就是利用长时间积分 换取采样频率的降低 , 省去了高速采样过程中获得大批冗余数据然后再舍去大 部分无用数据的中间过程, 从而有效缓解了高速采样实现的压力, 减少了
26、处 理、存储和传输的成本 , 使得用低成本的传感器将模拟信息转化为数字信息成 为可能 . 这种新的采样理论将可能成为将采样和压缩过程合二为一的方法的理 论基础 . 本文对压缩感知理论框架的全过程进行了描述, 详细阐述了压缩感知理论 所涉及的关键技术 , 综述了国内外研究成果、存在的公开问题及最新的相关理 论扩展 , 如冗余字典下的压缩感知理论、模拟2信息理论、分布式压缩感知理论 等. 并对其中的问题进行了概括性讨论. 压缩感知理论的研究已经有了一些成果, 但是仍然存在大量的问题需要研 究. 概括为以下几个方面 : (1) 对于稳定的重构算法是否存在一个最优的确定性的观测矩阵; (2) 如何构造
27、稳定的、计算复杂度较低的、对观测次数限制较少的重构算 法来精确地恢复可压缩信号; (3) 如何找到一种有效且快速的稀疏分解算法是冗余字典下的压缩感知理 论的难点所在 ; (4) 如何设计有效的软硬件来应用压缩感知理论解决大量的实际问题, 这 方面的研究还远远不够 ; (5) 对于p2范数优化问题的求解研究还远远不够; (6) 含噪信号或采样过程中引入噪声时的信号重构问题也是难点所在, 研 究结果尚不理想 . 此外 , 压缩感知理论与信号处理其它领域的融合也远不够, 如信号检测、特征提取等 . CS 理论与机器学习等领域的内在联系方面的研究工 作已经开始 . 压缩感知理论是新诞生的, 虽然还有许
28、多问题待研究, 但它是对传统信号 处理的一个极好的补充和完善, 是一种具有强大生命力的理论, 其研究成果可 能对信号处理等领域产生重大影响 参考文献 1 石光明 . 刘丹华 . 高大化 . 刘哲 . 林杰 . 王良君压缩感知理论及其研究进展-ACTA Electronica Sinica 2009， 37(5) 2张 锐基 于 压 缩 感 知 理 论 的 图 像 压 缩 初 步 研 究 -Computer Knowledge And Technology 2010，6(4) 3Candes E, Romberg J, Tao T. Robust uncertainty principles:
29、Exact signal reconstruction from highly incomplete frequency informationJ. IEEE Trans. Information Theory, 2006, 52(4): 489-509 4E Candes and J Romberg, Quantitative robust uncentainty principles and optimally sparse decompositionsJ. Foundations of Comput Math, 2006, 6(2): 227-218 5E Cand s.T Tao Ne
30、ar optimal signal recovery from random projections:Universal encoding strategies 2006(12) 6D L Donoho Compressed sensing 2006(04) 7B Kashin.The widths of certain finite dimensional sets and classes of smooth functionsJIzv Akad Nauk SSSR.1977, 41(2):334-351 8E Cand s Compressive sampling 2006 9 喻玲娟 .
31、 谢晓春压缩感知理论简介-Video Engineering 2008，32(12) 10DONOHO D.TSAIG Y Extensions of compressed sensing 2006(03) 11Guangming Shi.Jie Lin.Xuyang Chen.Fei Qi,Danhua Liu Li Zhang UWB echo signal detection with ultra low rate sampling based on compressed sensing 2008(04) 12 张春梅 . 尹忠科 . 肖明霞基于冗余字典的信号超完备表示与稀疏分解- 科学
32、通报 2006(06) 13V Temlyakov Nonlinear Methods of ApproximationIMI Research Reports 2001 14FIGUEIREDO M A T.NOWAK R D.WRIGHT S J Gradient projection for sparse reconstruction:application to compressed sensing and other inveme problems 2007(04) 15S Mallat.杨力华 . 戴道清 . 黄文良信号处理的小波导引 2002 16 覃凤清 . 数字图像压缩综述J
33、.宜宾学院学报,2006(6) 17 刘丹华 . 石光明 . 周佳社一种冗余字典下的信号稀疏分解新方法- 西安电子科技大 学学报（自然科学版）2008(02) 18 D Baron, M B Wakin, M Duarte, etc. Distributed compressed sensing OL . DCS112005. 19 R Chartrand. Exact Reconstruction of Sparse Signals via Non2 convex Minimization J . IEEE Signal Processing Letters. 2007, 14( 10) :
34、 7072710. 20 E J Candes, J Romberg. Sparsity and incoherence in compres2 sive sampling J . Inverse Problems. 2007, 23( 3) : 9692985. 21 T T Do, T D. Tran , L Gan. Fast compressive sampling with structurally random matrces OL . 22 S Ji, Y Xue, L Carin. Bayesian compressive sensing J . IEEE Transactio
35、ns Signal Processing, 2008, 56( 6) : 234622356. 23 W Wang, M Garofalakis, K Ramchandran. Distributed sparse random projections for refinable approxim2ation A . Proceed2 ings of the Sixth International Symposium on Information Pro2 cessing in Sensor Networks, ( IPSN2007) C . New York: As2 sociation f
36、or Computing Machinery, 2007. 3312339. 论文题目压缩感知技术研究进展 中文摘要 信号采样是联系模拟信源和数字信息的桥梁. 人们对信息的巨量需求造成了信 号采样、传输和存储的巨大压力. 如何缓解这种压力又能有效提取承载在信号 中的有用信息是信号与信息处理中急需解决的问题之一. 近年国际上出现的压 缩感知理论 (Compressed Sensing,CS) 为缓解这些压力提供了解决方法. 本文 综述了 CS 理论框架及关键技术问题 , 并介绍了仿真实例、应用前景, 评述了 其中的公开问题 , 对研究中现存的难点问题进行了探讨, 最后对 CS 技术做了一 下总结
37、和展望 关键词：压缩感知；稀疏表示；观测矩阵；编码；解码 英文题目 Advances in Theory and Application of Compressed Sensing 英文摘要 Sampling is the bridge between analog source signal and digital signal. With the rapid progress of information technologies, the demands for information are increasing dramatically. So the existing system
38、s are very difficult to meet the challenges of high speed sampling, large volume data transmission and storage. How to acquire information in signal efficiently is an urgent problem in electronic information fields. In recent year s, an emerging theory of signal acquirement. compressed sensing(CS) p
39、rovides a golden opportunity for solving this problem. This paper reviews the theoretical framework and the key technical problems of compressed sensing and introduces the latest developments of signal sparse representation, design of measurement matrix and reconstruction algorithm. Then this paper also reviews several open problems in CS theory and discusses the existing difficult problems. In the end, the application fields of compressed sensing are introduced. 英文关键词 compressed sensing;sparse representation; the observation matrix; coding;decoding