基于稀疏度自适应算法的压缩感知

王红亮，卢振国，王 帅，曹京胜，吕云飞

(中北大学电子测试技术重点实验室，山西 太原 030051)

基于稀疏度自适应算法的压缩感知

王红亮，卢振国，王 帅，曹京胜，吕云飞

(中北大学电子测试技术重点实验室，山西太原030051)

针对目前压缩感知的重构算法需预知信号稀疏度和重构时间较长的问题，提出基于稀疏度自适应算法的压缩感知，该方法基于分段和回溯思想，通过增大步长、合并上次原子来选择最匹配原子，能显著减小计算复杂度，从而减少信号重构时间。以语音信号为处理对象，对SAMP算法进行了仿真比较，仿真结果表明，在未知信号稀疏度的情况下，与基追踪(BP)算法和正交匹配追踪(OMP)算法比较，SAMP算法的重构信号运行时间明显降低，并且在不同的信号压缩比的条件下重构信号性能得以保证，验证了SAMP算法在稀疏度方面的自适应性以及重构效率高等优点。

压缩感知；稀疏度自适应算法；重构时间

0 引言

近年，Donoho、Candès、Romberg和Tao提出了新的信号压缩采样理论——压缩感知[1-4](Compressive Sensing，CS)，以低于奈奎斯特采样率的速度对信号进行采样。CS主要内容是将稀疏信号通过观测矩阵从高阶矩阵线性投影为低阶，最后高概率精确地重建原信号。这种新型的采样方式避免了传统香农采样先采样再丢弃的缺点，同时降低了采样率，缩减了存储数据，从而有效地减少了传输和存储设备的使用量。所以压缩感知提出后在光学成像[5]、雷达探测[6]和语音信号处理[7-9]等众多领域都有相关的研究。

重建算法作为压缩感知过程中的一个至关重要的环节，其主要目的是要实现从现有的低维数据中最大限度地恢复出原始的高维数据。重构算法的选择应遵循使用较少的观测值，并且能精确和快速地恢复原信号等原则。目前，重构算法有两大类应用较为广泛：松弛法[10-11]、贪婪算法[12-13]。松弛法中应用较广泛的有基追踪(Basic Pursuit，BP)算法，具有重构信号的质量较好，需要观测的个数较少的特点，但计算复杂度较高，恢复信号时间较长，而贪婪算法中具有代表性的正交匹配追踪(Orthogonal Matching Pursuit，OMP)算法需要将原始信号内的N个元素逐一恢复，而且每次重构时恢复数据的计算存在误差，同时需要较多的观测次数，重构信号的质量也相对较低。

压缩感知理论可以将信号通过观测矩阵从高阶矩阵投影到低阶，最后高概率恢复出原信号，解决了香农-奈奎斯特采样定理在信号采集中的不足，同时还具有低采样率和重构质量高等优点。压缩感知对信号是非自适应性采样，只能将可稀疏的信号随机观测得到压缩值，虽然压缩不同类型语音信号或者图像信号考虑了选取合适稀疏矩阵和重构算法，但仅仅针对某一类信号，而不是根据采样信号本身的特征自适应的压缩和重构，所以根据信号自身特征引入自适应稀疏算法是目前压缩感知研究的难点和热点。本文针对目前重构算法均存在需预先确定信号稀疏度，恢复时间较长等缺陷，采用稀疏自适应匹配追踪算法(Sparse Adaptive Matching Pursuit，SAMP)[14]实现重构原始信号，与其他重构算法相比较，SAMP算法具有在未知稀疏度的情况下高概率的恢复原信号，同时重构信号的时间显著减少等优点。

1 压缩感知理论

压缩感知理论的主要过程：首先判断信号本身或者在某个域是否稀疏(或可压缩)，如果稀疏再通过观测矩阵使信号从高阶矩阵线性投影变为低阶，信号的采集和压缩在此过程同时进行，最后通过恢复算法高概率精确地重建原始信号。压缩感知的理论包含三个内容：选择信号稀疏基，设计观测矩阵和重构原信号。其中信号是否具有稀疏性是前提条件；观测矩阵的设计是重要的组成部分，它的设计不仅关系到压缩和采样速率的快慢，而且影响重构信号的质量；重构原始信号是其核心部分，因此，重构算法是否合适决定恢复原信号质量的好坏。压缩感知实现需要满足一些条件：信号在某个变换域是可稀疏，稀疏矩阵和观测矩阵尽量不相干，感知矩阵满足RIP准则等。

根据以上条件可以建立如下算法数学模型：

假定有限实值离散空间为RN，其中Ψi(i=1,2,…,N)是RN的基向量，则长度为N的原始信号x可表示为：

(1)

式(1)中，Ψ=[Φ1,Φ2,…,ΦN]，Ψ是由基向量Φ1构成的N×N正交矩阵，矩阵s是信号x在Ψ域的稀疏后的矩阵。

然后采用与Ψ相干性较小的观测矩阵Φ(M×N,M≪N)对信号进行线性投影，得到观测值y：

y=Φx

(2)

观测值y是M阶列矩阵，注意：在此过程中观测值y不是原信号的采样值，而是信号x在观测矩阵Φ上的投影值。由于信号x是可稀疏矩阵，所以式(2)可以表示为：

y=Φx=ΦΨs=Θs

(3)

式(3)中，Θ(M×N矩阵)为感知矩阵。

从观测值y准确地恢复原始信号x最直接的方法是转化为L0范数的最优化问题：

(4)

但直接求式的解是个NP-hard问题[15]。Donoho认为最优化问题与信号稀疏分解两者有共同点，所以最优化问题的求解途径可以从信号稀疏分解相关理论中寻找，证明最小L0范数下在一定条件下和最小L1范数具有等价性找到最稀疏的解。所以，式(4)可转化为L1最小范数下的最优化问题：

(5)

2 恢复算法

2.1 正交匹配追踪法

OMP算法延续了匹配追踪算法中原子的选择准则，主要过程：从感知矩阵Θ中选择与余量(观测值的残差)相乘的最大值的列矩阵，再利用最小二乘法得到最匹配的原子，循环直至逼近原信号，实现了递归地对已选原子集合进行正交化以保证迭代的最优性，从而减少了迭代次数。

下面简单叙述OMP算法：

输入条件：感知矩阵Θ，观测值y，稀疏度k；

输出：x的k稀疏信号s的逼近sr，重构误差r；

初始化：余量r0=y，重建信号s0=0，索引集Γn=Γn-1∪{k}，迭代次数n=0；

步骤1：计算余量和感知矩阵Θ的每一列的内积gn=ΘTrn-1；

步骤 2：找出gn中元素最大的元素

j=argmax|gn[i]|；

步骤 3：更新索引集Γn=Γn-1∪{j}及原子集合Θrn=Θrn-1{θj}；

步骤 4：使用最小二乘法求得近似解

步骤5：更新余量rn=y-Θsn；

步骤6：判断是否满足收敛条件，满足则停止sr=sn，r=rn输出sr，sn，否则转步骤1。

OMP算法保证了每次迭代的最优性，减少了迭代的次数，易于实现。但需要预先知道信号的稀疏度K才能进行重构，在每次迭代中仅选取一个原子来更新新原子集，并且迭代的次数与稀疏度K和采样个数M密切相关，随着迭代次数的增大，这样必然会造成重构时间增大，并且重构时每次恢复都有微小误差。

2.2 基于SAMP算法的压缩感知

稀疏自适应匹配追踪算法是基于OMP算法基础上提出的，SAMP算法的主要思路是：在未知稀疏度K的情况下进行信号重构，利用逐步加大步长的方法不断增加所用的原子规模，并引入回溯思想，在每次加大步长和选择原子后，都会与上一步的原子进行合并，最后从中选择最佳的匹配原子。与其它贪婪算法相比，SAMP算法中回溯思想引入，使得在稀疏度K未知的前提下能够自适应重构原信号，显著提高了算法精度并减少了信号恢复时间。

SAMP算法实现步骤如下：

输入条件：观测值y，观测矩阵Φ，步长增量L；

初始化：余量r0=y，支撑集量F0=Φ,步长Γ=L,阶段内初始迭代次数i=1，步长增量的初始倍数j=1；

步骤1：求解感知矩阵Θ和残差余量内积p=|Φ·rn-1|,取绝对值最大的Γ个数据，将相应的感知矩阵Θ的列矩阵与候选集Wi合并；

步骤2：将支撑集Fi-1和候选集Wi合并，得到候选集Ci，

Ci=Fi-1∪Wi；

同时选择最大的Γ个元素的列矩阵，合并成新支撑集F；

步骤4：通过观测值y和支撑集F，计算余量r:

和OMP算法需预知稀疏度K不同，SAMP算法中阶段思想和回溯思想的引入,通过阶段与阶段间的累加来不断增大支撑集的大小，同时不断更新支撑集，实现了在稀疏度K未知的前提下能够自适应重构原信号的目的。SAMP算法通过将迭代过程分为多个阶段，在每个阶段中信号重建所需的支撑集的大小不发生改变，通过选取感知矩阵和余量的内积中最大的一些值形成候选集，在经过循环从候选集中选择支撑集中的原子，所以初始步长的确定就成为该算法的重建时间和重建质量的关键因素。

在SAMP算法中，特定的步长有不同的恢复效果，若步长Γ=1时，支撑集的大小可以达到稀疏度的大小，但对于大规模信号，重建时间将会很长。若步长Γ过大时，重建时间将会减少，但支撑集的大小很有可能会超越K，导致重建效果变差。因此，重建信号需要在重建时间和效果中取得平衡，根据信号和压缩比对步长进行合理的选择。

3 实验仿真及分析

本章节选用语音信号作为仿真对象，通过仿真证明SAMP算法与OMP、BP算法相比在信号恢复质量和信号重构时间上的优势。仿真实验将SAMP算法引入压缩感知，稀疏基选用冗余字典(K-SVD)算法，观测矩阵则是以随机高斯矩阵为基础，根据每帧语音信号能量的大小，自适应分配观测的个数，采用SAMP 算法重构恢复语音信号。

首先选用一段女生声音内容为“hello，酷狗”，共有44 100个样点，采样率为22.05 kHz。为了说明SAMP算法的重建效果，三种重构算法对语音信号均采用相同的预处理方法，进而重构语音信号。SAMP采用初始步长Γ=10，迭代停止条件ε=0.000 2，帧长取160，240，320，400，480，信号压缩比值取0.3，0.4，0.5，0.6。

3.1 信号评价方法

1)评价语音信号的客观方法

衡量一段语音信号恢复质量，一般采用平均帧信噪比(AFSNR，Average Frame Signal to Noise Ratio)和相对误差进行客观评价，其中 AFSNR 越大则说明重构信号质量越好，反之，重构信号越差。定义如下：

(6)

式(6)中，N是语音信号的总帧数。

2)评价语音信号的主观方法

MOS(Mean Opinion Score)值一般作为评价语音信号的主观方法，本文采用 ITU P.862的 PESQ 程序对语音信号和重构信号的对比来得到 MOS值，实现主观质量的客观评价

3.2 仿真结果

三种算法重构信号的AFSNR和MOS值如表1和表2中所示。根据表中数据分析可知：语音信号的帧长和压缩比值都对重构信号的AFSNR有影响，当帧长固定时，信号压缩比值越大，重构信号的AFSNR越大，说明重构语音的质量越高；当信号压缩比值不变时，语音的帧的样点越多，重构信号的AFSNR越大，表示恢复语音信号的质量越好，当帧长为400，压缩比值为0.6时，重构信号的质量达到最好。三种算法重构信号的质量性能相比较结果如图1所，在相同帧长和压缩比值的情况下，SAMP算法重构的语音质量稍好于BP算法，相对优于OMP算法。

表1 OMP，BP和SAMP算法的平均帧重构信噪比

表2 OMP，BP和SAMP算法重构信号的MOS值

以重构语音时间的角度评判，运行观测矩阵大概只需要1 s左右，剩余全部都是重构信号所用时间。从实验数据中不难发现，SAMP算法的重构时间都在10 s以内，但OMP算法最少时间的是10 s，而随着压缩比的增大，重构语音所需要的时间成倍增加，最高达到400 s，BP算法的时间重构更长，最小的是40 s，最高2 500 s，这么长的时间恢复一段语音信号是难以想象的。如图2所示，在相同帧长和信号压缩比值的条件下，OMP算法的重构时间是SAMP算法的15倍左右，而BP算法是SAMP算法的几百倍，所以使用SAMP算法会显著减少压缩感知重构语音信号的时间。

OMP算法虽然保证了每次迭代的最优性，减少了迭代的次数，但缺点是：需要预先知道信号的稀疏度K才能进行重构，在恢复过程中将原信号N个元素逐一恢复从而使得观测次数较多，并且重构时每次恢复都有微小误差，重构信号的质量比BP算法要低，但BP算法优化信号较为复杂，需要恢复信号的时间较长。SAMP算法与OMP算法有所不同，每次都选择原子更新原信号重构所需要的支撑集，并且利用回溯思想将所选原子和上次的支撑集进行合并，从而得到候选集，最后筛选出新的支撑集，SAMP是在自适应的基础上引入回溯思想，使它的恢复精度高于OMP算法。

4 结论

本文提出了基于稀疏度自适应算法的压缩感知，该方法在未知稀疏度K的情况下进行信号重构，基于分段和回溯思想，通过增大步长、合并上次原子来选择最匹配原子，能显著减小计算复杂度，从而减少信号重构时间。仿真结果表明，在未知信号稀疏度的情况下，与基追踪(BP)算法和正交匹配追踪(OMP)算法比较，SAMP算法的重构信号运行时间明显降低，并且在不同的信号压缩比的条件下重构信号性能得以保证， 验证了SAMP算法在稀疏度方面的自适应性以及重构效率高等优点。

[1]David L Donoho. Compressed sensing[J]. IEEE Transactions on Information Theory, 2006, 52(4):1289-1306.

[2]E Candès, M Wakin. An introduction to compressive sampling[J]. IEEE Signal Processing Magazine,2008,25(2):21-30

[3]Donoho David L, Tsaig Y. Extensions of compressed sensing[J]. Signal Processing, 2006,86(3):533-548.

[4]Candès E, Romberg J, Tao Terence. Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information[J]. IEEE Transactions on Information Theory, 2006,52(2):489-509.

[5]Lustig M, Donoho D, Pauly J M. Sparse MRI: The application of compressed sensing for rapid MR imaging[J]. Magnetic Resonance in Medicine, 2007, 58(6): 1182-1195.

[6]Duarte M F, Davenport M A, Takhar D, et al. Single-pixel imaging via compressive sampling[J]. IEEE Signal Processing Magazine, 2008, 25(2): 83-91.

[7]Michal A, Elad M, Alfred B. K-SVD: An algorithm for designing over-complete dictionaries for sparse representation[J]. IEEE Transactions on Signal Processing, 2006, 54(11):4311-4322.

[8]周小星,王安娜,孙红英,等.基于压缩感知过程的语音增强[J]. 清华大学学报(自然科学版),2011,51(9):1234-1238.

[9]Griffin A, Hirvonen T, Tzagkarakis C, et al. Single-channel and Multi-channel sinusoidal audio coding using compressed sensing[J]. IEEE Transactions on Audio Speech and Language Processing, 2011,19(5):1382 - 1395.

[10]Donoho David. For most large underdetermined systems of linear equations, the minimal ell-1 norm solution is also the sparsest solution[J]. Communications on Pure and Applied Mathematics, 2006,59(6): 797-829.

[11]Malioutov D M, Cetin M, Willsky A S. Homotopy continuation for sparse signal representation[C]//IEEE International Conference on Acoustics, Speech, and Signal Processing.Philadelphia, USA: IEEE Press,2005:733-736.

[12]Needell D, Vershynin R. Uniform uncertainty principle and signal recovery via regularized orthogonal matching pursuit[J]. Foundations of Comp. Math,2000,9(3):317-334.

[13]Needell D, Tropp J. Cosamp: Iterative signal recovery from incomplete and inaccurate samples [J]. Applied and Comput. Harmon. Anal. 2009,26(3):301-321.

[14]焦李成,杨淑媛,刘芳,等.压缩感知回顾与展望[J].电子学报，2011,39(7):1651-1662.

[15]Thong T Do, Lu Gan, Nam Nguyen, et al. Sparsity adaptive matching pursuit algorithm for practical compressed sensing [C]//Asilomar Conference on Signals, Systems and Computers. Pacific Grove, California, 2008.

AdaptiveAlgorithmforSparsityCompressiveSensing

WANG Hongliang, LU Zhenguo, WANG Shuai, CAO Jingsheng, LÜ Yunfei

(Key Laboratory of Instrumentation Science & Dynamic Measurement North University of China, Taiyuan 030051, China)

The current compressive sensing needs signal sparsity in advance and the reconstruct process sustained over long time.To solve the problem, a sparsity adaptive algorithm(SAMP) was put forward in this paper.The method was based on segmentation and retrospective thinking. By increasing step and merging last atom to select the best match, this algorithm could significantly reduce the computational complexity, thereby reduced the time signal reconstruction. The speech signal was processed in comparison with SAMP algorithm simulation. Simulation results showed that, in the case of unknown signals sparsity, the reconstructed signal quality of SAMP algorithm reduced the reconstruction time evidently comparing with the base pursuit(BP) algorithm and the orthogonal matching pursuit(OMP) algorithm. At the same time, the reconstructed signal quality of SAMP had a good performance under different signal compression ratio.

compressive sensing; sparsity adaptive algorithm; reconstruction time

2017-04-25

王红亮(1978—)，男，河南林州人，副教授，研究方向：测试系统集成，目标检测与识别，应用软件开发，超声成像。E-mail:nucwanghongliang@163.com。

TP391.41

A

1008-1194(2017)05-0040-05