大学科研成果论文 (15)

论文题目: 压缩感知理论及其应用前景

学 院： 计算机与信息学院 专业年级： 电子信息工程2010级 学 号： 姓 名： 指导教师、职称：

2012年 11 月15日

I

压缩感知理论及其应用前景

摘 要：信号采样是联系模拟信源和数字信息的桥梁．人们对信息的巨量需求造成了信号采样、传输和存储的巨大压力。多年来，指导信号采样的理论基础一直是著名的Nyquist采样定理，但其产生的大量数据造成了存储空间的浪费。压缩感知（Compressed Sensing）理论是近年来提出的一种基于信号稀疏性的新兴采样理论。与通常的数据采样定理不同，该理论提出可以用远远少于传统采样定理所需的采样点数或观测点数恢复出原信号或图像本文详述了压缩感知的基本理论。本文主要阐述了压缩感知中信号的稀疏表示、测量矩阵的设计及信号的重构算法等基本理论，并述了该理论的广阔应用。

关键词：压缩感知；稀疏表示；观测矩阵；重构算法

一、 引言

在过去的半个世纪里，奈奎斯特采样定理几乎支配着所有的信号或图像等的获取、处理、存储以及传输。它要求采样频率必须大于或等于信号带宽的两倍，才能不失真的重构原始信号。在许多实际应用中，例如高分辨率的数码装置及超带宽信号处理，高速采样产生了庞大的数据，为了降低存储，处理或传输成本，只保留其中少量的重要数据。由于采样后得到的大部分数据都被丢弃了，所以这种方式造成了采样资源的严重浪费。设想如果在采样的同时直接提取信号的少量重要信息，就可以大大降低采样频率，节约资源，提高效率而且仍能够精确重构原始信号或图像。这就是Donoho、Candes以及Tao等人提出压缩感知（Compressed Sensing、Compressive Sampling或Compressive Sensing，压缩感知）[1~4]理论的主要思想。压缩感知理论指出：只要信号是可压缩的或在某个变换域是稀疏的，那么就可以用一个与变换基不相关的观测矩阵将变换所得高维信号投影到一个低维空间上，然后通过求解一个优化问题就可以从这些少量的投影中以高概率重构出原信号，可以证明这样的投影包含了重构信号的足够信息。在该理论框架下，采样速率不再取决于信号的带宽，而在很大程度上取决于两个基本准则：稀疏性和非相干性，或者稀疏性和等距约束性。Nyquist采样定理指出，采样速率达到信号带宽的两倍以上时，才能由采样信号精确重建原始信号。可见，带宽是Nyquist采样定理对采样的本质要求。然而随着人们对信息需求量的增加，携带信息的信号带宽越来越宽，以此为基础的信号处理框架要求的采样速率和处理速度也越来越高。解决这些压力常见的方案是信号压缩。但是，信号压缩实际上是一种资源浪费，因为大量的不重要的或者只是冗余信息在压缩过程中被丢弃。从这个意义而言，我们得到以下结论：带宽不能本质地表达信号的信息，基于信号带宽的Nyquist采样机制是冗余的或者说是非信息的。

二、 压缩感知理论框架[6]

传统的信号采集、编解码过程如图l所示：编码端先对信号进行采样，再对所有采样值进行变换，并将其中重要系数的幅度和位置进行编码，最后将编码值进行存储或传输：信号的解码过程仅仅是编码的逆过程，接收的信号经解压缩、反变换后得到恢复信号。采用这种传统的编解码方法，由于信号的采样速率不得低于信号带宽的2倍，使得硬件系统面临着很大的采样速率的压力。此外在压缩编码过程中，大量变换计算得到的小系数被丢弃，造成了数据计算和内存资源的浪费。

1

图1 传统编解码理论的框图

压缩感知理论对信号的采样、压缩编码发生在同一个步骤，利用信号的稀疏性，以远低于Nyquist采样率的速率对信号进行非自适应的测量编码。测量值并非信号本身，而是从高维到低维的投影值，从数学角度看，每个测量值是传统理论下的每个样本信号的组合函数，即一个测量值已经包含了所有样本信号的少量信息。解码过程不是编码的简单逆过程，而是在盲源分离中的求逆思想下。利用信号稀疏分解中已有的重构方法在概率意义上实现信号的精确重构或者一定误差下的近似重构[10]。解码所需测量值的数目远小于传统理论下的样本数。

图2 压缩感知理论的编解码框图

faii或fN(i1,2,...,N)f(fR)i1假设信号，长度为N，基向量为i，对信号进行变换：

显然f是信号在时域的表示，是信号在域的表示。信号是否具有稀疏性或者近似稀疏性是运用压缩感知理论的关键问题，若式中的只有K个是非零值(NK)者仅经排序后按指数级衰减并趋近于零，可认为信号是稀疏的。

信号的可稀疏表示是压缩感知的先验条件。当前，压缩感知理论主要涉及三个核心问题： (1) 具有稀疏表示能力的过完备字典设计；

(2) 满足非相干性或等距约束性准则的测量矩阵设计； (3) 快速鲁棒的信号重建算法设计。

N1.信号的稀疏表示

信号的稀疏性是压缩感知的重要前提和理论基础。因此, 对信号稀疏表示的研究是压缩感知理论的首要任务。稀疏表示对于压缩感知的基础性作用主要体现在: 只有选择合适的稀疏矩阵, 才能保证表示系数具

有足够的稀疏性或衰减性, 才能在减少压缩测量的同时保证压缩感知的重建精度。( 1) 根据压缩感知理论, 高概率重构稀疏信号的充分条件是感知矩阵( ( ( ∈RM×N ) 必须满足约束等距性RIP( Rest ricted Isomet ry Property ) 条件, 即对于任意K 稀疏信号x( x∈RN ) 和常数Dk ∈( 0, 1) , ( 1 - Dk) ‖x‖22 ≤ ‖ ( Tx‖22 ≤ ( 1 + Dk) ‖x‖22 ( 2)

成立, 其中T< { 1, ⋯, N } , 且ûT û ≤ K , ( T 为( 中由索引T 所指示的相关列构成的大小为K ×ûT û的子矩阵。从上式可以看出, 信号的稀疏度K 越小, 即信号越稀疏, 约束等距性条件越容易满足。 ( 2) Candes 等进一步指出, 在感知矩阵( 满足约束等距性条件的前提下, 如果要精确重构K 稀疏信号x, 测量次数M 必须满足M ≥ O( K log ( N ) ) 。因此, 信号的稀疏度K 越小, 稀疏性越强, 保证信号重构所需的测量次数越少。在研究信号的稀疏表示时, 可以通过变换系数衰减速度来衡量变换基的稀疏表示能力。Candes 和T ao研究表明, 满足具有幂次衰减速度的信号, 可利用压缩感知理论得到恢复。

目前对于压缩感知中稀疏矩阵的研究大多仍集中在固定的正交基矩阵。而对于具有复杂特征的信号如自然图像、声音信号来说, 固定的正交基不足以捕获信号的多种特征, 使图像在变换域足够稀疏。例如, 正交小波变换由于缺乏平移旋转不变性而不能有效压缩几何图像。大量的研究表明过完备冗余字典下的信号稀疏表示更加有效, 而这方面的研究

2

也有了一定的进展。因此, 能否将压缩感知理论中的稀疏表示从固定的正交基扩展到冗余字典, 引起了人们巨大的研究兴趣[ 7/8] 。

2. 观测矩阵

感知理论中，通过变换得到信号的稀疏系数向量D = 后，需要设计压缩采样系统的观测部分，它围绕观测矩阵 展开．观测器的设计目的是如何采样得到 个观测值，并保证从中能重构出长度为Ⅳ的信号 或者基 下等价的稀疏系数向量D．显然，如果观测过程破坏了 中的信息，重构是不可能的_1 ．观测过程实际就是利用M ×N观测矩阵 的 个行向量{ } 对稀疏系数向量进行投影，即计算@和各个观测向量{之间的内积，得到 个观测值Yj=(J=1，2⋯ ． )，记观测向量Y=(Y1，Y2，⋯，)，即Y= D= =A (5)。

非零项的具体值。用一个与变换矩阵不相关的MN(MN)测量矩阵对信号进行线性投影，得到线性测量值

由于观测向量y是这些非零系数0 对应的列向量的线性组合，从而可以形成一个M ×K的线性方程组来求解这些

y：

yf

择不依赖于信号f。测量矩阵的设计要求信号从f转换为y的过程中，所测量到的K个测量值不会破坏原始信号的信息，保证信号的精确重构。

由于信号f是是可稀疏表示的，上式可以表示为下式：

测量值y是一个M维向量，这样使测量对象从N维降为M维。观测过程是非自适应的即测量矩阵少的选

yf

f2由于信号是K稀疏，若上式中的满足有限等距性质(Restricted Isometry Property，简称RIP)，即对于任意K稀疏信号1k1k2和常数

其中是一个MN矩阵。上式中，方程的个数远小于未知数的个数，方程无确定解，无法重构信号。但是，2则K个系数能够从M个测量值准确重构。RIP性质的等价条件是测量矩阵和稀疏基不相关。目前，用于压缩

k(0,1)，矩阵满足：

||f||||f||2

感知的测量矩阵主要有以下几种：高斯随机矩阵，二值随机矩阵(伯努力矩阵)，傅立叶随机矩阵，哈达玛矩阵，一致球矩阵等。

3.重构算法

在压缩感知理论中，由于观测数量 远小于信号长度Ⅳ，因此不得不面对求解欠定方程组y=A 的问题。观测矩阵具有RIP性质也为从M个观测值中精确恢复信号提供了理论保证。为更清晰地描述压缩感知理论的信号重构问题，首先定义向量X={ ， 2，⋯ ，％}的 范数为l X 1 =(Σ I P) -(6)，当P=0时得到0一范数，它实际上表示 中非零项的个数．于是，在信号 稀疏或可压缩的前提下，求解欠定方程组y=A 的问题转化为最小0 范数问题：n ll l』n s．t． A ： =Y -(7)。但是，它需要列出 中所有非零项位置的c备种可能的线性组合，才能得到最优解．因此，求解式(7)的数值计算极不稳定而且是NP难问题[加]．注意，这和稀疏分解问题从数学意义上讲是同样的问题．于是稀疏分解的已有算法可以应用到压缩感知重构中。

目前为止出现的重构算法都可归人以下三大类[9]：(1)贪婪追踪算法：这类方法是通过每次迭代时选择一个局部最优解来逐步逼近原始信号．这些算法包括MP算法，OMP算法，分段OMP算法 [10]．(2)凸松弛法：这类方法通过将非凸问题转化为凸问题求解找到信号的逼近，如BP算法，内点法，梯度投影方和迭代阈值法 J．3)组合算法：这类方法要求信号的采样支持通过分组测试快速重建，如傅立叶采样，链式追踪 J和HHS(Heavg Hitters on Steroids)追踪 等．可以看出，每种算法都有其固有的缺点．凸松弛法重构信号所需的观测次数最少，但往往计算负担很重．贪婪追踪算法在运行时间和采样效率上都位于另两类算法之间．

由上面的分析可知，重构算法和所需的观测次数密切相关．当前，压缩感知理论的信号重构问题的研究主要集中在如何构造稳定的、计算复杂度较低的、对观测数量要求较少的重构算法来精确地恢复原信号．

三、压缩感知的应用及前景

压缩感知理论利用了信号的稀疏特性，将原来基于奈奎斯特采样定理的信号采样过程转化为基于优化计算恢复信号的观测过程．也就是利用长时间积分换取采样频率的降低，省去了高速采样过程中获得大批冗余数据然后再舍去大

3

部分无用数据的中间过程，从而有效缓解了高速采样实现的压力，减少了处理、存储和传输的成本，使得用低成本的传感器将模拟信息转化为数字信息成为可能．这种新的采样理论将可能成为将采样和压缩过程合二为一的方法的理论基础．

压缩感知能从少量的非相关观测值中高效获取可压缩信号的信息，压缩感知 的这一特点决定了其应用的广泛性。压缩感知 的应用领域涉及数据压缩、模拟/ 信息的转换、压缩成像、信道编码、信道估计、生物传感、语音识别、雷达成像、雷达遥感、学习理论及模式识别等诸多领域。在压缩成像方面，RICE 大学已成功研制了“单像素”压缩数码照相机，该相机不像传统相机那样获取原始信号的N 个像素值，而是直接获取M个随机线性观测值，在实践中为取代传统相机迈出了实质性的一步。在通信领域，压缩感知也有着强大的生力，由于无线多径信道一般情况下是稀疏的，即使在时延扩展很大时，大幅度的径的个数也很少，因此利用少量的导频就能获取未知信道的频域响应估计。此外压缩感知理论还可用于通信信道的错误检测[11]感知理论的诞生在学术界引起了极大的反响，已经对理论数学、计算数学、计算科学、概率论、信息论、信号处理、电子工程、光学工程等诸多领域产生了重要影响。

虽然压缩感知理论具有广阔的应用前景，但其理论研究还不完善，相应的应用研究还处于起步阶段，仍有许多问题有待解决。主要有以下几个方面：（1）快速有效的稀疏分解算法的研究；（2）便于硬件实现和优化算法实现的测量矩阵的设计；（3）非l1范数驱动的可压缩信号的重建理论；（4）含有噪声时信号的快速顽健的重构算法设计；（5）针对实际问题，基于CS理论的软硬件设计；此外CS 与其他领域的融合还远远不够，有待进一步的探讨研究。

尽管压缩感知 体系还不完善，但它的出现已在信号处理及其他领域掀起了一股浪潮，它为目前许多尚未解决的难题提供了新思路和新方法。作为国外刚出现的新理论，压缩感知理论的研究方兴未艾。压缩感知 理论有着强大的生命力，将会开创更加广阔的应用前景。

参考文献

[1] Donoho D. Compressed sensing. IEEE Trans Information Theory，2006，52（4）：12~1306

[2] Candes E. Compressive sampling. Proceedings of the International Congress of Mathematicians.Madrid，Spain，2006，3：1433~1452

[3] Baraniuk R. A lecture on compressive sensing. IEEE Signal Processing Magazine，2007，24（4）：118~121

[4] Candes E J，Wakin MB. An introduction to compressive sapmpling. IEEE Signal Processing Magazine，2008，25（2）：21~30 [5]石光明.刘丹华.高大化.刘哲.林杰.王良君 压缩感知理论及其研究进展-ACTA Electronica Sinica 2009，37(5) [6]喻玲娟.谢晓春 压缩感知理论简介-Video Engineering 2008，32(12)

[ 7] 郭海燕, 杨 震. 基于近似KLT 域的语音信号压缩感知[ J] . 电子与信息学报, 2009, 31( 12) : 2948-2952.

[ 8] Rauhut H, Schass K, Vander gheynst P. Compr essed sensing and r edundant dictionaries[ J] . IEEE Tr ansactions on InformationTheo ry , 2008, 54( 5) : 2210-2219.

[9]D NeedeU，J A Tropp．CoSaMP：Iterative signal recovery fromincomplete and inaccurate sampleslJJ．Appl Comp HamaonicAnal，2009，26(3)：301—321．

[10]DLDonoho，YTsaig，IDrori etc．Sparse solution ofunderde—termined linear equations by stagewise orthogonal ma tchingpursuitlR J．Technical Report2006．

[11] Candes E J，Rudelson M，Tao T，Vershynin R. Error correction via linear programming. Proc IEEE Symposium on Foundations ofComputer Science（FOCS），2005. 668~681

4