压缩感知介绍.ppt

1、People Hear Without Listening,compressive sensing,奈奎斯特采样定理,公式： 频域表示：当时间信号函数f(t)的最高频率分量为fM时,f(t)的值可由一系列采样间隔小于或等于1/(2fM)的采样值来确定,即采样点的重复频率f (2fM)。,一般实际应用中 保证采样频率为 信号最高频率的510倍,占用体积最大已成为通信系统的瓶颈,需要很大的计算量,启发,奈奎斯特采样忠实的反应了原始信号的每一部分细节，但也带来了大量的冗余。 实际生活中大量的信号存在冗余性，虽然数据量很大，但信息量不大。既大部分信号都是“稀疏的”。 我们人类关注的大部分时候是信号中的

2、“奇异值”而不是每一个频率中的细节。,启发,接上一点，人们据此开发了很多压缩算法，如经典的jpeg和MP3，但这些算法都存在某种共性的问题。第一、它是发生在数据已经被完整采集到之后；第二、它本身需要复杂的算法来完成。相较而言，解码过程反而一般来说在计算上比较简单，以音频压缩为例，压制一个 mp3 文件的计算量远大于播放（即解压缩）一个 mp3 文件的计算量。,Traditional way,首先，对原始图像做傅里叶或小波变换 其中只有a1a100000,b1b100000有大于1的值，其余都在系数都在0附近。 其次，用一种压缩算法（如jpeg）压缩原始信号，丢弃掉冗余的信息，压缩时丢失掉90%

3、的原始信息（假设我们的压缩算法非常高效）。,问题,如果你的照相机收集了如此多的数据只是为了随后的删除，那么为什么不一开始就丢弃那90%的数据，直接去除冗余信息不仅可以节省电池电量，还能节省空间。 一个更一般的问题：是否有一种算法，可以实现通过对信号的高度不完备线性测量的高精确的重建。 这就是压缩感知理论。,压缩感知的发现是一次意外，话说一天，当时是加州理工学院教授（现在去了斯坦福）的Emmanuel Cands在研究名叫Shepp-Logan Phantom的图像，这种标准图像常被计算机科学家和工程师测试图像算法。Cands检查的图像质量非常差，充满了噪声，他认为名叫L1-minimizati

4、on的数学算法能去除掉噪声条纹，结果算法真的起作用了，突然就觉得好神奇哦，,“就像给出10位银行卡账号前三位，我能猜出后7为一样，并且，屡试不爽”。 而且在图像变干净的同时，他发现图像的细节出人意料的完美起来。,某一日Candes去幼儿园接孩子，正好遇上了也在接孩子的陶哲轩，两人攀谈的过程中他提到了自己手头的困难，于是陶哲轩也开始想这个问题，它们成为两人合作的压缩感知领域第一篇论文的基础。 陶哲轩：澳籍华人数学家，童年时期即天资过人，目前主要研究调和分析、偏微分方程、组合数学、解析数论和表示论。24岁起，他在加利福尼亚大学洛杉矶分校担任教授。他现在为该校终身数学教授。,照片的压缩感知处理,如果

5、只需要10万个分量就可以重建绝大部分的图像，那何必还要做所有的200万次测量，只做10万次不就够了吗？ 问题是，1.相机预先不知道哪10万个分量系数需要记录。如果“恰好”错过了最重要的10万个，后果不堪设想。2. 采集到了10万个重要的分量系数之后，如何恢复原始信号。,压缩感知的基本过程和问题,问题1如何设计测量矩阵 （尽量伪随机测量） 问题2如何恢复原始信号（ 是不可逆）,测量矩阵,作用：采集信号中关键的分量。 原理：最好的采样的方法是随机（伪）采样。 常见矩阵： a.普适：高斯矩阵，大维随机矩阵，随机游走 b.特殊：针对不同信号，如宽带频谱感知中用差分矩阵。,恢复方法,如何从不完整信号信号

6、中恢复出原始信号？高斯消除法或最小二乘法都可以，但是运算量太大。 匹配追踪：找到一个其标记看上去与收集到的数据相关的小波；在数据中去除这个标记的所有印迹；不断重复直到我们能用小波标记“解释”收集到的所有数据。 就是先找出一个貌似是基的小波，然后去掉该小波在图像中的分量，迭代直到找出所有10w个小波.,基追踪（又名L1模最小化）：在所有与(image)数据匹配的小波组合中，找到一个“最稀疏的”基，也就是其中所有系数的绝对值总和越小越好。（这种最小化的结果趋向于迫使绝大多数系数都消失了。） 又名BP算法,总结,压缩感知技术是一种抽象的数学概念，而不是具体的操作方案。 压缩感知的思想是在采样时完成对信号的压缩。 压缩感知对信号本身有适用条件，要求信号本身是k稀疏的，而奈奎斯特采