李盈婷

（西南大学计算机与信息科学学院 软件学院，重庆 400715）

压缩感知理论及两种贪婪算法详解

李盈婷

（西南大学计算机与信息科学学院 软件学院，重庆 400715）

压缩感知理论使得采样频率与信号的内容和结构相关，在远低于Nyquist采样定理的采样频率下对数据直接进行压缩采样，为处理冗余数据做出了巨大贡献。关于压缩感知的基本理论，文章从信号的重构算法、信号的稀疏基以及信号测量矩阵的设计3个方面详细介绍。贪婪算法是重构算法中效率最高的算法，文章介绍其最开始提出的比较经典的两种算法：匹配追踪和正交匹配追踪，并详细给出了两个算法的本质思想、数学框架以及推导过程，也分析并证明了其收敛性。

压缩感知；匹配追踪；测量矩阵；正交匹配追踪

Nyquist采样定理是初始时信号处理的基本原理—它指出在采样过程中只有用大于信号最高频率两倍的频率进行采样，才能由采样所获得的信号精确重建出原信号。但是由于自然界的数据都存在局部低维结构、周期性、对称性等特点，传统的固定采样率的采样方法必然存在大量的信息冗余，便会使硬件系统所需的采样速率大大增加，而且也造成了信号带宽的浪费。2006年，由Candes，Romberg, Tao和Donoho等人提出了压缩感知理论（Compressed Sensing, CS），其核心思想就是把采样与压缩合并起来，对可稀疏表示的信号以较低的采样率进行压缩采样，并用与稀疏基不相干的测量矩阵将高维信号投影到一个低维空间上以获得测量向量（即投影值），使用了较少的测量数据但实现了信号的精确重构，达到了“少测量，巧计算”的目的。

1 压缩感知理论

感知压缩即采集较少的数据并从这些数据中解压缩出大量原始信息，其先提条件：由于恢复原信号需要足够多的对原信号的概要信息，因此采集到的少量数据中必须包含所需的全局信息，而且必须具有一种算法可以根据这些数据所包含的信息精确重建出原始信息。

1.1 信号的稀疏表示

时域内的自然信号一般都不是稀疏的，因而直接对其进行压缩采样势必会造成硬件功率的浪费，但由于在某些变换域中可以将自然信号变为可稀疏的，因此压缩感知一般先通过某种变换域得到原始信号的稀疏表示，重构时先重构出原始信号的稀疏表示逼近值，再进一步变换可得到原始信号的逼近值。设长度为N的信号X并用一组稀疏基= {,,…,}（为列向量）的线性组合来表示：

1.2 信号的测量矩阵

1.3 信号的重构算法

压缩感知理论的核心之一便是其重构算法，重构算法是指由M维的测量值y重构出长度为N(M·N)的信号X的过程，如果原始信号X满足两个条件：X是可K稀疏并且X的感知矩阵满足RIP准则时，对（2）使的逆向求解S'=y 便是待估稀疏系数，然后从测量向量Y中将信号X精确无误地恢复出来，一般通过范数求解最优化问题是解码最直接的方法：

2 贪婪算法之MP、OMP详解

2.1 MP算法

用H表示Hilbert空间，把被表示的信号设为y，其长度为n，用一组向量构成字典矩阵D，因为单位向量模为1，所以对其中的每个向量作归一化处理，即MP算法基本操作步骤如下：

选择与信号y最匹配的原子：将信号向量y与字典矩阵中每列（原子）做点乘运算，即求内积，并且选择内积绝对值最大的一列，满足如下所示，其中r0表示一个字典矩阵的列索引：

基于（4）式便可将信号y分解为两部分（最匹配原子xr0的残值和垂直投影分量），即：

将残值R1f继续进行上述步骤1）中同样的操作，经过K步分解后，信号y被分解为：

其中R0f=y，在第一次分解过程中，不难发现三个向量构成了一个直角三角形，由三角形性质可得其满足勾股定理，这个规律在后面的迭代过程中依旧满足，又因为在（6）中f与正交，由此可得出：，因此MP算法是收敛的。但由于MP迭代结果大多情况下是次优解，因此对MP算法进行改进，即OMP算法。

2.2 OMP算法

OMP算法对MP算法做了改进，虽然稍有不同，但其性能的确提高了不少，首先对分解中的每一步都将已选择的全部原子进行正交化处理，即使前面的每个分量与OMP算法的残值具有正交性，这使得在相同的精度要下，OMP收敛速度相比MP效率更高。其k阶模型如下：

同理可得k+1阶模型如下，用k+1阶模型减去k阶模型可得：

由于字典矩阵D中的原子不都是正交的，因此构建一个辅助模型来表示字典矩阵D的xrk+1项对前k个项(n=1,2,…,k) xn的依赖，如下所示：

3 结语

压缩感知是一种全新的数据采集理论，理论上要实现原始信号的精确重构，只需采集少量概要的信息便可实现原始信号的精确重构，对处理可压缩或大规模稀疏的数据作出了巨大贡献，而且即使原始信号不是稀疏的也可以将其在其他变换域中稀疏并加以压缩采样。本文从压缩感知的3个方面阐述了其基础理论，且详细介绍了重构算法中贪婪算法的其中两种算法，即MP，OMP，包括算法的公式推导证明等。这两个算法都采用一次解出一个（或多个）待重建信号的构成要素，然后使用迭代的方式找出需重建信号的元素。

[1]杨真真，杨震，孙林慧.信号压缩重构的正交匹配追踪类算法综述[J].信号处理，2013（4）：486-496.

[2]BARANΙUK R.Compressive sensing[C].Conference on Ιnformation Sciences & Systems, 2008（4）：iv-v.

[3]方红，杨海蓉.贪婪算法与压缩感知理论[J].Acta Automatica Sinica，2011（12）：1413-1421.

[4]卢雁，吴盛教，赵文强.压缩感知理论综述[J].计算机与数字工程，2012（8）：12-14.

[5]尹宏鹏，刘兆栋，柴毅，等.压缩感知综述[J].控制与决策，2013（10）：1441-1445.

Theory of compressed perception theory and two greedy algorithms

Li Yingting
（Software Engineering College of Computer and Ιnformation Science College in Southwest University, Chongqing 400715, China）

The compression perception theory makes the sampling frequency directly related to the content and structure of the signal. Ιt compresses the data directly at the sampling frequency far below the Nyquist sampling theorem, making a great contribution to the processing of redundant data. The basic theory of compression perception is introduced in details from three aspects: signal reconstruction algorithm, signal sparse base and signal measurement matrix design. Greedy algorithm is the highest in the reconstruction algorithm efficiency of the algorithm. This paper has introduced two classic algorithms proposed at the beginning: matching pursuit and orthogonal matching pursuit, given a detailed description of the nature, mathematical framework and derivation process of two algorithms, as well as analyzed and proved its convergence.

compressed sensing; matching pursuit; measurement matrix; orthogonal matching pursuit

李盈婷（1996— ），女，甘肃古浪。