压缩感知毕业论文

压缩感知毕业论文

目录

第1章绪论 (1)

1.1 研究背景和意义 (1)

1.2 CS理论框架 (2)

1.3 本文框架结构 (4)

第2章国内外研究现状 (6)

2.1 从稀疏重构到压缩感知 (6)

2.2 稀疏重构算法和重构条件研究 (7)

2.3 压缩感知在光学成像中的应用 (9)

第3章压缩感知（CS）基本理论 (12)

3.1 压缩感知背景 (12)

3.2 压缩感知理论 (13)

3.2.1压缩感知的前提条件—稀疏性和不相干性 (13)

3.2.2 三个关键技术 (17)

3.2.3信号的稀疏表示 (17)

3.2.4 观测矩阵设计 (19)

3.2.5 稀疏信号的重构 (21)

3.2.6 重构算法 (22)

3.3压缩感知理论应用概述 (24)

3.3.1压缩成像 (24)

3.3.2 模拟信息转换 (25)

3.3.3 生物传感 (25)

3.4 本章小结 (25)

第4章压缩感知实现及结果分析 (26)

4.1图像压缩基本理论 (26)

4.1.1传统图像压缩重构方法 (26)

4.1.2 图像压缩重构质量的评价 (27)

4.2 压缩感知理论算法对一维信号的实现 (29)

4.2.1 正交匹配追踪算法（OMP） (29)

4.2.2 算法的实现及结果分析 (31)

4.3 压缩感知理论算法对二维图像重构的实现 (34)

4.3.1 基于小波变换的分块压缩感知理论 (34)

4.3.2 实现步骤 (35)

4.3.3 重构结果及分析 (38)

4.4 本章小结 (43)

第5章总结与展望 (44)

5.1 总结 (44)

5.2 展望 (44)

参考文献 (46)

致谢 (47)

附录 (49)

第1章绪论

信号采样是联系模拟信源和数字信息的桥梁。随着信息技术日新月异的进步，人们对信息的巨量需求造成了信号采样、传输和存储的巨大压力。如何缓解这种压力又能有效提取承载在信号中的有用信息是信号与信息处理中急需解决的问题之一。近几年来，在信号处理领域出现的压缩感知理论（CS）打破了传统采样过程中信号采样速率必须达到信号带宽两倍以上才能精确重构原始信号的奈奎斯特采样定理，使得信息存储、处理和传输的成本大大降低。

1.1 研究背景和意义

信息技术的飞速发展使得人们对信息的需求量剧增。现实世界的模拟化和信号处理工具的数字化决定了信号采样是从模拟信源获取数字信息的必经之路。奈奎斯特采样定理则是指导如何采样的重要理论基础。它指出，采样速率必须达到信号带宽的两倍以上才能精确重构信号。然而随着人们对信息需求量的增加，携带信息的信号带宽越来越宽，以此为基础的信号处理框架要求的采样速率和处理速度也越来越高，因而对宽带信号处理的困难在日益加剧。例如高分辨率地理资源观测，其巨量数据传输和存储就是一个艰难的工作。另一方面，在实际应用中，为了降低存储、处理和传输的成本，人们常采用压缩方式以较少的比特数表示信号，大量的非重要的数据被抛弃。这种高速采样再压缩的过程浪费了大量的采样资源，于是很自然地引出一个问题:能否利用其它变换空间描述信号，建立新的信号描述和处理的理论框架，使得在保证信息不损失的情况下，用远低于奈奎斯特采样定理要求的速率采样信号，同时又可以完全恢复信号? 即能否将对信号的采样转变成对信息的采样? 如果这个问题被解决，就可以极大地降低信号的采样频率及数据存储和传输代价，显著地降低信号处理时间和计算成本，并将带领信号处理进入一个新的革命时代。近几年来出现的一种新颖的理论——Compressed sensing(也称为Compressive sampling) 表明这是可能的。目前还没有一个统一的中文词汇与之对应，有人称之为压缩传感，也有人称其为压缩感知(以下均采用压缩感知) 。

压缩感知理论与传统奈奎斯特采样定理不同，它指出，只要信号是可压缩的或在某个变换域是稀疏的，那么就可以用一个与变换基不相关的观测矩阵将变换所得高维信号投影到一个低维空间上，然后通过求解一个优化问题就可以从这些少量的投影中以高概率重构出原信号，可以证明这样的投影包含了重构信号的足够信息。在该理论框架下，采样速率不决定于信号的带宽，而决定于信息在信号中的结构和内容。事实上，压缩感知理论的某些抽象结论源于Kashin创立的范函分析和逼近论，最近由

Candès，Romberg ，Tao和Donoho等人构造了具体的算法并且通过研究表明了这一理论的巨大应用前景。从信号分析角度来讲，傅立叶变换是信号和数字图像处理的理论基础，小波分析将信号和数字图像处理带入到一个崭新的领域。多尺度几何分析是继小波分析后的新一代信号分析工具，它具有多分辨、局部化和多方向性等优良特性，更适合于处理图像等高维信号。这些研究工作都为压缩感知理论奠定了基础。显然，在压缩感知理论中，图像/信号的采样和压缩同时以低速率进行，使传感器的采样和计算成本大大降低，而信号的恢复过程是一个优化计算的过程。因此，该理论指出了将模拟信号直接采样压缩为数字形式的有效途径，具有直接信息采样特性。由于从理论上讲任何信号都具有可压缩性，只能找到其相应的稀疏表示空间，就可以有效地进行压缩采样，这一理论必将给信号采样方法带来一次新的革命。压缩感知理论的引人之处还在于它对应用科学和工程的许多领域具有重要的影响和实践意义，如统计学、信息论、编码等。本文以稀疏信号的压缩观测及重构为主线，综述了压缩感知理论以及与之相关的信号稀疏变换、观测矩阵设计、重构算法等一系列最新理论成果和应用研究，描述了国内外的研究进进展，讨论了其中的公开问题，展望了未来的研究方向。

1.2 CS理论框架

在传统理论的指导下，信号X的编解码过程如图1.1所示：编码端首先获得X 的N点采样值，经变换后只保留其中K个最大的投影系数并对它们的幅度和位置编码，最后将编得的码值进行存储或传输。解压缩仅是编码过程的逆变换。实际上，采样得到的大部分数据都是不重要的，即K值很小，但由于奈奎斯特采样定理的限制，采样点数N可能会非常大，采样后的压缩是造成资源浪费的根本所在。

图1.1传统编解码理论框图

CS 理论的信号编解码框架和传统的框架大不一样，如图1.2 所示。CS 理论对信号的采样、压缩编码发生在同一个步骤，利用信号的稀疏性，以远低于Nyquist采样率的速率对信号进行非自适应的测量编码。测量值并非信号本身，而是从高维到低

维的投影值，从数学角度看，每个测量值是传统理论下的每个样本信号的组合函数，即一个测量值已经包含了所有样本信号的少量信息。解码过程不是编码的简单逆过程，而是在盲源分离中的求逆思想下，利用信号稀疏分解中已有的重构方法在概率意义上实现信号的精确重构或者一定误差下的近似重构，解码所需测量值的数目远小于传统理论下的样本数。

压缩感知的核心思想是压缩和采样合并进行，并且测量值远小于传统采样方法的数据量，突破了香农采样定理的瓶颈，使高分辨率的信号采集成为可能。

压缩感知理论主要包括信号的稀疏表示、随机测量和重构算法等三个方面。稀疏表示是应用压缩感知的先验条件，随机测量是压缩感知的关键过程，重构算法是获取最终结果的必要手段。

图1.2 CS理论下数据的编解码过程

压缩感知关键要素包括稀疏表示、测量矩阵和重构算法。

信号在某种表示方式下的稀疏性，是压缩感知应用的理论基础，经典的稀疏化的方法有离散余弦变换（DCT）、傅里叶变换（FFT）、离散小波变换（DWT）等。

最近几年，对稀疏表示研究的另一个热点是信号在冗余字典下的稀疏分解。这是一种全新的信号表示理论：用超完备的冗余函数库取代基函数，称之为冗余字典，字典中的元素被称为原子。目前信号在冗余字典下的稀疏表示的研究集中在两个方面：一是如何构造一个适合某一类信号的冗余字典，二是如何设计快速有效的稀疏分解算法。目前常用的稀疏分解算法大致可分为匹配追踪（Matching Pursuit）和基追踪（Basis Pursuit）两大类。

压缩感知理论中，通过变换得到信号的稀疏系数后，需要设计压缩采样系统的观测部分，它围绕观测矩阵Φ展开。观测器的设计目的是如何采样得到M个观测值，并保证从中能重构出长度为N的信号X或者稀疏基基ψ下等价的稀疏系数向量。

CandeS和Tao等证明:独立同分布的高斯随机测量矩阵可以成为普适的压缩感知测量矩阵。2007年Candes等研究者建立了著名的约束等距性（RIP）理论，即要想使信号完全重构，必须保证观测矩阵不会把两个不同的K项稀疏信号映射到同一个采样集合中，这就要求从观测矩阵中抽取的每M个列向量构成的矩阵是非奇异的。

Donoho给出压缩感知概念的同时定性和定量的给出测量矩阵要满足三个特征：(1)由测量矩阵的列向量组成的子矩阵的最小奇异值必须大于一定的常数；(2)测量矩阵的列向量体现某种类似噪声的独立随机性；(3)满足稀疏度的解是满足1范数最小的向量。

目前常用的测量矩阵包括：

（1）随机高斯矩阵。矩阵每个元素独立地服从均值为0，方差为M

1的高斯分布。（2）随机贝努利矩阵。矩阵的每个元素独立地服从对称的贝努利分布，等概率为M

1

或-M

1。

（3）部分正交矩阵。先生成N×N的正交矩阵U（如傅里叶矩阵），然后在矩阵U中随机地选取M行向量，对M×N矩阵的列向量进行单位化得到测量矩阵。

（4）部分哈达玛矩阵。生成大小为N×N的哈达玛矩阵，然后在生成矩阵中随机地选取M行向量，构成一个M×N的矩阵。

（5）托普利兹和循环矩阵。首先生成一个向量u，由向量u生成相应的轮换矩阵或托普利兹矩阵U，然后在矩阵U中随机地选取其中的M行而构造的矩阵Φ。

（6）稀疏随机矩阵。首先生成一个零元素的矩阵Φ，在矩阵Φ的每一个列向量中，随机地选取d个位置，然后在所选取的位置的值赋为1。

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

此外，迭代阈值法也得到了广泛的应用，此类算法也较易实现，计算量适中，在贪婪算法和凸优化算法中都有应用。但是，迭代阈值法对于迭代初值和阈值的选取均较敏感，且不能保证求出的解是稀疏的。

就目前主流的两种重建算法而言，基于1范数最小的重建算法计算量巨大，对于大规模信号无法应用；贪婪算法虽然重建速度快，但是在信号重建质量上还有待提高。

1.3 本文框架结构

本文通过对压缩感知理论进行系统认真的学习和研究，查阅了大量的国内外相关的文献和资料，主要完成了围绕正交匹配追踪算法的信号和图像重构处理。本文的主要结构如下所示：

第一章，绪论。本章首先介绍了压缩感知理论研究的背景和意义，然后综述了

CS理论的理论框架，最后陈述了本文的内容安排。

第二章，国内外研究现状。本章介绍了压缩感知理论的历史、发展及将来的研究方向。然后介绍了其在光学成像方面的应用。

第三章，压缩感知（CS）基本理论。本章详细阐述了压缩感知理论的基本原理。首先讲述了CS理论的数学原理，然后围绕压缩感知的三个关键技术，信号的稀疏表示、观测矩阵的设计和重构算法展开讨论，介绍了该理论是如何实现的。最后介绍了其在现实中的最新应用及一些不足和需要改进之处。

第四章，压缩感知实现及结果分析。本章首先简单介绍了传统图像压缩技术在变换编码方面的重构方法。然后完成了分别基于离散傅里叶变换（DFT）和离散余弦变换的一维信号和二维图像的OMP算法重构，并进行了性能参数方面的对比。

第五章，总结和展望。本章总结了本设计所完成的工作，并对其中的缺陷做出了说明，指出了所采用算法的不足指出，对下一步的工作做了展望。

第2章 国内外研究现状

压缩感知理论是近几年刚刚兴起的理论，但却展现了强大的生命力引起了广泛的关注，下面我们将对该理论的历史和发展历程做出介绍。

2.1 从稀疏重构到压缩感知

早在压缩感知理论正式提出以前，1970年代的石油勘探地震数据处理中，人们已经发现香农-奈奎斯特采样定理的限制是“可以突破的”。由于测量条件的限制，获取的数据十分有限，根据传统理论并不足以重构地层结构。幸运的是，地层内部是均质的，只是层与层之间又不连续，且这种不连续是“稀疏的”。当理由这种稀疏性先验知识时，便可以较好的反演地质结构。

从数学上看，地层结构反演属于典型的逆问题，逆问题往往是病态的，需要加入正规化约束以得到有用的结果。”稀疏性”是近二十年来逐步发展起来的一种正规化约束，含稀疏性约束的逆问题被称为稀疏重构问题，其本质是从超完备字典Φ中寻找尽可能少的原子（选出的原子只占所有原子中很少的一部分），通过它们的线性组合来逼近给定的向量y 。即

t Findsparse x ，s.t x y Φ≈ (式2.1)

定义2.1：对于M ?N 维矩阵Φ，若其各列具有单位长度，则称之为字典，矩阵的各列N i i ,...,1,=φ被称为原子。

稀疏重构问题本质上是一种后端处理方法。其应用是在数据获取之后，并没有与前端的数据获取系统相结合。

采样理论的研究自Shannon 以后也经历着不断的发展，其中基于“新息率”（rate of innovation ）的采样策略与压缩感知理论密切相关。考虑在单位时间内具有有限自由度的信号，称该自由度为新息率。实际应用中有很多这样的信号，如Poisson 过程、非均匀采样和分段多项式等。这些信号不是带限的，根据Shannon 定理，均匀矩形脉冲采样条件下无法精确重构。文献[11-14]指出基于高于新息率的非均匀采样和适当构造的核函数，这些信号仍可以精确重构。

Analog-to-information conversion(AIC)是根据压缩感知理论设计的一种新概念采样体制，其充分利用这样一个事实：许多射频信号虽然具有很大的带宽，但是他们的“新息率”有限，因此可以根据其新息率，而非带宽进行采样。

随着稀疏重构和新兴采样定理研究的不断深化，很多学者发现，当测量数据不完全时，有时甚至只有很小一部分测量数据，利用该方法仍可以很好的重构原图像。2006年Candes, Romberg 及Tao 等人在研究高度欠定的核磁共振成像问题时，得出一个重要的结论：当测量矩阵为Fourier 矩阵时，O(K*log(N))的数据采集量能将N 维空间的

K 稀疏信号精确重建。2007年，Candes 和 Romberg 将Fourier 测量方式推广到任意正交测量并得到类似的结论。这两项工作表述了一个问题：可通过低维频域(或时域)信号实现高维稀疏时域(或频域)信号的精确重建。

这个令人惊喜的发现促使压缩感知理论的诞生：既然利用部分测量数据就可以精确重构原图像，那么为什么不在测量时就仅获得所需的数据，而不是耗费大量资源来获取全部数据。其后Candes, Romberg 及Tao 等人，初步建立了压缩感知的理论基础。

压缩成像的组成可以分为两个部分：数据的获取过程和图像的重构过程。其中，后者和稀疏重构的研究一脉相传，但需特别考虑二维图像所涉及的大规模数据下的保精确度快速计算问题；前者的研究理论上需研究使得“稀疏重构”能够恢复原信号的测量矩阵的行质，即可重构条件，应用中还需考虑满足重构条件的测量矩阵的物理实现问题，即利用适当的硬件设备完成压缩采样。

2.2 稀疏重构算法和重构条件研究

首先给出l p 范数的定义，需要指出的是，当参数p 在某些范围内取值时，

(式2.2)的定义可能不满足三角不等式，因此不是真正意义上的范数，但不影响讨论，仍称其为范数。

定义2.3： 信号T N x x x ),...,(1=的l p 范数p x

为： （式2.2）

其中当p=0时，（式2.2）等价于计算x 中的非零元素的个数，当p=2时，（式2.2）为空间中的欧氏范数，当∞→p 时， 根据定义2.1，图像的稀疏性最本质的度量为l 0范数，则（式2.1）的数学描述为

0min x x

s.t. x y Φ= （式2.3） 若测量噪声中含有噪声，则重构模型为

0min x x s.t. δ≤Φ=2x y （式2.4）

其中参数δ反映了测量噪声的水平。

（式2.3）和（式2.4）等含l 0范数的稀疏重构问题已被证明是NP 难解的，需要

寻找多项式时间内可解得近似方法，现有的主要方法可以分为：

1)贪婪算法 基本思想是迭代地从字典中选择原子，并计算相应的系数，使得这些原子的线性组合与测量数据之间的差别逐渐缩小。以最基本的正交匹配追踪（Orthogonal Matching Pursuit,OMP ）算法为例，设当前迭代结果为k x ，已选取原子

的索引为Ω，它是{

}N ,...,1的一个子集，令{}Ω=Ω\,...,1N c ；设残差p p N i i p x x /11)(∑==i N

i p x x ≤≤→1max

k k x y r Φ-=，计算k r 与字典中的原子的相关性k T r Φ，取其中绝对值最大的元素，

即为索引j ；令更新后的索引集为{}j ?Ω=Ω，则更新后的信号为

2

1min arg x y x x k Ω+Φ-=，其中ΩΦ为按Ω索引Φ的各列后得到的子矩阵。由于ΩΦ是线性无关的，因此1+k x 可以通过最小二乘计算得到。

其它的贪婪算法还有StOMP 算法、Regularized OMP(ROMP)算法以及Compressive Sampling Matching Pursuit(CoSaMP)等。

在计算复杂度方面，从形式上看，若字典Φ是显示的，则贪婪算法涉及矩阵向量之间的乘法运算k T r Φ，其运算量为O(MN),若Φ具有隐式的快速变换，则计算量可显著降低。此外，求解1+k x 的最小二乘过程可以利用ΩΦ的QR 分解，其运算量为O(MK)。

注：称Φ是显式的，若x Φ和r T Φ的运算可以通过矩阵和向量的乘法运算完成；相对应的，称Φ是隐式的，是指x Φ和r T Φ的运算可以通过函数运算完成。

2）凸优化 基本思想是将（式2.3）和（式2.4）“松弛”为凸优化问题，利用凸函数性质，实现多项式时间内的稀疏重构。由于l 1范数是最接近l 0范数的凸函数，

因此常将l 0范数松弛为l 1范数，文献[27-31]讨论了l 0范数与l 1范数之间的等价特性

条件。

内点法（interior-point ）为最早的l 1范数凸优化求解方法，可用的软件包有SeDuMi

和MOSEK 等。但总的来说，内点法的重构结果受参数选取影响较大，且计算复杂度高，不适用于二维像等大数据量应用问题。

梯度下降类算法是一阶精度的l 1范数凸优化求解方法，该类算法在每步的迭代中

计算残差的梯度：

（式2.5）

)(1k temp k k k x x x x -+=+γ （式2.6）

其中τ，k α，k γ均为控制参数。

其它类似的方法包括TwIST 和GPSR 等。当测量矩阵满足可重构条件时，这些方法能迅速识别信号中稀疏分量的位置，并重构原信号。

3)其它算法 一些非凸优化算法，如将l 0范数松弛为l p ，0

先验分布引入稀疏性，再用贝叶斯方法实现稀疏重构；此外，还有一些启发式算法（heuristic algorithms ）,用借鉴图模型和编码理论中的belief-propagation 和message-passing 技术。

重构条件的研究就是讨论稀疏重构解得唯一性条件。设1x 和2x 是两个稀疏解，

则有：0)(2121=-Φ?Φ=Φx x x x ，即矩阵Φ将稀疏度为2K 的信号21x x -映

122)()(min arg z x z y x x z x k k k T T k x temp τα+-+-ΦΦ-=

射为零，这意味着当且仅当Φ的每个2K 列子矩阵均为单射时，稀疏解是唯一的。在实际运用中，不仅要求稀疏解是唯一的，还要求其实稳定的，假设测量数据有扰动y ?，其导致解的变化x ?满足：x y ?Φ=?，稳定性是指微小的y ?不会导致较大x ?。

约束等距性（Restricted Isometry Property ，RIP ）是压缩感知理论中用以描述重构条件的指标，但对于给定的测量矩阵Φ，验证其是否满足RIP 是NP 难解问题。此外，稀疏重构理论中常用的字典相关性，也可以用于重构条件的描述，它的优点是计算简单，缺点是得到的条件不是紧致的，如根据相关性理论，M 个测量数据（即测量矩阵的行数为M ）至多可恢复稀疏度)(M O K =的信号，而根据RIP 当测量矩阵为特定的随机矩阵时，可重构信号的稀疏度可以放宽为))log(/(N M O K =。

2.3 压缩感知在光学成像中的应用

压缩感知应用于光学成像的首个实际系统是Rice 大学Baraniuk 等建立的“单相素相机”，其原理图与实际系统如图2.3.1

左图中，入射光线经过第一个透镜之后进入成像系统，照射在放置于像平面的数字微镜设备（Digital Micro-mirror Device ，DMD ）阵列上。DMD 阵列由数百万个尺寸为um 量级的微小反射镜组成，每个反射镜的角度可以独立控制（图中用黑白两色表示两个不同的反射角度），从而可以控制其上的反射光线的方向。DMD 阵列的反射光线经过第二个透镜，其中仅一个方向的光线进入不具备空间分辨力的单相素光子探测器，经过AD 转换后以数字信号的形式被记录下来。DMD 上的每个微小反射镜的角度是可以控制的，频率可以到达310Hz ，所有小反射镜角度控制的一次实现称为一个“测量模式”

。每个“测量模式”下，探测采集一个数字信号，为了获得足够多的数

图2.3.1 单相素相机与实际系统图

据，需要进行多次测量。“单相素相机”实际系统如右图所示，该系统目前已可获取原理验证性图像。值得一提的是rice大学的单像素相机硬件成本昂贵，重建算法效率低下，还有很大的改进空间。

其它基于压缩感知原理建立的成像系统有：Compressive Structured Light for Recovering Inhomogeneous Participating Media, Compressive Dual Photography, Random Lens Imager和Tranform Imager等。

特别地，美国国防高级研究计划局（DARPA）资助的Multiple Optical Non

-Redundant Aperture Generalized Sensors(MONTAGE)致力于通过有机结合光学系统、检测和后处理技术的最新进展，开发革命性的成像系统。Compressive Optical MONTAGE Photography Initiative(COMP-I)是MONTAGE计划下的一个子项目，其目标是在不损失成像系统分辨率的条件下，减小焦距，制造“超薄”成像系统。目前，已实现了一个5mm的环形孔径透镜，其分辨率与40mm焦距的传统成像系统相当。

“超薄”成像的关键技术之一是所谓的焦平面编码，即在焦平面处设置二值幅度调制掩膜，固定于探测器上，以完成对焦平面光场的某种变换，而探测器测量的是这种变换下的“系数”（本质上，每个测量是光场的一种线性组合）。最后在计算机上将测量数据逆变换得到原图像。

在光学成像领域，将与之相类似的技术称之为“计算成像”。传统的成像系统利用透镜或反射镜系统形成图像，并利用探测器进行采样。数据处理在传统概念中被认为是后处理过程，并不纳入成像系统设计的考虑之中。随着电子学的发展，在探测器和光场操控、编码方面取得了重大的进展；另一方面，光学系统的设计却受限于信息光学中物理定理的限制，为了提高分辨率，体积重量不断增加。因此，现代成像系统的设计不能仅考虑前端的光学系统，还需考虑探测器和图像重构的因素。“计算成像”的概念就是在这样的背景下提出的，它同时需要光学系统、采样以及图像重构的技术，于压缩成像有着异曲同工之处。

目前，已有若干类似的“计算成像”原理验证系统。Duke大学Duke Image and Spectroscopy Program(DISP)小组在DARPA MONTAGE计划的支持下，在多路光学技术中开展了很多研究。例如，验证了红外相机可以采用同时利用多路小孔径光学透镜收集若干低分辨率图像，但不是当长焦距大孔径透镜，是想高分辨率成像。

如上所述，CS测量矩阵的实现硬件是将CS推向实用的必备条件。在RIP理论指导下，莱斯大学R. Baraniuk教授等研制的单像素相机和A/I转换器。随后，有多种CS硬件相继报道，例如，麻省理工学院教授等人研制的MRI RF脉冲设备，麻省理工学院W. T. Freeman教授等人研制的编码孔径相机，耶鲁大学研制的超谱成像仪，伊利诺伊州立大学O. Milenkovic等人研制的DNA微阵列传感器，我们课题组研制的CS滤波器和混沌腔，等等。这些CS硬件实现将CS向实用化推进了一大步，然而仅

能处理有限维信号，无法处理无限维信号。另外，由于缺乏有效的CS矩阵判别理论，除rice大学的单像素相机(硬件成本昂贵，重建算法效率低下)外，其它硬件均缺乏严格的理论分析。

第3章 压缩感知（CS ）基本理论

信号的稀疏重构主要包括三个方面内容：1）信号的稀疏表示方法，它是重构的前提；2）稀疏约束项的构造，它在一定程度上决定了重构所需的压缩采样数量和重构过程的复杂度；3）含稀疏约束项的最优化求解方法，它决定了重构的计算复杂度、精度和稳健性。信号的压缩采样理论主要讨论为使稀疏重构能精确、稳定恢复原信号，测量矩阵需满足的条件。

3.1 压缩感知背景

考虑一个实值的有限长一维离散时间信号X ， 可以看作为一个N R 空间N ×1 维的列向量， 元素为X[ n] ， n = 1 ，2 ， ?N 。N R 空间的任何信号都可以用N ×1

维的基向量N i i 1}{=ψ的线性组合表示。 为简化问题，假定这些基是规范正交的。把向

量N i i 1}{=ψ作为列向量形成N ×

N 的基矩阵Ψ: = [N ψψψ,...,,21] ， 于是任意信号X 都可以表示为：

i N i i X ψ=

∑=1θ or ψΘ=X （式3.1） 其中Θ是投影系数],[][>ψ<==Θi i X θ构成的N ×1 的列向量。反变换后得

到： X T ψ=Θ （式3.2）

显然， X 和Θ是同一个信号的等价表示， X 是信号在时域的表示，Θ则是信号在Ψ 域的表示。 如果Θ的非零个数比N 小很多，则表明该信号是可压缩的。一般而言，可压缩信号是指可以用K 个大系数很好地逼近的信号， 即它在某个正交基下的展开的系数按一定量级呈现指数衰减， 具有非常少的大系数和许多小系数。这种通过变换实现压缩的方法称为变换编码。

变换编码在数据采样系统中，比如数码相机，发挥了重要作用。 在这些系统中， 采样速率高但信号是可压缩的，采样得到N 点采样信号X ；通过X T ψ=Θ变换后计算出完整的变换系数集合{θi} ；确定K 个大系数的位置，然后扔掉N-K 个小系数；对K 个大系数的值和位置进行编码，从而达到压缩的目的。

图3.1 传统方法压缩过程

但这种传统的信号编解码方法存在显著的一些缺点：

（1）考虑到奈奎斯特采样定理，为了能获得很好的信号分辨率，采样间隔会取的很小，这样便造成了原始信号长度会很长，因此变换过程也会消耗较长的时间。

（2）K 个需要保留的重要分量的位置，是随着信号的不同而不同的。因此，这种策略是“自适应”的，而且需要分配多余的空间来存储这些位置。

（3）一旦在传输的过程中K 个分量的某几个丢失了，后果便可想而知。例如按照以上方法制作一个音频设备，便会存在以下的一些缺点：带来电力的大量消耗和用户的不满、带来存储空间的增加、带来较差的抗干扰能力等。

针对上述所遇到的问题，压缩感知理论指出：对于信号1+∈N R X ，如果它在某个正交变换基Ψ上是可进行稀疏变换的，则选取一个与Ψ不相关的M × N 维观测矩阵Φ来观测得到原始信号的M 个降维观测向量Y ，即Y = ΦΘ，其中N M R ?∈Φ，Θ是原始信号在正交变换基Ψ 域的稀疏表示形式。拥有了这M 个测量值Y 和观测矩阵Φ，最后通过求解一个优化问题便可以得到原始信号的精确重构或近似逼近。重构算法的问题是基于如下严格的数学最优化问题： 目标函数：0

min Θ，且满足等式约束：Y X T =Φψ （式3.3） 综合以上所述，得到了基于压缩感知理论框架下的信号编解码流程图，如图 3.2所示。

3.2 压缩感知理论

3.2.1压缩感知的前提条件—稀疏性和不相干性

CS 隐含的两个基本前提：稀疏性和不相关性。前者属于信号的性质，后者和感知（观测）形式有关。

稀疏性：稀疏性表达了这样一个思想，一个连续时间信号的“信息速率”可能比由带宽所决定的香农采样率要低很多，或者，一个离散时间信号所依赖的自由度数目远远低于它的长度。更准确地说，CS 利用了这样一个事实，即许多自然信号在某个合适的基Ψ下具有简洁的表达。

不相关性：不相关性说明用于采样信号的波在基Ψ下有很稠密的表达。不相关性表达了这样的思想，正如时间域的Dirac 或者冲击信号可以在频域展开那样，在基Ψ下

图3.2 压缩感知理论框架下的信号编解码流程

具有稀疏表示的信号一定可以在获得它们的某个域中展开。

1 稀疏性

众所周知，任意长度为N 的离散信号X 都可以表示为一系列基函数的叠加， 即可以在任何正交基下用下式表示：

（式3.3）

其中ψ由一组基向量{}N

i i 1=ψ构成的正交基，例如，sinusoids ，尖峰spikes 、B -splines ，wavelets 。Θ为展开系数。展开系数大，说明信号和基足够相似。如果信号在基ψ下的展开系数在很小的集合上有值，我们就说该信号在ψ域是稀疏的，如果有值序列集中在一个小范围内，那么我们就说该信号是可以压缩的。本章我们将集中研究具有稀疏表示的信号，其中X 是K 个基向量的线性组合，K<

许多自然信号在一些基下有简洁的表达。图3.3（a ）是一幅具有N （N =512×512）

个像素点的coins 图像向量N R X ∈，我们在9/7小波基]...,[,,2,1N ψψψ=ψ下展开该向

量，如（式3.4），其中ψ是,,2,1...,N ψψψ为列向量构成的N N ?的矩阵，是正交基。

图3.3（b ）是coins 图像的9/7小波系数在一维下的表示。图2.3（c ）展示了这样一个事实：将图像在9/7小波变换域丢掉93.75%的小系数后得到的逼近图像尽管PSNR 只有29.09dB ，但肉眼很难察觉到失真。由此可见，尽管原图中几乎所有的像素都是非零值，它在9/7小波域中却是稀疏的：大部分小波系数都很小，少数的大系数（1/16）就可以捕获信号的大部分信息。

本例中仅仅保留展开（式3.4）中Θ的())161(N K K =个大系数得到K K X ψΘ=，其中K Θ表示系数向量的除K 个大系数外其余置0的向量。该向量从严格意义上说是稀疏的，因为K<

现在稀疏的含义很清楚了：如果x 在某个变换域下是稀疏或者可压缩的，就意味着将x 的系数N i i ,...,1,=θ按幅值大小排列衰减很快，那么x 可以由K 个大系数很好地逼近K K X ψΘ=。图3.3（c ）所示告诉我们，可以丢弃除了少数几个系数外的所有小系数而不会带来视觉上的损失。我们称至多有K 个非零项的向量为K -稀疏，且有

K K X X Θ-Θ=-。稀疏性原理是大部分现代有损压缩编码算法和许多其它应用的基础。不过在传统编码中，这K 个大系数的位置必须事先确定。更一般地，稀疏性是一个基本的建模工具，可以进行信号的精确统计估计和分类、有效的数据压缩等等。而近几年来Candès 等人提出的压缩感知理论使得稀疏性有了更加令人惊奇的深远含义，即信号稀疏性对采样本身有重要意义，稀疏性决定了我们可以摆脱奈奎斯特采样频率的约束，并可以做到高效地非自适应地采样信号。

2 不相关性

Candès ， Romberg 等人已经证明一个降维的投影集合包含了重构稀疏信号的足够信息。这就是压缩感知（CS ）理论的核心内容。在CS 中，假定信号在某个变换域的系数是K 项稀疏的，我们不直接对K 个重要的系数i θ直接编码，而是将信号的系数向量投影到另一个基函数集合{

}M m m ,...,1,=φ上，观测得到M (<=

列向量，观测矩阵Φ是一个以每个基向量m φ作为行向量的N M ?矩阵。由于M<

CS 理论告诉我们，当满足一定条件时，也即是基n ψ不能稀疏表示m φ（该条件被称为两组基不相关）并且观测值个数M

足够大，那么就可以从一个相似规模的集合

(a)512x512的coins 原始图像 （b ）coins 图像的9/7小波系数在一维下的表示

（c ）1/16系数重构图像（PSNR=29.09dB ） 图3.3稀疏重构图像案例

{}m y 中恢复大系数集合{}n θ，继而也就可以得到信号X 。许多对基都满足不相关性质，例如，三角尖峰和傅里叶基中的正弦波不相关，傅里叶基和小波基不相关。重要的是，任意一个固定的基和一个随机产生的基也以高概率满足这种不相关。因此在CS 理论中随机矩阵被广泛应用于CS 观测中。在框架下或者基下可以找到稀疏表示的信号都可以以同样的方式从不相关观察中恢复。

文献[3]给出了相关性度量的具体定义，如下。

定义3.2：观测系统Φ和表示系统ψ之间的相关性度量用μ表示，则有如下式子成立：

（式3.4）

简单来讲，相关性度量的是两个矩阵Φ和ψ的元素之间的最大相关性。如果Φ和ψ包含了相关的元素，则相关性很大；否则，就很小。相关系数取值范围为],1[),(N ∈ψΦμ。压缩采样研究的是具有低相关性的两个系统。下面给出一些例子。

（1）Φ是尖峰基)()(k t t k -=δ?，ψ为傅立叶基n jt i j e n t /22/1)(π-=ψ，则有1),(=ψΦμ。进一步讲，尖峰信号和正弦信号不仅在一维而且在任何维，例如2D ，3D 空间都具有最大的不相关性。

（2）ψ为小波基，Φ是noiselet 。这里，noiselet 和Haar 小波基间的相关系数是2，noiselet 和Daubechies db4及db8小波基间的相关性分别是2.2和2.9。这也可以扩展到高维情况。noiselets 也和尖峰信号及傅立叶基高度不相关。人们对noiselets 感兴趣基于以下两个事实：1）它们和为图像数据和其它类型的数据提供稀疏表示的系统不相关；2）它们具有快速算法。noiselet 变换的时间复杂度为O (N )，而且类似于傅立叶变换，noiselet 矩阵不需要存储。这一点对于高效的数字计算是至关重要的。如果没有高效的计算，CS 的实用性就会大打折扣。

（3）Φ为随机矩阵，则ψ可以是任何固定的基。此时它们之间具有极大不相关。例如，Φ可以通过在单位球面上独立均匀地采样并做规范正交化得到，此时，Φ和ψ间的相关性以很高的概率为N log 2。各项服从独立同分布的随机波形{

})(t k ?，例如高斯分布或者1±，也表现出和任何固定基ψ具有很小的相关性。

研究者们通过大量的实验分析，得出如下结论：精确重构所需要的观测值个

数依赖于稀疏变换基和观测基之间的不相关性。不相关性越强，所需的个数越少；反之，相关性越强，例如ψ=Φ，则需要采样所有的系数才能保证精确重构。

>

ψΦ≤≤j k N j k n ψ?μ,max ),(,1

3.2.2 三个关键技术

从以上压缩感知理论的介绍中我们可以看出，压缩感知理论主要包括以下三个方面的内容：

（1）信号稀疏表示；

（2）信号的编码测量即观测矩阵的设计；

（3）信号重构算法的设计。

信号的稀疏表示是指当将信号投影到某个正交变换基时，一般情况下绝大多数的变换系数的绝对值都是很小的，得到的变换向量也是稀疏的或者是近似稀疏的，这是原始信号的一种简洁的表达方式，也是压缩传感理论的先验条件。信号必须得在某种变换下才可以进行稀疏表示。通常我们可以选取的变换基有离散傅里叶变换基（DFT ）、离散余弦变换基（DCT ）、离散小波变换基（DWT ）、Curvelet 变换基、Gabor 变换基还有冗余字典等。在信号的编码测量即观测矩阵的设计过程中，要选择稳定的观测矩阵，观测矩阵的选取必须满足受限等距特性(Restricted Isometry Property ，RIP)准则，才能保证信号的投影能够保持原始信号的结构特征。通过原始信号与观测矩阵相乘我们可以获得原始信号的线性投影值。最后设计合适的重构算法从所得到的观测值和原来的观测矩阵来重构原始始号。

所以对压缩感知理论的研究也主要是基于这三个方面的内容：

（1）信号的稀疏表示。即对于信号N R X ，如何找到一个合适的正交基或者紧框架Ψ，以使得原始信号在Ψ上的表示是稀疏的。

（2）观测矩阵的设计。即如何设计一个平稳且满足受限等距特性条件或者与变换基Ψ 满足不相关约束条件的M × N 维观测矩阵Φ，以保证信号稀疏表示后的向量Θ能从原来的N 维降到M 维时所包含的重要信息没有受到破坏，从而保证原始信号的准确重构。这个过程也就是压缩感知理论中信号的低速采样过程。

（3）重构算法的设计。即如何设计快速有效且稳定的重构算法，从所得到的低维观测向量中准确地恢复原始信号。

下面我们对压缩感知理论的这三个关键技术做一个详细的总结和分析，以为后文对压缩感知理论在图像重构方面的研究打下基础。

3.2.3信号的稀疏表示

从傅立叶变换到小波变换再到后来兴起的多尺度几何分析（Ridgelet ，Curvelet ，Bandelet ，Contourlet ），科学家们的研究目的均是为了研究如何在不同的函数空间为信号提供一种更加简洁、直接的分析方式，所有这些变换都旨在发掘信号的特征并稀