论文题目: 压缩感知
学 院： 计算机与信息学院 专业年级： 电子信息工程2010级 学 号： 102260004027 姓 名： 王吉祥 指导教师、职称： 潘晓文副教授
2012年 11 月15日
I
压缩感知
摘 要：压缩感知在传感方面的应用越来越广泛, 压缩传感采用非自适应线性投影来保持信号的原始结构, 能通过数值最优化问题准确重构原始信号. 压缩传感以远低于奈奎斯特频率进行采样, 在压缩成像系统、模拟/信息转换、生物传感等领域有着广阔的应用前景。
关键词：压缩感知，压缩传感
传统的信号获取和处理过程主要包括采样、压缩、传输和解压缩四个部分, 如图1所示. 其采样过程必须满足香农采样定理, 即采样频率不能低于模拟信号频谱中最高频率的2倍. 在信号压缩中, 先对信号进行某种变换, 如离散余弦变换或小波变换, 然后对少数绝对值较大的系数进行压缩编码, 舍弃零或接近于零的系数. 通过对数据进行压缩,舍弃了采样获得的大部分数据, 但不影响\\感知效果\"[1]. 例如, 在运用数百万像素的数码相机对场景进行成像时, 将会得到海量的像素信息, 但通过压缩编码后,只对部分信息进行存储和传输, 最后通过相应的解压缩算法对原始图像进行重构.
如果信号本身是可压缩的, 那么是否可以直接获取其压缩表示(即压缩数据), 从而略去对大量无用信息的采样呢？Candés在2006年从数学上证明了可以从部分傅立叶变换系数精确重构原始信号, 为压缩传感奠定了理论基础[2]. Candés和Donoho在相关研究基础上于2006年正式提出了压缩传感的概念[1;3]. 其核心思想是将压缩与采样合并进行,首先采集信号的非自适应线性投影(测量值), 然后根据相应重构算法由测量值重构原始信号[1]. 压缩传感的优点在于信号的投影测量数据量远远小于传统采样方法所获的数据量, 突破了香农采样定理的瓶颈,使得高分辨率信号的采集成为可能. 压缩传感理论框架如图2所示.
压缩感知的一些新的研究方向：
1. 非线性测量的压缩感知。讲压缩感知解决的线性逆问题推广到非线性函数参数的求解问题。即：y=A*x 发展到 y = f (x)。广义的讲，非线性测量的压缩感知，可以包括以前的测量矩阵不确定性问题，量化误差问题，广义线性模型问题，有损压缩样本问题。 2. 压缩感知在矩阵分解中的推广应用。主成分分析，表示字典学习，非负矩阵分解，多维度向量估计，低秩或高秩矩阵恢复问题。 3. 确定性测量矩阵的设计问题。随机矩阵在实用上存在难点。随
1
机矩阵满足的RIP是充分非必要条件。在实际中，稀疏表示矩阵和随机矩阵相乘的结果才是决定稀疏恢复性能字典。
1 压缩传感
传统通信系统中的采样遵循的是奈奎斯特抽样定理，该定理指出，为防止在获得信号时损失信息，抽样速率必须大于信号带宽的两倍。在许多应用中，包括数字图像和视频摄像中，奈奎斯特抽样速率太高，不利于数据存储和传输；在其他应用，包括图像系统（医疗浏览和雷达）、高速模数转换中，增加抽样速率代价也很昂贵。压缩感知则是保存原始信号结构的线性投影，然后再从这些投影中将信号重构出来，其速率远远低于奈奎斯特抽样率。CS 理论系统与传统通信系统的类似关系如图 2-1 所示：
由图 2-1 可知，在 CS 系统中，信源和信道编码被 CS 测量（即一个矩阵与信号矢量相乘的形式）代替；信道和信源解码则用 CS 恢复（即依赖于优化准则的恢复算法）替代。压缩感知理论主要由三部分构成：稀疏信号、观测矩阵和重构算法。下面将从这三个方面详细讲述压缩感知的关键技术。
2 原信号的稀疏表示
信号稀疏化的基本概念是：将在空间域里描述的信号，经过某种变换(常用的如傅立叶变换、离散余弦变换、小波变换等)后在变换域中进行描述，改变了原信号能量的分布，即将空间域的信号能量的分散分布变为在变换域的能量的相对集中分布，这样有利于进一步采用其它的处理方式。需要引起注意的是信号的稀疏化本身并不进行数据压缩，它只是把信号映射到另一个域，使信号在所变换的域里更容易压缩，从而，量化操作可以通过有效地比特分配来压缩数据。尽管信号的稀疏化本身并不压缩数据量,但它为新坐标系中的数据压缩创造了条件,去除了大部分相关性,使系数分布相对集中。
根据调和分析理论, 一个长度为N的一维离散时间信号f, 可以表示为一组标准正交基的线性组合
其中，
为列向量, N £ 1的列向量x是f 的加权系数序列, xi = hf;
Ãii = ÃTi f.可见x是信号f 的等价表示, 如图4所示. 如果x只有很少的大系数, 则称信号f 是可压缩的. 如果x只有K个元素为非零, 则称x为信号f 的K稀疏表示.另外, 当信号不能用正交基稀疏表示时, 可以采用冗余字典稀疏表示。原信号的稀疏化表示是压缩感知的前题，但是一般的自然信号在时域都不具有稀疏性，
因此如何选择稀疏基矩阵，使得信号能够得到足够的稀疏表示，是一个非常值得深入研究的问题。Candès指出，平滑信号在傅里叶基（频域）、小波基（小波域）以及不连续边缘的图像信号在曲波变换之后得到的系数都具有稀疏性。Peyré则是把变换基是正交基的条件扩展到了由多个正交基构成的正交基字典中。在某个正交基字典里，根据不同的信号可以自适应地寻找最适合信号特性的一个正交基，对信号进行变换可以得到最稀疏的信号表示。另外，近来出现了一种新的信号表示思想：基于冗余字典（Redundant Dictionary, RD）的信号稀疏表示。与正交基不同的是，
2
冗余字典是采用用超完备的冗余函数，字典中的元素被称为原子，字典的选择应尽可能好地符合被逼近信号的结构，因此可以更好的稀疏逼近信号。简单的说，就是从已有的冗余字典中找到具有最佳线性组合的 项原子来表示一个信号。在本文中所选择的是频域变换中常用的傅立叶变换基。
3测量阵的设计
众所周知，测量矩阵 Φ 必须使得长为 N 的信号 x 从M ( M < N)个观测值中重构出来。由于M < N，所解问题无固定解，但是，又因为 是 稀疏的，而且这 个非零系数在 中的位置是已知的，那么只要x K K sM ≥ K，这个问题就能解出来。解决这个问题的充分必要条件就是对于任意矢量 v ，都与 s一样有着相同的 个非零系数，而且存在某
个
大
于
0
的
常
数
K
ε
，
使
得
也就是说，矩阵Θ必须保存这些 稀疏矢量的长度。当然，总的来说，这 个非零系数在 中的位置是未知的，然而，对于 稀疏且可以压缩的信号而言，能够稳定解决问题的充分条件是，对于任意地的 3 稀疏的矢量 ，Θ必须满足式（2-2）的条件。这个条件被称作约束等距特性(Restricted Isometry Property ,RIP) )。
其他常见的能使传感矩阵满足约束等距性的测量矩阵还包括一致球矩阵、二值随机矩阵、局部傅立叶矩阵、局部哈达玛矩阵以及托普利兹矩阵等[15]. 一致球测量矩阵是指矩阵的列在球Sn¡1上是独立同分布随机一致的, 并且当测量次数为
M =O(K log(N))时, 准确重构信号的概率很大[1;18;19].二值测量矩阵是指矩阵中每个值都服从对称伯努力分布P(©ij = §1=pM) = 1=2[3;15], 研究表明当K · C ¢ M= log(N=M)时, 准确重构信号的概率极大, 并且重构速度很快. 方红等将亚高斯随机投影引入压缩传感理论, 给出了两种新类型的测量矩阵:稀疏投影矩阵和非常稀疏投影矩阵[20]. 局部傅立叶矩阵可以首先从傅立叶矩阵中随机选择M行, 然后再对列进行单位正则化得到[15;21]. 傅立叶矩阵的一个突出优点是可以利用快速傅里叶变换快速计算大大降低采样系统的复杂性, 然而由于其通常只与时域稀疏的信号不相关, 应用范围受到了限制. 局部哈达玛测量矩阵是从N维哈达玛矩阵中随机选择M行。得到[22;23], 当 (其中B是块的维数)时, 置乱(Scrambled)块哈达玛矩阵可以以极大概率准确重构信号. Tsaig对一致球矩阵、二值矩阵、局部哈达玛矩阵以及局部傅立叶矩阵的性能进行了比较, 发现将这几类矩阵作为测量矩阵时重构信号的误差都比较小, 并且随着测量数目的增加进一步减小。
目前，主要用于压缩感知的测量矩阵有以下几种：
（1）高斯随机测量矩阵：即矩阵中的每一个元素都是服从零均值、方差为1 N 的正态分布的独立随机变量。 （2）傅里叶随机测量矩阵：矩阵中的M 个行矢量都服从均匀随机分布，而且，列向量都进行了单位化。 （3）贝努利测量矩阵：又被称为二值随机测量矩阵，即矩阵中的每个元素独立的服从对称的贝努利分布。 （4）非相关测量矩阵：即测量矩阵是从N × N维正交矩阵中均匀随机选取M 个行组成行矢量，并将所有的列向量进行了单位化。按照上述条件，选择了适合的测量矩阵能够保证我们以很高的概率去恢复信号，但是并不能保证肯定可以精确的恢复信号，所以，需要我们继续选择稳定而高效的重构算法。
参考文献
[1] 胡海峰，杨震. 无线传感网中基于空间相关性的分布式压缩感知. 南京邮电
3
大学学报（自然科学版, 2009, 29(6): 12-16.
[2] 石光明, 刘丹华, 高大化, et al. 压缩感知理论及其研究进展. 电子学报, 2009, 37(5):1070-1081.
[3] 沙威.压缩感知引论[OL].[2008]. http:// www. eee. hku/ ~wsha/ Freecode/ Files/ CompressiveSensing. Pdf.
[4] 张春梅, 尹忠科, 肖明霞. 基于冗余字典的信号超完备表示与稀疏分解. 科学通报, 2006,51(6): 628-633.
[5] 陈丹，郑增威，李际军. 无线传感网络研究综述. 计算机测量与控制, 2004, 12(8): 701-704.
[6] 马祖长，孙怡宁，梅涛. 无线传感器网络综述. 通信学报, 2004, 25(4): 114-124.
4
因篇幅问题不能全部显示，请点此查看更多更全内容