压缩感知基本理论

1、压缩感知基本理论压缩感知基本理论一、压缩感知基本理论介绍二、几种重要算法的介绍（一）压缩感知理论的提出（二）压缩感知的基本理论（三）压缩感知的核心问题（四）压缩感知理论的应用一、压缩感知基本理论介绍一、压缩感知基本理论介绍（一）压缩感知理论的提出（一）压缩感知理论的提出信号采样是模拟的物理世界通向数字的信息世界之必备手段。多年来，指导信号采样的理论基础一直是著名的奈奎斯特采样定理，然而这一传统采样定理存在有以下不足：1.采样速率受信号带宽限制；2.传输速度要求太高；3.信号压缩严重浪费存储资源；4.信号处理系统设计要求和成本太高。（一）压缩感知理论的提出（一）压缩感知理论的提出考虑到这些缺点，

2、能否利用其它变换空间来描述信号，建立新的信号描述和处理的理论框架，使得在保证信息不损失的情况下，用远低于传统采样定理要求的速率采样信号，同时又可以完全恢复信号？事实上与信号带宽相比，信号的稀疏性能够直观地而且相对本质地表达信号的信息，因此我们可以利用信号这一特性来重构信号。（一）压缩感知理论的提出（一）压缩感知理论的提出考虑到传统采样定理的不足， 2004年Candes、Tao和Donoho等人基于信号稀疏特性，提出了压缩感知，相关文献于2006年发表 ：Compressed SensingRobust Uncertainty Principles: Exact Signal Re-const

3、ruction from Highly Incomplete Frequency Information（一）压缩感知理论的提出（一）压缩感知理论的提出传统采样定理流程图：压缩感知理论流程图：压缩感知理论为信号采集技术带来了革命性的突破，它采用非自适应线性投影来保持信号的原始结构，以远低于奈奎斯特频率对信号进行采样，通过数值最优化问题准确重构出原始信号。（二）压缩感知的基本理论（二）压缩感知的基本理论设信号为 中的一组列向量，可以用一组正交基 线性组合表示：NxR12,N 1Niiixss 式中， 是对应于正交基的投影系数。如果系数矩阵s中只有KN个非零系数，则称信号x在正交基上的投影系数是K

4、-稀疏的；如果系数矩阵s中非零系数的个数远大于零系数的个数，将系数按照由大到小排序，近似幂级数衰减，则信号x可用少量的大系数近似表示，说明信号x是可压缩的。is假设长度为 N的信号x在正交基上的投影系数是K-稀疏的，利用与正交基不相关的观测矩阵:MN（KMN），得到信号x在上的非自适应性线性映射，有观测集合：yxss 式中 是 的向量， 。最后可用适当的方法，从获取的观测值 中重构出原始信号 。可见压缩感知理论可以大大降低采样速率和传输成本，节约在传统采样方法前期所需的系统资源和存储空间，实现对信号的采样和压缩编码过程。y1M yx（二）压缩感知的基本理论（二）压缩感知的基本理论（二）压缩感知

5、的基本理论（二）压缩感知的基本理论由于信号的观测值y的维数M远小于信号x的维数N，上式是欠定性问题，不能直接求解。由于式中系数s是K-稀疏的，仅有K个非零系数，且KMN ，可通过上式的逆得到稀疏系数 ，得到原始信号x的近似解。稀疏信号的压缩采样过程可形象的用下图表示：（二）压缩感知的基本理论（二）压缩感知的基本理论重构信号的过程，就是求解公式：yxss 最初是利用0-范数最优化来求解：0min . . lssst ys 但是利用0-范数来求解是一个NP难题，研究者指出当s满足一定条件时可以用p（0p2）范数最优化来求解，将非凸化问题转化成凸化问题来求最优化求解：min . . plsss ty

6、s （三）压缩感知的核心问题（三）压缩感知的核心问题核心问题之一：信号的稀疏表示核心问题之一：信号的稀疏表示信号的稀疏性是压缩感知的重要前提和理论基础。设 ， 时，若投影投影系数 满足：02p0R Tsx1/(| )ppipisR则说明系数s是稀疏的，从而信号x是K-稀疏的；也存在另外一种表示方式，如果信号x的变换系数 的支撑域 的数目小于或等于K，则说明信号x是K-稀疏的。可见只有找到合适的基，才能保证信号变换到稀疏域上。,iisx :0ii（三）压缩感知的核心问题（三）压缩感知的核心问题压缩感知的另一个重要前提是正交基与测量矩阵不相关。信号x在某个变换域的投影系数向量s是K-稀疏的，不是直

7、接对这 个系数直接采取编码的，而是将该系数向量投影到另一个与变换基不相关的测量矩阵的 个行向量上，得到观测值： 。核心问题之二：测量矩阵的设计核心问题之二：测量矩阵的设计,(1, 2 , .)jjysjM对任意K稀疏信号x和常数 ，若测量矩阵满足约束等距性质： 。(0,1)k222222(1) |(1) |kkxxx才保证用于稀疏表示x的稀疏基与测量矩阵不相关。（三）压缩感知的核心问题（三）压缩感知的核心问题核心问题之三：重构算法的构造核心问题之三：重构算法的构造当信号x能够稀疏表示出来和稀疏基与测量矩阵不相关时，这时就要构造算法来求解测量过程的逆问题 来求解出投影系数，从M个观测值y中重构出

8、稀疏度为K的原信号x，其过程可以表示为：Tsx （四）压缩感知理论的应用（四）压缩感知理论的应用运用压缩感知理论，莱斯大学一种单像素的相机，实现用单像素来完成高分辨率的成像，耶鲁大学研制的超谱成像仪，麻省理工学院研制的MRI RF脉冲设备，伊利诺伊州立大学研制的DNA微阵列传感器等等。（四）压缩感知理论的应用（四）压缩感知理论的应用压缩感知的提出给信号采样方法带来了一次新革命，研究者已将这一理论引入到模拟-信息采样、合成孔径雷达成像、遥感成像、核磁共振成像、深空探测成像、无线传感器网络、信源编码、人脸识别、语音识别、探地雷达成像等诸多领域。二、几种重要算法的介绍二、几种重要算法的介绍贪婪追踪算

9、法贪婪追踪算法贪婪追踪算法的基本思想就是通过迭代的方法依次找出待重建信号的支撑，来求解最小0范数，基于某种贪婪准则一次求出一个或者是多个待估信号的构成元素，从而在迭代时选择一个局部最优解来逐步逼近原始信号。主要算法包含有匹配追踪（MP）算法、正交匹配追踪（OMP）算法、分段正交匹配追踪（StOMP）算法、正则化正交匹配追踪（ROMP）算法、压缩采样匹配追踪（CoSaMP）算法、子空间追踪（SP）算法等等。这些算法结构实现简单，运算量小，计算速度很快，常用于重构维数较低的小尺度信号。匹配追踪算法流程二、几种重要算法的介绍二、几种重要算法的介绍这一种算法收敛速度很慢，基于改进些算法，提出了正交匹配

10、追踪算法、分段正交匹配追踪算法、正则化正交匹配追踪算法、压缩采样匹配追踪算法等等。凸优化算法凸优化算法这类算法本质思想是通过将非凸化问题转化成凸化问题来求最优化求解，即将求0范数的NP难题转变为求1范数的线性问题来找到信号的逼近，针对最小化1范数模型来提出线性规划方法。主要算法包括有：基追踪（BP）算法、梯度投影稀疏重构（GPSR）算法、凸集交替投影（POCS）算法、内点迭代算法、迭代阀值算法以及同伦算法等。这些算法具有最强的稀疏恢复保证，在测量矩阵满足一定条件下能精确重构所有稀疏信号，而且所需的测量次数也非常少，抑制噪声干扰能力强，也常用于小尺度信号。二、几种重要算法的介绍二、几种重要算法的介绍二、几种重要算法的介绍二、几种重要算法的介绍迭代阀值算法流程组合算法组合算法组合算法的基本思想是针对信号进行高度的结构化采样，由群测试来获得快速信号支撑，要求信号的采样支持通过分组测试来重建。主要算法包括有：傅立叶采样算法、链式追踪（CP）算法、 HHS追踪算法等。统计优化算法统计优