压缩感知_研究现状概述.pptx

压缩感知概述 2017-11-23 数学工具 概念及背景 compressive sensing（CS） 又称 compressived sensing ，compressived sample，大意是在采集信号的时候（模拟到数字），同时完成对信号压缩之意。中文的翻译成“压缩感知”。 CS大约是2000年左右的一篇博士论文中，已经出现了雏形。后来被陶哲轩，C牛（Emmanuel Candes）和D（Donoho）牛，完善理论。这几位顶尖高手联手挖出了信号处理领域、机器学习领域，近10年最大的学术大坑。 概念及背景 对核磁共振的图像，来看一下这些系数， 6000 个不连续性系数，我说我们只要看 1800 不连续的测量，让我们看有什么变化，让我们看看重建后的图片，这些图片是非常接近真实图像的， 我们可以用少于三倍或甚至四倍的测量次数而得到一个非常接近的结果。 概念及背景 稀疏性的概念 为方便介绍压缩感知理论, 我们将信号的稀疏性简单理解为信号中非0元素数目较少. 我们所指的信号即为一向量x ∈. 我们用Σs 表示s-稀疏向量集合, 即 这里||x|表示x 中非0元素的数目. 所谓对信号x0 ∈ 编码, 即指用一n×N 的矩阵Φ与x0 ∈ 进行乘积, 那么我们得到 此处, y ∈ 即为我们所观测到的关于x0 的信息. 概念及背景 其中y是n维向量，x是N维向量， Φ是n×N维矩阵。 概念及背景 感知压缩难点在于，压缩后的数据并不是压缩前的数据的一个子集，并不是说，本来有照相机的感光器上有一千万个像素，扔掉其中八百万个，剩下的两百万个采集到的就是压缩后的图像，──这样只能采集到不完整的一小块图像，有些信息被永远的丢失了而且不可能被恢复。 如果要想采集很少一部分数据并且指望从这些少量数据中“解压缩”出大量信息，就需要保证： 第一：这些少量的采集到的数据包含了原信号的全局信息，第二：存在一种算法能够从这些少量的数据中还原出原先的信息来。 概念及背景 概念及背景 compressive sensing实际上是对信号采集的颠覆性的理论，打破了乃奎斯特采样(也称香农采样)。实际上，大部分信号是稀疏的，没有必要用乃奎斯特采样进行时间离散化。注意两点： （1）乃奎斯特采样对信号没有稀疏性的假设；（2）CS对信号有稀疏性假设，既s-稀疏；  压缩感知适合解决什么问题？ （1）信号是稀疏的 （2） sensor方计算代价较大，receiver方计算代价较小（即不适合将信息全部存储下来，而适合取少量信息，之后恢复） 算法框架及具体内容 对于之前介绍过的编码表达式 其中， ， ，Φ是n×N 的矩阵。 我们先将解码，就是试图通过y 反求x0, 记为Δ。我们用Δ(y) 表示反求结果. 一般而言, 若n N, 则有无数个x ∈ 满足y = Φx. 因而, 只有借助信号稀疏性的特征, 我们才有可能反求原始的信号x0. 那么, 给定一编码、解码对(Φ, Δ), 我们关心其性能, 即 此处X 为一给定范数. 算法框架及具体内容 考虑 的解码问题 情况一：当x0的s个非零元素位置已知，我们只要Φ的对应s列线性无关，必有唯一解； 情况二：当x0的s个非零元素位置未知，此时我们有定理： 此时，我们需要求如下规划问题的解: 算法框架及具体内容 上述规划问题是NP—hard问题，所以我们想能不能换个什么方法来恢复信号，自然而然的，我们想到了最小平方法。即最优化问题： 2 如右图，我们可以发现效果 不是很理想。 算法框架及具体内容 但是，如果我们采用L1范数来近似 即： 如右图，我们可以发现效果 非常好。 算法框架及具体内容 Q：对什么样观测矩阵Φ, P1 解与P0 解总一致? 充要条件： 说明：s-阶零空间性质 算法框架及具体内容 虽然可以用零空间性质给出P1 的解与P0 的解一致的充要条件. 但是, 零空间性质并不容易操作,无论在理论还是计算方面. 也就是说, 给一个矩阵Φ, 难以从理论上证明其是否满足零空间性质, 也不容易在计算机上快速验证. 因而, 人们考虑了另外一种刻画方式, 即是所谓的矩阵RIP(Restricted Isometry Property) 性质. RIP 性质的定义: 算法框架及具体内容 下面定理给出了解码Δ1 能够精确恢复s-稀疏信号的一个充分条件. 此定理的证明Candes已经给出，将RIP 常数定为 s 阶RIP 条件 2s 阶RIP 条件 算法框架及具体内容 事实上, 当0 p 1, |· |p 为一拟范数. 相比于Δ1 解码, Δp 解码所需观测次数较少, 但解码复杂度