变比例的稀疏度自适应匹配追踪算法*

唐川雁，史姣姣

（杭州电子科技大学 通信工程学院，浙江 杭州 310018）

0 引 言

压缩感知（Compressed Sensing，CS）[1]理论与奈奎斯特定理相比，最大的优势是减少了采样数据，同时完成采样和压缩，有效降低了资源消耗与信号处理成本。压缩感知已广泛应用于多个领域，如信道估计[2]、人脸识别[3]、图像处理[4]、医学应用[5]等。

重构算法作为CS的重要部分，解决的是从低维测量值中恢复出原始高维信号的问题。重构算法大致可分为三类：凸优化算法、贪婪迭代算法和组合优化算法。其中贪婪类算法计算复杂度较低，算法结构简单易于实现，并且重构效果好，是在实际中应用较多的一类算法，如正交匹配追踪（Orthogonal Matching Pursuit，OMP）算法[6]、压缩采样匹配追踪（Compressive Sampling Matching Pursuit，CoSaMP）算 法[7]和 子 空 间 追 踪（Subspace Pursuit，SP）算法[8]等。虽然这些算法都能实现原始信号的准确重构，但前提条件是需要预知信号稀疏度。事实上，信号稀疏度通常是未知的，这使得上述算法的应用范围比较受限。为解决未知稀疏度类信号的重构问题，Thong T D，Gan Lu等学者[9]提出了稀疏度自适应匹配追踪（Sparsity Adaptive Matching Pursuit，SAMP）算法。SAMP算法不需输入稀疏度，在实际应用中有巨大优势，因此近年来众多学者对SAMP算法进行研究和改进，如文献[10]结合原子匹配测试、正则化和回溯思想及变步长选择原子的方法，在不需要预知稀疏度的情况下，能够准确重构原始信号，且与同类算法相比迭代次数和重构时间更少，性能更优，不足的是该算法稀疏度估计值与真实值相比在大稀疏度时误差较大。文献[11]提出一种稀疏度估计方法来避免稀疏度的过估计，以及在不同阶段根据测量值与估计信号的能量比值调整步长，实现了未知稀疏度类信号的精确重构，但其稀疏度估计方法在约束等距常数增大时误差也增大。Qiu S等人[12]提出基于SAMP的步长优化算法，该算法针对SAMP算法随迭代次数的增加步长也只能增加的缺点，根据当前残差与上一次迭代残差的差值改变步长，若该差值满足设定的条件则计数，当达到3次则减少步长，否则继续计数直到满足迭代停止条件，该算法虽然能减少重构时间，但在重构成功率上改善并不明显。

研究发现现有的SAMP改进算法重构成功率还有提高空间，因此从原子选取方式出发，提出了变比例的稀疏度自适应匹配追踪（Sparsity Adaptive Matching Pursuit with Variable Proportion，VP-SAMP）算法。该算法对SAMP算法的原子预选方法进行改进，以内积累加比例准则筛选原子，并采用变比例策略在大稀疏度时提高重构成功率。

1 压缩感知理论

CS理论表明，若信号是稀疏的或可压缩的，则可通过测量矩阵与该信号相乘得到少量观测值，实现信号的降维处理，最后再利用相关算法求解最优化的非线性问题从样点中恢复原始信号。

设x是RN空间中一个长度为N的离散信号，可看作是一个列向量，现假设有一组维度同为N×1的基函数ψi(i=1,2,…,N)，则可用ψi的线性组合来表示x，令Ψ=[ψ1,ψ2,…,ψN]，则x可以表示为：

式（1）中Ψ为N×N的正交基矩阵，称为变换基（稀疏基），α称为加权系数向量，且可表示为α=Ψ-1x，因此加权系数在Ψ域（即以Ψ为基的变换域，简称Ψ域）的表示等同于信号在时域的表示，是同一个信号的等价表示。如果α中仅存在K(K<

在信号经过稀疏表示后，即可设计一个测量矩阵Φ(M×N,M

式（2）中，D=Φ·Ψ为M×N维的传感矩阵。由于N远大于M，所以求解式（2）就是一个NP难题[13]。然而式（2）中α只有K个非零值，满足K

2 变比例的稀疏度自适应匹配追踪算法

SAMP算法在稀疏度未知的情况下也能重构原始信号，是贪婪类算法的重要突破。SAMP的基本思想是：在迭代开始时，初始化步长为一个较小的值，采用分阶段思想逐步扩大步长，随着迭代次数的增加，当残差的值比上一次残差为非递减时增加步长，逐步向信号的真实稀疏度逼近。SAMP在原子预选时，每次选择当前步长大小的原子个数。随着阶段的增加步长也会变大，当稀疏度较大时，在迭代后期每次从内积中选取的原子数很多，可能导致大量的误选，使得重构成功率下降较多甚至重构失败。

针对上述SAMP原子选取的问题，提出了变比例的稀疏度自适应匹配追踪（VP-SAMP）算法。该算法预选集选取的原子个数不再依赖于当前步长，而是通过一个变化阈值β进行控制。在每次迭代时，将占内积总和比例较大的部分对应原子选出，这个比例就是阈值β，同时当匹配追踪的稀疏度增大时，β也进行增大。预选集选取原子的个数由当前内积数值的分布情况确定，内积中存在较大的值时，选取的原子个数较少；内积中的值分布较平均时，选取的原子个数变多，所以β不变时，每次选取的原子个数也是自适应变化的。下面通过内积累加比例选取准则和变比例策略两方面来对VP-SAMP算法进行描述。

2.1 内积累加比例选取准则

对残差与测量矩阵的内积的绝对值分布进行了研究，发现内积中只有少数值比较大，这些值包含了内积中较大比例的能量，使用这些原子便能够大概率重构信号。输入信号为长度N=256的随机信号，其稀疏度K=20，测量矩阵为64×256的高斯矩阵，以上述实验条件进行重构中的内积计算，得到第二次迭代时内积的绝对值大小分布情况如图1所示。

图1 信号测量降序排列结果

由图1可见，将第二次迭代得到的测量矩阵与残差的内积的绝对值降序排列后，只有小部分的值较大，其余的大部分值较小。根据降序排列得到的结果，对前n个值进行累加，当累加的和占内积的总和比例超过β时，由这n个原子组成该次迭代预选集中的原子。如式（4）所示。

式（4）中，u为当前迭代计算的内积，rt-1表示第t次迭代的残差，Φ是测量矩阵，sort(·)表示按照从大到小的顺序进行排序，sum·)表示求和。通过式（4）即可进行初次原子筛选，称之为VP-SAMP算法的内积累加比例选取准则。利用该原子选取准则选择的原子数根据内积值的大小分布自适应变化，不会因为步长随阶段数的增加而增加导致预选时选择的原子数越来越多，从而导致预选浪费甚至原子误选，降低信号重构成功率。

2.2 变比例策略

基于内积累加比例准则的阈值法筛选原子时，阈值β取值是固定的。在重构某个原始信号的过程中，每次迭代时将占内积总和固定比例的值较大的部分对应原子选出，虽然每次选取的原子个数是自适应变化的，但在迭代开始阶段，估计稀疏度与真实的稀疏度相差较大，因此应在开始阶段选择较少的原子，可以减少回溯的时间；在迭代后期，支撑集中的原子越来越多，接近真实支撑集大小，此时应在时间允许的范围内，增加阈值β，使得满足式（4）的原子更多，从而可以选出更多的原子参与重构，以此提高大稀疏度条件下的重构成功率。在迭代开始前，设置阈值β的初始值和最大值分别为β0和βmax，当满足设定的阈值改变条件时，按照式（5）增加β：

通过上述阈值调整策略，选取原子的方式更加合理，在前期迭代阶段，估计稀疏度较小时可以减少重构时间，在稀疏度较大时可以提高重构成功率，可在不同稀疏度下达到重构成功率和重构时间两种性能的平衡。

2.3 VP-SAMP算法步骤

VP-SAMP算法的主要思想是：设置阈值β的初始值和最大值，通过基于内积累加比例的阈值法选取预选集，同时在迭代过程中，根据设定的阈值改变条件增加阈值，以此提高大稀疏度条件下的信号重构成功率性能。VP-SAMP算法的具体步骤如下。

输入：测量矩阵Φ，测量值y，初始步长s；

初始化：残差r0=y，支撑集初始支撑集大小L=s，迭代次数t=1；

（1）计算u=〈rt-1,Φ〉，选择满足式（4）的所有原子，并将对应的索引值放入预选集J1中；

（2）得到候选集：C=F∪J1；

（5）如果||r||2≤10-6，则停止迭代，得到最后的结果否则转步骤（6）；

（6）如果||r||2≥||rt-1||2，更新支撑集长度为L=L+s，若β<βmax，则β=β+β0，转步骤（1）；否则更新支撑集Ft=F，更新残差rt=r，更新迭代次数t=t+1转步骤（1）进入下一阶段；

输出：信号的稀疏近似x^。

3 实验结果

以下实验均在Windows 10系统，MATLAB R2014a环境中进行的。实验时针对单种算法单个参数重复实验500次，当重构误差小于10-6即认为重构成功，统计其中的重构成功次数即为重构成功率，统计其中重构成功的平均误差即为重构误差，统计其中重构成功的平均时间即为重构时间。

3.1 内积累加比例选取准则的有效性

式（4）中参数β的取值范围是[0,1]，为了研究β取值对性能的影响，先设定β0=0，βmax=1进行不同β下的实验分析，得到VP-SAMP算法中β对性能影响实验结果。实验时选择高斯信号作为原始信号，长度为N=256，测量矩阵为128×256的高斯随机矩阵，稀疏度K取值为42～60，每隔3取一次值，步长s取值为3。β取值为0.1～0.6，每隔0.1取一次值，得出不同β值下重构成功率和重构时间随稀疏度的变化情况，如图2所示。

图2 不同β值对VP-SAMP算法性能影响

由图2可知，在同一稀疏度下，β值越大，重构成功率越高，但所用的重构时间也越多。当稀疏度较小时，基于小β值进行原子预选便能得到较好的重构效果，同时重构时间也较少；当稀疏度较大时，需要更多的原子参与重构，在时间允许的情况下，应选取大的β值进行原子预选才能得到较好的重构效果。这表明理论分析与实验结果相一致。按照图2的实验结果，综合考虑重构成功率和重构时间两方面的性能，选定VP-SAMP算法中β0=0.1，βmax=0.6，按照此参数进行VP-SAMP与SAMP算法的性能分析实验。

3.2 VP-SAMP与SAMP重构效果比较

实验比较SAMP和所提VP-SAMP算法的性能，分别从重构成功率、重构误差和重构时间三方面进行对比。实验时两种算法步长s取值均为2，3，4，可得不同步长下的VP-SAMP算法和SAMP算法的重构成功率、重构误差和重构时间随稀疏度的变化曲线如图3所示。

图3 VP-SAMP算法与SAMP性能对比

由图3可得，VP-SAMP算法与SAMP算法相比，重构成功率明显更高。在稀疏度超过65之后，SAMP算法的成功率三种步长下均为0，因此在重构误差和重构时间图中，SAMP算法在稀疏度超过65之后没有数据；而VP-SAMP则成功率在20%到70%之间，并且重构误差和重构时间较更小稀疏度情况下没有剧烈增加，依然保持在同个数量级水平，充分说明了VP-SAMP算法在大稀疏度下的重构成功率优于SAMP算法。考虑到稀疏度大于65之后SAMP算法重构成功率为0，因此只统计稀疏度为56到62之间的两种算法各步长下的平均重构成功率统计如表1所示。

表1 稀疏度为56到62之间的平均重构成功率

从表1明显可见VP-SAMP算法的平均重构成功率高于SAMP算法，且图3表明稀疏度继续增加时，SAMP算法成功率迅速降低为0，而VP-SAMP下降速度更慢，依然保持一定成功率。

重构误差方面，当K<65时两种算法基本相当，当K＞65时，SAMP成功率为零，重构误差非常大，VP-SAMP算法虽然重构误差增大，但是依然保持在10-13数量级。因此认为两种算法在重构误差方面性能基本一致。

从表1可见SAMP算法s=2时的重构成功率低于VP-SAMP算法在s=4时的重构成功率，而结合重构时间性能来看，同等初始步长下，VP-SAMP算法重构时间高于SAMP算法，但是从图3的重构时间曲线中可以看出，VP-SAMP算法s=3时的重构时间和SAMP算法s=2时的重构时间基本一致，因此可以结合表1和图3比较两种算法在时间一致情况下的重构成功率。从表1可知，SAMP算法s=2时的重构成功率为84.88%，而VP-SAMP算法s=3时的重构成功率为90.72%，提升5.84%。说明在重构时间和重构误差一致的情况下，VP-SAMP算法有着比SAMP更高的重构成功率，充分说明了本文所提VP-SAMP算法在大稀疏度下的重构成功率方面具有较大性能提升。

4 结 语

针对SAMP算法每次选择当前步长值个原子加入预选集会导致预选浪费甚至误选的问题，提出变比例的稀疏度自适应匹配追踪（VP-SAMP）算法，该算法以内积累加比例准则选择预选集，并采用变阈值策略来控制不同迭代阶段预选集选取原子的数量，保证大稀疏度情况下的较高重构成功率同时减少小稀疏度情况下的运行时间。仿真实验表明，VP-SAMP算法在重构成功率和重构误差两方面与SAMP算法相比一致的情况下，在大稀疏度时重构成功率可平均提高5.84%。