压缩感知综述

1、压缩感知综述汪琪中科院光电研究院2011年10月20日 压缩感知理论简介 压缩感知数学模型 压缩感知关键要素 压缩感知应用前景 压缩感知仿真实例压缩感知综述压缩感知综述压缩感知理论简介压缩感知理论简介 压缩感知(压缩传感，Compressive Sensing, Compressed sensing)理论是近年来信号处理领域诞生的一种新的信号处理理论，由D. Donoho(美国科学院院士)、E. Candes(Ridgelet, Curvelet创始人)及华裔科学家T. Tao(2006年菲尔兹奖获得者)等人提出，自诞生之日起便极大地吸引了相关研究人员的关注。网站http:/dsp.rice.

2、edu/cs上可以获取大量相关的论文。 压缩感知理论在信号获取的同时，就对数据进行适当地压缩，而传统的信号获取和处理过程主要包括采样、压缩、传输和解压缩四个部分，其采样过程必须遵循奈奎斯特采样定率，这种方式采样数据量大，先采样后压缩，浪费了大量的传感元、时间和存储空间，相较之下，压缩传感理论针对可稀疏表示的信号，能够将数据采集和数据压缩合二为一，这使其在信号处理领域有着突出的优点和广阔的应用前景。压缩感知理论简介压缩感知理论简介传统的信息获取与处理流程压缩感知理论框架 压缩感知的核心思想是压缩和采样合并进行，并且测量值远小于传统采样方法的数据量，突破了香农采样定理的瓶颈，使高分辨率的信号采集成

3、为可能。 压缩感知理论简介压缩感知理论简介 压缩感知理论主要包括信号的稀疏表示、随机测量和重构算法等三个方面。稀疏表示是应用压缩感知的先验条件，随机测量是压缩感知的关键过程，重构算法是获取最终结果的必要手段。压缩感知信号稀疏性非相关测量非线性优化传统方式信号带宽Nyquist采样规则Fourier变换压缩感知数学模型压缩感知数学模型 设x为长度N的一维信号，稀疏度为k（即含有k个非零值），A为MN的二维矩阵（MN），y=x为长度M的一维测量值。压缩感知问题就是已知测量值y和测量矩阵的基础上，求解欠定方程组y=x得到原信号x。 需要求解如下最优化问题： 这个过程称之为重构，其中的0范数指的就是0

4、元素的个数。 Candes等指出，要精确重构k稀疏信号x，测量次数M（即y的维数）必须满足y=O(k logN) ，并且矩阵必须满足约束等距性条件(Restricted Isometry Principle)。 然而最小0范数是一个NP问题，通常需要对该问题加以转换，如将0范数转化为1范数问题。 0argminxx. stxy 压缩感知数学模型压缩感知数学模型 一般的自然信号x本身并不是稀疏的，需要在某种稀疏基上进行稀疏表示，x=s，为稀疏基矩阵，s为的稀疏系数。 压缩感知方程为y=x=s=s。 将原来的测量矩阵变换为=（称之为传感矩阵），解出s的逼近值 ，则原信号 。 sxs 压缩感知关键要

5、素压缩感知关键要素 压缩感知关键要素包括稀疏表示、测量矩阵和重构算法。 信号在某种表示方式下的稀疏性，是压缩感知应用的理论基础，经典的稀疏化的方法有离散余弦变换（DCT）、傅里叶变换（FFT）、离散小波变换（DWT）等。 最近几年，对稀疏表示研究的另一个热点是信号在冗余字典下的稀疏分解。 这是一种全新的信号表示理论：用超完备的冗余函数库取代基函数，称之为冗余字典，字典中的元素被称为原子。目前信号在冗余字典下的稀疏表示的研究集中在两个方面：一是如何构造一个适合某一类信号的冗余字典，二是如何设计快速有效的稀疏分解算法。目前常用的稀疏分解算法大致可分为匹配追踪（Matching Pursuit）和基

6、追踪（Basis Pursuit）两大类。压缩感知关键要素压缩感知关键要素 压缩感知理论中，通过变换得到信号的稀疏系数后压缩感知理论中，通过变换得到信号的稀疏系数后, ,需要设计压缩需要设计压缩采样系统的观测部分，它围绕观测矩阵采样系统的观测部分，它围绕观测矩阵展开。观测器的设计目的是展开。观测器的设计目的是如何采样得到如何采样得到M M个观测值，并保证从中能重构出长度为个观测值，并保证从中能重构出长度为N N的信号的信号x x或者稀或者稀疏基疏基下等价的稀疏系数向量。下等价的稀疏系数向量。 CandeS和Tao等证明:独立同分布的高斯随机测量矩阵可以成为普适的压缩感知测量矩阵。2007年Ca

7、ndes等研究者建立了著名的约束等距性（RIP）理论，即要想使信号完全重构，必须保证观测矩阵不会把两个不同的 K项稀疏信号映射到同一个采样集合中，这就要求从观测矩阵中抽取的每M个列向量构成的矩阵是非奇异的。 Donoho给出压缩感知概念的同时定性和定量的给出测量矩阵要满足三个特征：由测量矩阵的列向量组成的子矩阵的最小奇异值必须大于一定的常数；测量矩阵的列向量体现某种类似噪声的独立随机性；满足稀疏度的解是满足1范数最小的向量。压缩感知关键要素压缩感知关键要素 目前常用的测量矩阵包括： 1）随机高斯矩阵。矩阵每个元素独立地服从均值为0，方差为 的高斯分布。 2）随机贝努利矩阵。矩阵的每个元素独立地

8、服从对称的贝努利分布，等概率为 或- 。 3）部分正交矩阵。先生成NN的正交矩阵U（如傅里叶矩阵），然后在矩阵U中随机地选取M行向量，对MN矩阵的列向量进行单位化得到测量矩阵。 4）部分哈达玛矩阵。生成大小为NN的哈达玛矩阵，然后在生成矩阵中随机地选取M行向量，构成一个MN的矩阵。 5）托普利兹和循环矩阵。首先生成一个向量u，由向量u生成相应的轮换矩阵或托普利兹矩阵U，然后在矩阵U中随机地选取其中的M行而构造的矩阵。 6）稀疏随机矩阵。首先生成一个零元素的矩阵，在矩阵的每一个列向量中，随机地选取d个位置，然后在所选取的位置的值赋为1。1/M1/M1/M压缩感知关键要素压缩感知关键要素压缩感知的

9、重构算法主要分为两大类，一是贪婪算法，它是通过压缩感知的重构算法主要分为两大类，一是贪婪算法，它是通过选择合适的原子并经过一系列的逐步递增的方法实现信号矢量的逼近，选择合适的原子并经过一系列的逐步递增的方法实现信号矢量的逼近，此类算法主要包括匹配跟踪算法、正交匹配追踪算法、补空间匹配追此类算法主要包括匹配跟踪算法、正交匹配追踪算法、补空间匹配追踪算法等。二是凸优化算法，它是把踪算法等。二是凸优化算法，它是把0 0范数放宽到范数放宽到1 1范数通过线性规划范数通过线性规划求解的，此类算法主要包括梯度投影法、基追踪法、最小角度回归法求解的，此类算法主要包括梯度投影法、基追踪法、最小角度回归法等。凸

10、优化算法算法比贪婪算法所求的解更加精确，但是需要更高的等。凸优化算法算法比贪婪算法所求的解更加精确，但是需要更高的计算复杂度。计算复杂度。 此外，迭代阈值法也得到了广泛的应用，此类算法也较易实现，此外，迭代阈值法也得到了广泛的应用，此类算法也较易实现，计算量适中，在贪婪算法和凸优化算法中都有应用。但是，迭代阈值计算量适中，在贪婪算法和凸优化算法中都有应用。但是，迭代阈值法对于迭代初值和阈值的选取均较敏感，且不能保证求出的解是稀疏法对于迭代初值和阈值的选取均较敏感，且不能保证求出的解是稀疏的。的。 就目前主流的两种重建算法而言，基于1范数最小的重建算法计算量巨大，对于大规模信号无法应用；贪婪算法

11、虽然重建速度快，但是在信号重建质量上还有待提高。压缩感知应用前景压缩感知应用前景 压缩感知理论带来了信号采样理论的变革，具有广阔的应用前景，包括压缩成像、模拟信息转换、生物传感等。 压缩感知应用于光学成像的首个实际系统是Rice大学的“单像素相机” 入射光线经过第一个透镜之后进入成像系统，照射在放置于像平面的数字微镜设备(DMD)阵列上。DMD 阵列由数百万个尺寸为m量级的微小反射镜组成，每个反射镜的角度可独立控制。DMD 阵列的反射光线经过第二个透镜，其中仅一个方向的光线进入单像素光子探测器。压缩感知应用前景压缩感知应用前景国防科技大学从压缩感知的角度对热光源关联成像进行了研究。 随机热光源

12、辐射的光束通过分束器分为完全相同的两束，一束称为检测随机热光源辐射的光束通过分束器分为完全相同的两束，一束称为检测光束，使其照射被成像物体，利用光学器件将透射的光束会聚为一点，并由光束，使其照射被成像物体，利用光学器件将透射的光束会聚为一点，并由“单像素单像素”光电检测器记录该点光强；另一束为参考光束，由光电检测器记录该点光强；另一束为参考光束，由 CCD CCD 阵列直阵列直接记录光强。通过计算单像素点与接记录光强。通过计算单像素点与 CCD CCD 阵列光强之间的互相关，可得到物阵列光强之间的互相关，可得到物体的像。体的像。 压缩感知应用前景压缩感知应用前景 Duke大学的DISP小组开发

13、了一种新的多光谱成像器：Coded Aperture Snapshot Spectral Imager (CASSI)。 多谱图像具有二维的空间分辨和一维的光谱分辨率，可形成一个三维的多谱图像具有二维的空间分辨和一维的光谱分辨率，可形成一个三维的数据体。数据体。CASSI CASSI 利用编码孔径和色散介质调制场景的光场，一个探测器获利用编码孔径和色散介质调制场景的光场，一个探测器获取三维数据体的二维、多路投影。因此，取三维数据体的二维、多路投影。因此，CASSI CASSI 不直接测量三维数据体的不直接测量三维数据体的“体素体素”，而是通过少量的编码测量（即压缩采样）和稀疏重构算法估计，而是通过少量的编码测量（即压缩采样）和稀疏重构算法估计数据体。数据体。压缩感知仿真实例压缩感知仿真实例 对256256大小的8bit灰度lena图像进行仿真计算，由于数据量过大，将图像分为1616大