压缩感知-----介绍

1、2022-6-261压缩感知概述压缩感知概述Introduction to Compressive Sensing22022-6-26目录目录一、背景与现状一、背景与现状 理论产生背景 研究现状二、压缩感知理论介绍二、压缩感知理论介绍 压缩感知的基本思想 压缩感知的数学模型 压缩感知要解决的问题三、应用与展望三、应用与展望 压缩感知的初步应用 压缩感知研究的公开问题 压缩感知的总结与展望 2022-6-263 一、背景现状一、背景现状42022-6-261.1 理论产生背景理论产生背景1、背景现状、背景现状 一方面， 在奈奎斯特( Nyquist) 采样定理为基础的传统数字信号处理框架下，若要

2、从采样得到的离散信号中无失真地恢复模拟信号，采样速率必须至少是信号带宽的两倍。然而，随着当前信息需求量的日益增加，信号带宽越来越宽，在信息获取中对采样速率和处理速度等提出越来越高的要求，因而对宽带信号处理的困难在日益加剧。例如高分辨率地理资源观测， 其巨量数据传输和存储就是一个艰难的工作。52022-6-261.1 理论产生背景理论产生背景1、背景现状、背景现状原始图像采样数据采样压缩数据传输解压缩数据传输恢复图像通过显示器显示图像 另一方面， 在实际应用中, 为了降低存储、处理和传输的成本, 人们常采用压缩方式以较少的比特数表示信号, 大量的非重要的数据被抛弃。这种高速采样再压缩的过程浪费了

3、大量的采样资源。 62022-6-261.1 理论产生背景理论产生背景1、背景现状、背景现状大部分冗余信息在采集后被丢弃采样时造成很大的资源浪费能否直接采集不被丢弃的信息？72022-6-261.1理论产生背景理论产生背景1、背景现状、背景现状被感知对象重建信号压缩感知名词解释：压缩感知直接感知压缩后的信息基本方法：信号在某一个正交空间具有稀疏性（即可压缩性），就能以较低的频率（远低于奈奎斯特采样频率）采样该信号，并可能以高概率重建该信号。82022-6-261.2 研究现状研究现状1、背景现状、背景现状2006Robust Uncertainty Principles：Exact Signa

4、l Reconstruction fromHighly Incomplete Frequency InformationTerence Tao、Emmanuel Cands2006Compressed SensingDavid Donoho2007Compressive SensingRichard Baraniuk上述文章奠定了压缩感知的理论基础。国内也将其翻译成压缩传感或压缩采样。92022-6-261.2 研究现状研究现状1、背景现状、背景现状u理论一经提出，就在信息论、信号处理、图像处理等领域受到高度关注。u在美国、英国、德国、法国、瑞士、以色列等许多国家的知名大学(如麻省理工学院、斯

5、坦福大学、普林斯顿大学、莱斯大学、杜克大学、慕尼黑工业大学、爱丁堡大学等等)成立了专门的课题组对CS进行研究。u此外，莱斯大学还建立了专门的CompressiveSensing网站，及时报道和更新该方向的最新研究成果。102022-6-261.2 研究现状研究现状1、背景现状、背景现状u西安电子科技大学石光明教授在电子学报发表综述文章，系统地阐述了压缩传感的理论框架以及其中涉及到的关键技术问题。燕山大学练秋生教授的课题组针对压缩感知的稀疏重建算法进行了系统深入的研究，提出一系列高质量的图像重建算法。中科院电子所的方广有研究员等，探索了压缩感知理论在探地雷达三维成像中的应用。u除此之外，还有很多

6、国内学者在压缩感知方面做了重要的工作，如清华大学、天津大学、国防科技大学、厦门大学、湖南大学、西南交通大学、南京邮电大学、华南理工大学、北京理工大学、北京交通大学等等单位，在此不一一列举。2022-6-2611 二、压缩感知理论介绍二、压缩感知理论介绍122022-6-262.1 压缩感知的基本思想压缩感知的基本思想2、压缩感知理论介绍、压缩感知理论介绍 压缩感知理论与传统奈奎斯特采样定理不同， 它指出，只要信号是可压缩的或在某个变换域是稀疏的， 那么就可以用一个与变换基不相关的观测矩阵将变换所得高维信号投影到一个低维空间上，然后通过求解一个优化问题就可以从这些少量的投影中以高概率重构出原信号

7、，可以证明这样的投影包含了重构信号的足够信息。在该理论框架下，采样速率不决定于信号的带宽， 而决定于信息在信号中的结构和内容。132022-6-262.2 压缩感知的数学模型压缩感知的数学模型2、压缩感知理论介绍、压缩感知理论介绍 若将N维实信号 在某组正交基 下进行展开，即： 1NRx Nii1Niiix1xxTiii ,其中，展开系数写成矩阵形式可以得到：（2）（1）x142022-6-262.2 压缩感知的数学模型压缩感知的数学模型2、压缩感知理论介绍、压缩感知理论介绍这里NNR),.,(321为正交基字典矩阵，满足ITT，展开系数向量为TN),.,(21假设系数向量是K稀疏的，即其中非

8、零系数的个数KN，那么采用另一个与正交基不相关的矩阵：MN（MN）（这里的每一行可以看作是一个传感器，它与系数相乘，获取了信号的部分信息），对信号执行一个压缩观测：xy（3）152022-6-262.2 压缩感知的数学模型压缩感知的数学模型2、压缩感知理论介绍、压缩感知理论介绍就可以得到M个线性观测（或投影）MRy，这些少量线性投影中则包含了重构信号X的足够信息，如下图所示：162022-6-262.2 压缩感知的数学模型压缩感知的数学模型2、压缩感知理论介绍、压缩感知理论介绍 从y中恢复x是一个解线性方程组的问题，但从方程（3）上看，这似乎是不可能的，因为这是一个未知数个数大于方程个数的病态

9、方程，存在无穷多个解。但是，将式（2）带入式（3），记CS信息算子 可以得到： CSACSAy（4） 虽然从y中恢复 也是一个病态问题，但是因为系数 是稀疏的，这样未知数的个数就大大减少，使得信号重构成为可能。那么在什么情况下式（4）的解是存在的呢？172022-6-262.2 压缩感知的数学模型压缩感知的数学模型2、压缩感知理论介绍、压缩感知理论介绍 可以证明：只要矩阵 中任意2K列都是线性独立的，那么至少存在一个K-稀疏的系数向量满足 。换言之，在满足上述要求的情况下，通过解一个非线性优化问题就能从观测y、观测矩阵 和字典矩阵 中近乎完美的重建信号x。信号压缩感知的过程如下图所示： CSA

10、CSAy 182022-6-262.3 压缩感知要解决的问题压缩感知要解决的问题2、压缩感知理论介绍、压缩感知理论介绍 从上述数学模型可知, 压缩感知理论的实现包含三个关键要素：稀疏性、非相关观测、非线性优化重建，其中信号的稀疏性是压缩感知的必备条件, 非相关观测是压缩感知的关键, 非线性优化是压缩感知重建信号的手段。 要解决的问题有以下三方面： 1、信号的稀疏表示 2、观测矩阵的设计 3、信号重构算法的设计192022-6-262.3 压缩感知要解决的问题压缩感知要解决的问题2、压缩感知理论介绍、压缩感知理论介绍 1、信号的稀疏表示 稀疏表示是信息优化建模的终极目标, 也是信息处理中一个古老

11、而又崭新的课题, 利用稀疏性可以解决信号处理中许多复杂的问题, 各种数学分析和信号处理的理论为字典的构建提供了许多良好的工具,如下图所示。稀疏表示的研究兴起于二十世纪九十年代,在本世纪初得到蓬勃发展, 压缩感知的提出更是为其提供了工程应用的土壤, 极大地丰富了该领域的研究成果。202022-6-262.3 压缩感知要解决的问题压缩感知要解决的问题2、压缩感知理论介绍、压缩感知理论介绍 1、信号的稀疏表示 212022-6-262.3 压缩感知要解决的问题压缩感知要解决的问题2、压缩感知理论介绍、压缩感知理论介绍 1、信号的稀疏表示 研究现状：（1）多种变换域分析方法为稀疏表示提供了可能。（2）

12、许多信号，诸如自然图像，本身就存在着变换域稀疏性。（3）信号在冗余字典下的稀疏表示 目前信号在冗余字典下的稀疏表示的研究集中在两个方面: (a)如何构造一个适合某一类信号的冗余字典; (b)如何设计快速有效的稀疏分解算法. 222022-6-262.3 压缩感知要解决的问题压缩感知要解决的问题2、压缩感知理论介绍、压缩感知理论介绍 2、观测矩阵的设计 目前, 对观测矩阵的研究是压缩感知理论的一个重要方面。在该理论中， 对观测矩阵的约束是比较宽松的， Donoho在中给出了观测矩阵所必需具备的三个条件， 并指出大部分一致分布的随机矩阵都具备这三个条件, 均可作为观测矩阵， 如：部分Fourier

13、集、部分Hadamard集、一致分布的随机投影(uniform Random Projection)集等，这与对有限等距性质进行研究得出的结论相一致。但是， 使用上述各种观测矩阵进行观测后, 都仅仅能保证以很高的概率去恢复信号， 而不能保证百分之百地精确重构信号。 对于任何稳定的重构算法是否存在一个真实的确定性的观测矩阵仍是一个有待研究的问题。232022-6-262.3 压缩感知要解决的问题压缩感知要解决的问题2、压缩感知理论介绍、压缩感知理论介绍 3、信号重构算法的设计 目前为止出现的重构算法都可以归入以下3大类： （1）贪婪追踪算法：这类方法是通过每次迭代时选择一个局部最优解 来逐步逼近

14、原始信号，这类算法包括MP（Matching Pursuit,匹配 追踪）算法，OMP（Orthogonal Matching Pursuit, 正交匹配 追踪)算法，分段OMP算法和正则化OMP算法。 （2）凸松弛法: 这类方法通过将非凸问题转化为凸问题求解找到信号 的逼近, 如BP算法, 内点法， 梯度投影方法和迭代阈值法。 （3）组合算法：这类方法要求信号的采样支持通过分组测试快速重建， 如傅立叶采样， 链式追踪和HHS(HeavgHitters onSteroids)追踪等。242022-6-262.3 压缩感知要解决的问题压缩感知要解决的问题2、压缩感知理论介绍、压缩感知理论介绍 3

15、、信号重构算法的设计 可以看出， 每种算法都有其固有的缺点。凸松弛法重构信号所需的观测次数最少， 但往往计算负担很重。贪婪追踪算法在运行时间和采样效率上都位于另两类算法之间。 重构算法和所需的观测次数密切相关。当前， 压缩感知理论的信号重构问题的研究主要集中在如何构造稳定的、计算复杂度较低的、对观测数量要求较少的重构算法来精确地恢复原信号。2022-6-2625 三、应用与展望三、应用与展望262022-6-263.1 压缩感知的初步应用压缩感知的初步应用3、应用与展望、应用与展望 直接信息采样特性使得压缩感知理论具有巨大的吸引力和应用前景， 随之出现的是相关的理论完善和实践成果。应用研究已经

16、涉及到众多领域，如： CS雷达、DCS(DistributedCompressedSensing)理论、无线传感网络、图像采集设备的开发、医学图像处理、生物传感、Analog 2 to 2 Information、光谱分析、超谱图像处理等。 1、在成像方面, 压缩感知理论的出现激起了人们研究新型传感器的 热情, 压缩感知采样对昂贵的成像器件的设计产生重大影响。 2、在地震勘探成像和核磁共振成像中, 对目标信号将有望采用少量 的随机观测次数就能获得高精度重构。272022-6-263.1 压缩感知的初步应用压缩感知的初步应用3、应用与展望、应用与展望 3、取代传统数码相机拍照时采集大量像素的一种

17、新型单像素CS相机 已经得到论证。 4、美国Rice 大学也已经研制出单像素相机。 5、在宽带无线频率信号分析中, 由于目前A/D转换器技术的限制, 可以 用远低于奈奎斯特采样频率的速率采集信号。 6、在X射线和生物医学中, 可以通过采集远少于未知像素点数的观测样 本来获取感兴趣的图像信息。 7、基因表达研究也开始使用压缩感知理论, 试图从少量的观测样本中, 例如几十种来推断成千上万种基因的表达。282022-6-263.2 压缩感知研究的公开问题（摘自压缩感知研究的公开问题（摘自09年文献）年文献）3、应用与展望、应用与展望1、p2范数优化问题 压缩感知理论在图像压缩编码等方面也应该有很广泛

18、的前景，但由于信号的恢复方法是建立在p2范数意义下，数据之间还有很大的冗余性没有去除， 相比传统的小波变换编码，压缩感知理论应用于图像压缩的效果还不理想， p2范数的优化是提高基于压缩感知理论的压缩算法效果的必经之路。 p2范数的优化方法是一个公开问题(open problem)，对它的研究将推动压缩感知理论在压缩方面的应用，具有很深远的意义。292022-6-263.2 压缩感知研究的公开问题（摘自压缩感知研究的公开问题（摘自09年文献）年文献）3、应用与展望、应用与展望2、含噪信号的恢复算法 在实际工程应用中, 待处理信号一般都不同程度地受到各种噪声的污染。含噪信号不是严格的稀疏信号, 但

19、是仍属于可压缩信号。 现有的压缩感知理论中,恢复信号的最基本依据是信号在某个变换空间的分解系数是稀疏的, 而噪声的存在则破坏了信号在空间中的稀疏性。在使用优化方法恢复信号时, 如果对含噪信号采用单一的稀疏性约束原则, 则无法有效恢复原始稀疏信号。这时, 压缩感知理论仍然可以采用其它有效的恢复信号的方法, 主要的不同之处在于恢复过程所使用的优化目标函数的形式不同, 参数的设置不同. 不同的优化目标函数使得信号的恢复效果也不尽相同.302022-6-263.2 压缩感知研究的公开问题（摘自压缩感知研究的公开问题（摘自09年文献）年文献）3、应用与展望、应用与展望3、观测矩阵与恢复性能关系 观测矩阵

20、与稀疏变换基的不相干特性是压缩感知理论具有良好性能的基础。由于随机高斯分布的观测矩阵具有与其它固定基都不相关的特性而被广泛采用。但在实际的应用中, 这种观测矩阵存在存储矩阵元素容量巨大、计算复杂度高的缺点。 观测矩阵的随机不相关特性是正确恢复信号的一个充分条件, 观测矩阵和信号的高度不相干是有效恢复信号的保证。但是, 现在仍然无法确定随机不相关特性是否是最优恢复信号的必要条件, 这仍是一个公开问题。另外, 如何衡量观测矩阵的不相干特性, 以及它们与恢复性能之间的关系也是一个尚未解决的问题。312022-6-263.2 压缩感知研究的公开问题（摘自压缩感知研究的公开问题（摘自09年文献）年文献）

21、3、应用与展望、应用与展望4、分布式压缩感知理论(Distributed Compressed Sensing, DCS) 目前， 针对单个信号的压缩感知的研究和应用已经开展得比较深入, 但是对分布式信号的处理仍然研究得不够。 例如， 对于一个包含大量传感器节点的传感器网络，每个传感器都会采集大量的数据， 这些数据将会传输到一个控制中心， 也会在各个节点之间传输。 显然， 在这种分布式传感器网络中， 数据传输对功耗和带宽的需求非常大， 那么， 如何对分布式信号进行压缩以减少通信压力成为非常紧迫的需求。 322022-6-263.3 压缩感知研究的总结与展望压缩感知研究的总结与展望3、应用与展望、应用与展望 压缩感知理论利用了信号的稀疏特性, 将原来基于奈奎斯特采样定理的信号采样过程转化为基于优化计算恢复信号的观测过程。 也就是利用长时间积分换取采样频率的降低, 省去了高速采样过程中获得大批冗余数据然后再舍去大部分无用数据的中间过程,