压缩感知测量矩阵构造方法研究

前言

  这是我本科毕设的题目，现在毕业过了一个多月才想起来把毕设做的整理一下，写这个博客不为别的，只为纪念一下本科最后的时光吧。记得刚拿到这个题目时，满脑子都是黑人问号，压缩感知到底是个什么东东？也正是因为它，我第一次接触到博客这个强大的东西，在这里搜索关于CS的资料的同时，发现了很多有意思的东西，这里大神云集，能学的东西太多了，所以从那时开始我决定开始玩博客了，取名叫rookie，因为我在这里就是个菜鸟，本科的颓废时光，我要在这里弥补回来，学习大神的成果（总感觉有点偷东西的味道）。说起压缩感知还是挺有缘的，研究生面试的时候，面试老师问我你毕设做的什么，我说压缩感知，他当时就告诉旁边那个老师（也就是现在我的导师），和你的方向一样呀，这个确实和我现在学习的视频编码有一些关联。在此很感谢本科导师孙洁娣老师给我的一些学习上的建议，在我迷茫的时候指点方向。好了，回归正题。

摘要

  压缩感知理论抽样直接减少了多余信息，直接采集有效的信息，刚好弥补了传统抽样会采集极多无用信息的缺点。而测量矩阵的设计又是压缩感知的关键一步。如何设计出采样效率高，重构效果好且易于硬件实现的测量矩阵是我们必须考虑的问题。所以，探索它的设计方法具有重大意义。
  本文首先通过常规压缩技术和压缩感知的对比，指出压缩感知避免了数据冗余问题，能够高效地利用资源并且极大地减少存储空间的特点。其次，在新的理论框架下介绍压缩感知的基本原理，指出测量矩阵需要满足的零空间特性、约束等距特性、非相关性，为测量矩阵的构造提供了理论基础。测量矩阵可以分为随机性测量矩阵和确定性测量矩阵两大类。在随机性测量矩阵中具体给出了随机高斯测量矩阵、随机伯努利测量矩阵。部分哈达吗测量矩阵的构造方法；在确定性测量矩阵中具体给出了托普利兹测量矩阵、循环测量矩阵、稀疏随机测量矩阵的构造方法。最后，利用正交匹配追踪法，采用不同测量矩阵完成一维信号、二维图像仿真实验，验证各个矩阵的性能。

研究背景

   人类已经步入一个数字化的时代，很多信号处理已经从模拟领域进入数字领域[1]。例如，很多身边常用的技术正在悄悄的转变，从模拟收音机到数字调频收音机，从模拟电视信号到数字电视信号，从模拟手机到数字手机，这种转变主要是因为数字信号比模拟信号具有更好的操控性，更灵活的应用和更便宜的成本，具有更易推广的潜质。20世纪曾叱咤风云的模拟胶片相机经过短短几年的时间，于21世纪黯然推出主流市场，直接导致了国产胶卷品牌“乐凯”成为中国人永久的记忆。数字信号的巨大成功使得采样系统获取的数字信息从原来的涓涓细流发展波涛汹涌的浩瀚海洋。常规把模拟信号变成数字信号的过程，离不开奈奎斯特采样定律，该定律从20世纪后半叶开始在采样领域一直处于绝对的主导地位。传统采样定律最初是闻名世界物理学家麦克四特在19世纪发明的，所以常被命名作奈奎斯特抽样定理。而后信息论的创始人香农对这一理论加以明确并最终确定为定理来推广，因而该定律亦被称为奈奎斯特—香农采样定律[2]。该定律指出，在模拟信号到数字信号的转换过程中，当采样频率大于信号中最高频率的两倍时，采样后的数字信号能够完整的保留原始信号中的信息。现实中，一方面，该采样定律经常导致过多的冗余采样或测量值；另一方面，在某些特定的应用中，满足该采样率将耗资巨大，甚至有时受客观条件限制，满足奈奎斯特采样定律的采样频率是根本无法实现的。虽然目前电脑的计算数据速度得到了长足的发展，但对于数码相机成像，视频捕获，医疗成像，射电天文观测，远程监控等应用场合的海量信息的收集、存储等等仍是个艰巨的难题。
   为了解决在处理多维海量信息时不得不解决的存储和传输的问题。通常，对目标信号进行压缩处理，就可以解决海量信息在有限带宽和有限空间下的难题了。信号能够被压缩是因为信号本身具有很大的冗余度，无论声音信号还是图像信号都是如此。常规的压缩技术过程，首先通过AD（模拟数字）转换完成采样，其中含有大量的冗余数据，而后通过变换域挖掘信号的稀疏性，最后通过压缩算法实现压缩。
   这个过程其实造成了巨大的浪费，首先采集大量的冗余数据，然后在压缩过程再把这些冗余数据去掉。为了一开始就丢弃大量的冗余数据，直接采集有效的数据，2006年Emmanuel Candes、Justin Romberg、Terence Tao和David Donoho提出了压缩感知的采样体系。这个理论实质是说，若信号在时间内可以在某变换域稀疏表示，其稀疏度为K，对抽样时，若保证抽样点数(c为常数)，那么，可由高概率地恢复出,即保留了的几乎所有信息。该理论一经提出，便在信息论，信号图像处理，医疗成像、射电天文，模式识别，光学雷达成像和信道编码等诸多领域引起广泛关注[3]。 
   尽管压缩感知理论问世的时间并不长，到目前为止也就10年左右，可一直以来都受到广大学者的广泛关注。在二零零七年的时候，人们更是将这一理论评选为了人类年度最值得期待的科技之一。当前有关Compressive Sensing(CS) 理论的问题总体是围绕着下述三个的关键问题来研究。第一，得到稀疏性信号。第二，构造一个矩阵能够在采集过程中保存信号有效信息。第三，如何基于测量信号重建出目标信号。
   CS理论的核心就是如何设计出高效的矩阵，而它的构造需要考虑很多方面的因素。其中一个因素就是测量信号的波形。当前所用最多的测量波形是独立地服从同一分布的高斯随机波形，独立服从同一贝努力分布的随机波形，正交函数系等[4]。另一个因素就是采样方式。所用最多的采样方式是均匀采样，随机采样，jitter采样等。陶哲轩测不准原理指出：当N是质数时， 个频域数据采集就可将S-稀疏的N维时域信号精确重建[5]。2006年Candes, Romberg及Tao等人在研究核磁共振成像问题时，提出一个重要的结论：当测量矩阵为傅里叶矩阵时， 的数据采集量能将N维空间的K稀疏信号精确重建。以上两个工作向我们表达了一个问题：可利用低维度的信号完成对高维度的信号的准确重构。不得不说，上述结论不具备普遍性，也就是说，一旦实验信号不满足稀疏条件时，这种方法构造的矩阵就不能实现采集少量测量数据。经过Candes和陶哲轩的研究，这一问题得到解决。他们证明得到：独立地服从同一分布的高斯随机变量形成测量矩阵可成为普适的CS测量矩阵。在理论上，这一证明完美无瑕，可是美中不足的是该测量矩阵在硬件实现上和重建算法构造上都是不实用的。2007年Candes, Romberg和陶哲轩等人建立了著名的Restricted Isometry Property（RIP）理论，成为CS的奠基性理论。该理论指出：任一矩阵只要满足约束等距特性，那么只需要满足 的采样信号就能将N维信号的K个最大值稳定地重建出来[6]。我们发现，其实RIP理论和很多数学理论很相似。比如， Johnson-Lindenstrauss定理，Kashin-Garnaev-Gluskin理论，Donoho测不准原理，等等。可是就算陶哲轩提出的RIP很完美，固定地构建满足K阶RIP且大小为 的测量矩阵 是可行的，但往往要求参数M相对较大，但是在具体的应用中，构建这样一个超多行的测量矩阵往往是不现实的。虽然困难不小，可是依然有不少学者用RIP理论指导设计出了多种确定性测量矩阵。例如，多项式测量矩阵， 分块多项式测量矩阵，广义轮换测量矩阵，等。矩阵的斯巴克特性、零空间特性和约束等距特性都可以确保重建出稀疏信号。但是很多时候，在很多情况下，更需要一种容易计算的矩阵特性来确保目标稀疏信号的重建，而矩阵的相关性正是这样的一种特性。
   要想完成将CS转为实用，那么就必须先将CS的测量矩阵在硬件上实现。在RIP理论指导下，莱斯大学R. Baraniuk教授等研制出了单像素相机和 转换器。但是，目前大多这些技术只能处理有限维度的信号。
 现在只要应用：（1）压缩感知在雷达激光中的应用，（2）压缩感知在基因检测器中的应用，（3）压缩感知在星载天文望远镜中的应用，（4）基于压缩感知的单像素相机。

压缩感知基本原理

1，压缩感知与奈奎斯特抽样定理

 如表2-1所示，压缩感知与常规的经典采样理论这个区别主要表现在如下四个方面。
（1）在常规的奈奎斯特采样框架下，对目标信号的采样是通过Sinc函数直接与目标信号的内积来完成的，而压缩感知采样系统通常利用采样矩阵或函数与目标信号乘积的方式间接获取采样值。
（2）传统的采样方法利用目标信号中最高频率两倍以上的采样率均匀的对目标信号进行采样，而压缩感知中则采用随机非均匀的采样方式。
（3）传统的抽样定理指出，在模拟信号到数字信号的转换过程中，当采样频率大于信号中最高频率的两倍时，采样后的数字信号能够完整的保留原始信号中的信息[11]。即目标信号最高频率决定采样频率，而在压缩感知的框架下，目标信号的稀疏性，决定采样个数。针对目标中包含少量非零信号的情况，由较低采样率来无失真的重建原始目标信号。所以，实质上CS理论是边采样边压缩。
（4）在常规的赖奎斯特采样框架下，信号重建是通过Sinc函数插值来完成的。由于压缩感知，并没有直接对目标信号采样，因而它需要一个利用基于最小一范数的重建步骤来恢复出原始的目标信号。
   传统抽样定理指出，为了完成抽样一定带宽的信号，至少需要一定数目抽样值。于此相比，压缩感知可以极大地降低采样个数，提高采样率，因而它比较适合用在某些探测器昂贵或测量手段耗资巨大的场合。例如，星载光学成像设备、观测天文的探测器、红外探测器。

2， 稀疏信号和可压缩信号模型
（1）稀疏性信号

   为了更精炼地表达某一信号，通常把它变化到新的框架下，当变换后零的个数远远大于之前的零的个数时，把剩下的这些少量不是零的项数定义为信号的稀疏性表达。针对一些特定的存储空间受限或传输带宽受限的情况，可以只存储或传输一些基或框架下的非零系数，而不是全部的原始冗余信号，因而这种稀疏性表达在现实生活中具有重要意义。在CS定理体系下，稀疏信号模型能够确认高倍压缩率。不用采集大量的采样值。只要预先知道目标信号在已知的基或框架下具有稀疏性表达，就可以无失真恢复原始信号。

（2）可压缩信号

3， 压缩感知数学模型

4，稀疏性表达算法

（1）标准正交基

（2）字典学习
压缩编码和字典学习的首要任务就是通过每个原子信号的稀疏表达，估计出原子信号及其权重。字典学习可以通过寻找信号中的不变量，来从许多信号中推知原子信号以及各个信号的原子信号权重。在字典学习中典型的一种算法就是奇异值分解法（singular value decomposition,SVD）,K-SVD的相应伪码如下：

5，测量矩阵的特性

   在压缩感知中有两个非常重要的问题。第一是如何设计矩阵Φ使得它在采样过程中保存信号x的有效信息；第二是如何基于测量信号y重建出目标信号x。当信号是稀疏的或可压缩的，可以通过设计大小为 的测量矩阵Φ来对原始目标信号采样，其中 ，再通过一些实际优化算法重建原始信号。[13]本文重点探讨如何设计压缩感知系统中的测量矩阵Φ，这里将先介绍测量矩阵应该具有的一些特性。

（1）零空间特性

（2）约束等距性质

（3）非相关性

6，稀疏信号重建算法

压缩感知的另一核心问题就是基于y如何重建出原始的稀疏信号x。简单描述就是已知测量值y,s为k-Sparse的稀疏信号，利用重构算法求解k尽可能小的x
一般来说，设计稀疏信号重建算法需要考虑多种因素，如以下四点。
一，  数量较少的测量值。基于相同个数的测量值，稳定地恢复出包含K个非零值的目标信号。
二，  针对测量噪声和模型噪声的鲁棒特性。无论测量值包含噪声还是测量矩阵本身的系统噪声，重建算法都需要稳定地重建出原始稀疏信号。
三，  速度。重建算法一定要高效，在占用较少计算资源的情况下，实现稀疏信号的重建。这一点非常重要。在实际的应用中，压缩感知往往需要处理多维信号，重建算法的执行效率决定了它在实际应用中的可行性。
四，  稳定性。采用一范数最小化可以确保重建的稳定性，然而在评估算法时，需要所有算法基于同样的重构条件。
大多数重建算法，考虑到了上面提出的部分或全部因素，可以宽泛的分为以下三类：基于凸优化类算法，贪婪算法，组合重建算法[15]。

（1）基于凸优化类算法

（2）贪婪算法

（3）组合重建算法

（4）信号重构质量的评价标准
本小节介绍常用的评价信号重构质量的标准。一维信号重构质量的衡量标准主要包括：信噪比，绝对误差，均方误差（MeanSquareError,MSE），相对误差，匹配度等。此外，峰值信 噪比（PeakSignaltoNoiseRatio,PSNR）对于图像而言，则是另一个重要标准。PSNR 是重构图像与原图像之间均方误差相对于信号最大值平方的对数值，该值越大表示失真越小，它是最广泛使用的评价图像质量的客观标准，本文也采用此准则来衡量重构的质量。

7，正交匹配追踪法
在本次课题中，主要采用了贪婪算法中的正交匹配跟踪算法（orthogonal matching pursuit以下简称OMP），在OMP中，残差总是和已选取的列正交，所以相同的列在OMP中不会被选中两次，因而它的最多循环次数可以明显减少。理论上来说，可以通过格拉姆-施密特正交化来生成一个正交的列集合。OMP在每次循环中，并非将残差r减去一个跟其最大相关的字典中的矢量，而是把残差r投影到与所有已选定的列线性展开的正交子空间中。

上面这个步骤不断循环，直至残余分量收敛到某一特定阈值。Tropp和Gilbert证明OMP同样可以应用于压缩感知的重建中，假设原始信号的待采样是稀疏的，同时测量矩阵中的每个元素都是从一个服从亚高斯分布的变量中随机选取的，则基于线性混叠的有限个测量值，通过OMP实现以极大的概率重建出原始的稀疏信号。这个算法最多需要K次循环即可收敛，其中K是目标信号的非零个数，缺点是在每次循环中，需要额外的正交化运算。OMP不仅保留了匹配追踪算法的元素选择准则，而且能够在每次迭代中对已选元素集合进行正交化，保证迭代结构的最优性，从而降低了运算时间[16]。
重构算法OMP算法伪代码为：


正交匹配追踪法也有一定的弊端，当重建不是特别稀疏而且规模较大的目标信号时，逐步正交匹配跟踪算法（stagewise orthogonal matching pursuit，StOMP）就是一个较好的选择。StOMP与OMP在每次循环中从字典选取一个元素不同，StOMP算法从字典中选取一个元素集合，这个集合特点是，残余分量与字典的列相关性均大于一定阈值，而后残余分量将基于这些字典中的列集合得到更新，其他步骤与OMP完全一致。

8，压缩感知的压缩过程

由图2-3我们看出传统压缩技术的过程，首先实现模拟信号到数字信号的采样，而后把这些采样数据变换到相应的变换域挖掘稀疏性，进而开展量化编码实现压缩，最后解压缩重建信号。在这个过程中首先通过A/D转换完成采样，其中含有大量的冗余数据，而后通过变换域挖掘信号的稀疏性，最后通过压缩算法实现压缩。这个过程其实造成了巨大的浪费，首先采集大量的冗余数据，然后在压缩过程再把这些冗余数据去掉。
正是由于常规压缩技术的这一弊端，现在我们主要采用压缩感知技术。模拟信号通过一特定测量矩阵，在这过程中完成了对信号的压缩和采样得到采样信号，在这个采样过程中，采样数远远低于奈奎斯特采样的个数。再将采样信号进行存储与传输。最后再通过一范数最小化的优化算法来重建出原模拟信号。
压缩感知理论压缩过程见图2-4所示：

结语

这基本是我论文的内容，后面的实验部分，利用正交匹配追踪法，采用不同测量矩阵完成一维信号、二维图像仿真实验，验证各个矩阵的性能。因为没有完成改进矩阵的实验，只是采用了六种常见测量矩阵进行实验，相当于一个验证性实验吧，我就不拿出来献丑了，如果有想看的怎么构造六种常见测量矩阵，以及一维波形和二维图像实验的详细过程就去看看我的完整论文吧，我已上传（http://download.csdn.net/detail/rookiemonkey/9919542），整个实验过程都是在MATLAB2016上完成的，代码我也已经上传了。相互参考学习一下吧！