改进的稀疏度自适应多路径匹配追踪算法

2021-12-26吴梦行伍飞云杨坤德田天

哈尔滨工程大学学报 2021年11期

吴梦行，伍飞云，杨坤德，田天

(1.杭州应用声学研究所声纳技术重点实验室，浙江杭州 310023； 2.西北工业大学航海学院，陕西西安 710072)

压缩感知(compressed sensing, CS)在过去的十几年中，由于其在图像和音频处理[1]、视觉跟踪[2-4]、以及计算机视觉和水声信道估计[5-8]等多个领域的巨大潜在应用价值，受到了越来越多的关注。

结合测量矩阵和压缩的信号对原始信号进行恢复是压缩感知最重要的部分之一，其可以对采样不足的信号进行充分的重构，突破了传统的香农奈奎斯特采样定理，实现了可接受的准确性和复杂度。常用的重构算法主要包括凸优化算法和贪婪迭代算法[9]。其中，贪婪算法以其兼顾重构质量和运行效率的优势，受到越来越多的关注。匹配追踪算法(matching pursuit)是最典型的贪婪算法之一，其特点是根据传感矩阵与残差值相关性的强弱，挑选最为匹配的原子扩充支撑集，其重构速度快且有较好的重构质量。其改进算法还包括OMP (orthogonal MP)[10]、ROMP (regularized OMP)[11]、 StOMP (stagewise OMP)[12]等算法。然而，挑选的原子被选入支撑集后，将在整个迭代过程中保留，无法判断和更新错选的原子，影响了支撑集的准确性，且相关性判据有待改进。为此，出现的CoSaMP算法 (compressive sampling MP)[13]和SP算法(subspace pursuit)[14]算法通过回溯步骤剔除相关性较低的原子，获得更精确的支持集，但是重构效果受到支撑集原子选择方式缺乏灵活性的约束。为了满足在未知稀疏度K的情况下获得更好的跟踪和重建性能，SAMP (sparsity adaptive MP)等算法对匹配跟踪算法进行了大量的改进[15-18]。这类稀疏度自适应算法的核心是利用一个固定步长多次迭代不断逼近，达到事先不需要知道稀疏度就能准确估计真实的稀疏度K的目的。

在满足稀疏性条件的前提下，MMP算法[19]从多个候选支撑集中选择最优方案，显然多路径搜索比单路径搜索有更好的性能。但由于MMP计算量大，在没有稀疏信息的情况下很难求解大规模问题。因此对MMP算法进行优化具有重要的意义。本文在MMP算法基础上提出了一种改进的快速稀疏度自适应多路径匹配追踪算法(improved multipath matching pursuit algorithm with sparsity adaptive, IMMP)。与传统算法相比，IMMP算法具有明显的重构精度和时间优势。

1 压缩感知与多路径匹配追踪算法

1.1 压缩感知理论

由CS理论可知，将一个K-稀疏或在某一稀疏域能稀疏表示的N维离散数字信号通过某一个测量矩阵进行有效压缩，我们就能够在线性变换下通过得到少量的观测值精确重构原始信号[10]。信号x中除了只有K个非零值外其余N-K个值均为零，且K远小于N。采样和压缩过程可以描述为：

y=Φx

(1)

式中：Φ是大小为M×N的测量矩阵，观测值y的长度为M且满足M≪N。压缩感知理论的目标是基于观测值y和测量矩阵Φ将重构问题转换为求具有稀疏约束的l0范数的最优解问题。其求l0范数最优解模型为：

(2)

式中 ‖x‖0为x的l0范数。如果在某一变换域中使信号x满足稀疏条件，称此变换域为x的稀疏域，在此稀疏域中，信号可以稀疏表示为：

x=Ψθ

(3)

式中：Ψ=[ψ1ψ2…ψN]为稀疏基矩阵;θ为在稀疏基矩阵Ψ下的K稀疏信号矩阵。理论表明，求解最小l0范数是一个NP-hard问题[20]，而且求解最小l0范数可以转化为求解最小l1范数[11]，即最小l1范数优化问题：

(4)

1.2 MMP算法

MMP算法通过将搜索最优路径建模成基于树的路径搜索问题，每次迭代依据测量矩阵与残差的相关性来更新一个支撑集原子，通过贪婪迭代搜索多个路径，每个路径经K次迭代后得到一个含K个原子的支撑集，最终达到选择最优路径即最优支撑集的目的。在多路径搜索中，当前第k层分支节点原子通过计算第k-1层分支节点的残差rk-1与测量矩阵Φ的内积确定：

Γ=arg max|〈Φ,rk-1〉|

(5)

(6)

(7)

(8)

伪逆矩阵为：

(9)

在MMP算法中，分支原子选择的优先级由式(10)决定，其中Cl=[c1c2…cK]，优先级函数layer_Order是其算法实现过程:

(10)

式中：ck与当前k层分支原子的选择相关;d表示当前原子节点的子路径数。Cl给予MMP搜索的第l条路径每个节点原子被选择的优先级，直至残差值满足一定停止迭代阈值ε1或达到最大搜索路径数LMAX时停止搜索。

layer_Order函数的实现步骤如下：

1) 输入当前路径次序当前路径次序l，子路径d，稀疏度K，初始值j=1,p=l-1并计算余数cj=mod(p,d)。

2) 计算p除以d的商并赋值给p，如果j≤K,更新迭代j值:j=j+1，并转步骤1)；否则停止迭代，输出当前路径节点搜索顺序Cl=[c1c2…cK]。

MMP-DF算法步骤如下：

1) 输入观测向量y，测量矩阵Φ，稀疏度K，子路径d，最大路径迭代次数LMAX和停止迭代阈值ε，初始值l=0,rmin=y,Ω0=Ø,r0=y。

2) 如果lε，则用当前参数l、d、k由优先级函数layer_Order算法步骤得到当前路径节点搜索顺序序列Cl，更新参数l=l+1，j=0；否则转到步骤6)结束。

4) 如果j

MMP算法改进了正交匹配追踪算法支撑集非最优的不足，将正交匹配追踪算法每个原子仅分支出一个原子改为分支出多个原子，其多样化的搜索路径使搜索范围更广，避免陷入局部最优解。理论上可以得到远多于OMP算法的支撑集，大大提高了重构精度。但当遇到大规模数据时，MMP算法需要搜索大规模路径，考虑实际应用需要对搜索路径进行有效优化降低计算复杂度。

2 改进的快速稀疏度自适应多路径匹配追踪算法

在实际应用中，重构信号的稀疏度一般是未知的，借鉴SAMP算法稀疏度自适应和SP算法回溯的思想，结合MMP算法的优点和不足，本文提出了IMMP算法。该算法对内积匹配准则进行改良，利用阈值法选择支撑集，并采用变步长思想来逼近信号稀疏度，并对MMP算法的搜索路径进行剪枝处理，在不影响重构质量的同时极大减少了运算时间，使之更具实用价值。下面主要从以下几个方面对IMMP算法进行描述。

2.1 改进的内积匹配准则

MMP等贪婪算法主要使用内积匹配准则度量测量矩阵与残差值间的相关性强弱。传统的内积匹配准则更多地是从方向上区分差异，而对绝对的数值不敏感，从而影响对相似原子的区分，使观测矩阵中任意2个相近似的原子可能影响残差信号的匹配过程。这种仅考虑向量维度方向上的相似性而没考虑到各个维度量纲差异的不合理性会降低信号的重构质量。假设有任意向量a=(a1,a2,…,an)和向量b=(b1,b2,…,bn)。改良后的内积匹配准则公式为[21]：

(11)

2.2 剪枝优化搜索路径

(12)

从根节点迭代到第K个分支节点,其中每个节点代表不同的字典原子，当候选支撑集中选择的原子数量等于稀疏度K时，认为此路径搜索完成。根据原子选择优先级的不同，将会得到不同的候选支撑集。取当前起始路径l={1,2,…,LMAX},在后面每个路径迭代过程中,一个最有希望的原子被添加到当前路径中。当搜索路径达到最大值LMAX或者完全确定最优路径时终止迭代。图1给出了该算法的树搜索过程，其中LMAX=3，d=3,K=3。可以看到由C1=(1,1,1)确定的原子构成第1个支撑集，第2个支撑集则由C1=(2,1,1)确定的原子构成，直到选择最佳的候选支撑集为止。

在当前支撑集迭代完成后，将与上一个支撑集执行回溯步骤用来选择最佳的K个原子。在第2个候选支撑集{4,1,2}完成后，执行回溯细化没有替换任何原子，第3个候选支撑集{6,3,4}回溯重新选择原子后，支撑集更正为{6,2,4}，提高了路径搜索的精度。回溯虽然带来了额外的计算负担，但优化路径大大降低了计算复杂度，提高了算法的重构精度。

2.3 稀疏度自适应与指数变步长

稀疏度自适应算法设置的固定步长无法兼顾重构精度和重构效率，初始步长较小会降低算法重构效率，步长较大则会降低算法重构精度。采用兼顾两者的变步长是一个不错的方法。根据稀疏度估计的特点，改进算法稀疏度估计可以分为2个部分：1)初始阶段大步长快速估计，2)完成阶段小步长逐步逼近。

图1 MMP和IMMP算法原理Fig.1 Schematic diagram of MMP and IMMP algorithms

文献[22]研究表明,重构信号的残差能量在2个相邻阶段中是递减的，且随着支撑集长度λ不断逼近真实稀疏度K，残差能量减小速度逐渐变缓趋于稳定。所以本文以相邻阶段重构信号的残差能量作为步长变换的条件。当残差能量小于等于‖rmin‖2时，步长切换更新稀疏度到下一阶段，当残差能量小于ε2时稀疏度估计过程完成。ε2是迭代停止阈值，在这里取ε2=10-6。

利用ax指数函数的变化规律来调整步长，初始阶段步长取一个合适的初值s0，每次增加步长s=s0ax，支撑集长度λ=λ+s；其中a是固定常数，文献[23]证明当a∈[0.3,0.5]时效果较好，x为当前候选支撑集迭代次数，「·⎤表示向上取整。当支撑集长度λ接近真实稀疏度K时，添加进支撑集的原子越来越少，直到支撑集长度λ=λ+1。采用此变步长方法可提高算法重构质量和计算效率。

2.4 算法步骤

根据上面对IMMP算法原理的描述，在下面分别详细地给出了阶段自适应估计稀疏度Search函数和IMMP算法的实现步骤：

Search函数的实现步骤如下：

1) 输入搜索序列Cl，残差值r0，稀疏度λ，inputj={rj,Ωj,j}。

2) 如果j<λ或λ>length(Ωj)，更新参数j=j+1，否则转到步骤4)。

MMP-DF算法步骤如下：

3 仿真验证

本节使用一维信号模拟实验，以信号精确重构比(exact reconstruction ratio, ERR)和重构时间作为算法重构性能的评价标准，其中当重构信号的残差小于阈值ε1时，认为信号重构是成功的，本文取ε1=10-6。信号精确重构率反映了重构精度，其中ERR定义为准确恢复次数pn与总实验次数psum的比值：ERR=pn/psum重构时间和迭代残差反映了重构效率。仿真实验使用Matlab(版本R2018b)在一台装配了Core i5-6400 @2.70GHz 处理器的计算机上进行。实验中设置MMP和IMMP算法的最大迭代次数和子路径数(LMAX,d)分别为(50, 6)和(10, 6)。选择高斯随机矩阵作为观测矩阵，为避免随机因素的干扰，每个算法都独立重复进行了10 000次试验且稀疏信号的非零位置都是随机选择的。

3.1 改进的内积匹配准则的有效性验证

以典型的单路径搜索算法OMP作为MMP算法中的一条搜索路径中为例，分别使用内积准则和改进的内积准则来度量观测矩阵原子和残差信号的相关性，以便挑选最为匹配的原子。随机生成稀疏度K=30，长度N=256的一维信号作为测试信号。比较在加入高斯噪声后(SNR=15 dB),2种匹配准则下的残差值随不同迭代次数的变化情况，取对数表示的结果如图2所示。

图2 OMP不同迭代次数的残差(K=30)Fig.2 Residual error of different iterations of OMP(K=30)

很明显，随着迭代次数增加，残差值逐渐减小。同等条件下，可以从图2看出改进的内积匹配准则的残差值比内积准则更低，迭代过程中残差值逼近零的速度更快。这充分说明改进的内积匹配准则不仅更有利于挑选最优匹配原子，降低误选原子的概率，而且能够加速完成迭代逼近，提高重构效率。

表1是当压缩比M/N=[0.234 4,0.312 5,0.396 0]时，OMP算法应用2种不同原子匹配准则在不同高斯白噪声等级(SNR=[0,5,10,15,20,25,30] dB)干扰下的平均重构信噪比，更进一步验证了改进的内积匹配准则的性能。其中，重构信噪比公式为：

(13)

表1 2种原子匹配准则的重构性能比较Table 1 Reconstruction performance comparisons of two atomic matching criterias

实验表明应用改进的内积匹配准则在稀疏度和测量数2个方面都优于改进前的内积匹配准则。在相同压缩比时，改进的内积匹配准则有更高的重构信噪比；在有相同的重构效果下，改进的内积匹配准则能适应更低的信噪比，抗干扰性能更优。改进的内积匹配准则从向量的夹角信息和长度数值信息2个方面更好地比较了向量间的相关性强弱，是一种更加合理有效的相关性度量准则。

3.2 算法性能分析

本部分比较了IMMP算法与OMP、StOMP、SP、CoSaMP和MMP等5种稀疏信号重构算法的平均重构性能，同时也分析了在相同迭代次数下不同初始步长对IMMP算法性能影响。

图3(a)给出了固定测量数M=100时，重构信号的ERR性能随不同稀疏度K的变化曲线。从图3(a)可以看出，本文提出的IMMP算法的ERR要高于传统的重构算法，尤其当K>30时，IMMP算法的ERR明显远高于传统算法。当K=40时，IMMP算法在初始步长s={1,5,8,12}时的ERR为86.59%、87.51%、88.12%和88.79%，而除了CoSaMP算法ERR为0外，OMP、StOMP、SP和MMP算法的ERR分别仅为6.99%、34.91%、4.99%和40.85%。

图3(b)显示了各种算法对应的CPU平均计算时间，客观上可以比较算法的计算效率。MMP多路径搜索算法计算时间随着稀疏度K的增加呈现近似指数式增长，而OMP、StOMP、SP和CoSaMP算法的计算时间增加幅度不明显。优化搜索路径后的IMMP算法的计算时间较OMP、StOMP、SP和CoSaMP等单路径搜索算法略有增加，但远低于MMP算法。