基于CS的稀疏度变步长自适应压缩采样匹配追踪算法

雷丽婷 李 刚 蒋常升 梁 壮

1(兰州交通大学机电技术研究所 甘肃 兰州 730070)2(甘肃省物流及运输装备信息化工程技术研究中心 甘肃 兰州 730070)3(兰州交通大学机电工程学院 甘肃 兰州 730070)

0 引 言

Donoho[1]在2006年首次提出了压缩感知理论，成为了信号领域的一种新理论[1-3]。Nyquist采样定理局限性在于先采样后压缩，CS可以实现压缩与采样同时进行，并且缩短了重构时间。

重构作为压缩感知中最重要的部分，主要是指用低维的压缩信号通过某种算法还原出高维原始信号的过程，因此，重构算法的性能好坏将直接影响重构结果的精度。目前重构算法主要包括凸优化算法和迭代贪婪算法[4]，其中使用较为广泛的是迭代贪婪算法，因为它具有复杂度低和重构用时短的优势。起初此算法主要包括匹配追踪算法(Matching Pursuit，MP)和正交匹配追踪算法(Orthogonal Matching Pursuit，OMP)[5]两种，但将其广泛运用于多个信号处理领域后发现其并不能满足要求。许多学者针对其在残差内积的选择过程中效率较低，处理能力与抗干扰能力随着数据的复杂将变得均较弱等不足，提出了大量优化和改进的新算法。文献[6]和文献[7]分别提出了广义正交匹配追踪算法(generalized OMP，gOMP)及正则化正交匹配追踪(Regularized OMP，ROMP)，通过每次迭代选取多个原子扩充支撑集来提高重构速度。文献[8]为了找到重构复杂度和重构精度更好的折衷点，提出基于回溯思想的子空间追踪(Subspace Pursuit，SP)算法。文献[9]提出一个具有较大影响力的重构算法——压缩采样匹配追踪(Compressive sampling matching pursuit，CoSaMP)算法，对候选原子进行了“二次”检验，提高了原子的正确匹配率。以上为第一类迭代贪婪算法，均要求已知稀疏度K，而实际稀疏度K是未知的。文献[10]提出了稀疏度自适应匹配追踪算法(SAMP)，它具有计算速度快、算法简单的优点，但通过增加固定步长S的倍数，可逐渐增加至信号的真实稀疏度。因此，步长S的取值在重构过程中显得特别重要，取大或取小都将会影响重构精度，甚至可能出现较大的重构误差[11]。

SAMP算法是目前使用较为广泛的重构算法之一，但其以固定步长逼近真实稀疏度K，初始步长的选取对于重构性能影响很大。由于对于压缩信号误差来源于测量与恢复，原有的重构算法中将残差的2范数作为停止迭代的条件，这不能判断迭代的准确性。因此，本文以SAMP算法为主体，提出了一种稀疏度变步长自适应压缩采样匹配追踪(CSVssAMP)算法，采用CoSaMP算法中选出内积值最大的2L列的思想，使用相邻两次迭代最小二乘解的差的2范数作为停止迭代的条件，再通过变步长的方式逼近稀疏度的真值。

1 压缩感知理论

1.1 信号的稀疏分解

在实际应用场景中，需要稀疏化目标信号，表示如下：

x=Ψs

(1)

式中：Ψ为N×N的稀疏矩阵；s为K稀疏的矩阵。

1.2 信号的观测矩阵φ的设计

在观测矩阵的设计过程中，采用降低维度的方法使信号应用更加简单，为保证其信号的完整性，从观测数据中准确地还原原始信息，必须满足有限等距理论(RIP)。在CS编码测量模型中，可以通过式(2)得出原始信号x：

x=φx=φΨs=A

(2)

式中：φ可以选用高斯随机矩阵。

1.3 信号的重构算法设计

重构算法就是利用观测数据来恢复原始信号。当测量矩阵满足RIP条件时，经过一系列的运算，通过y值重构出目标信号x，利用l0范数求解以下最优化问题：

minα‖α‖l0s.t.y=φΨα

(3)

2 算法设计

根据稀疏度是否已知，将迭代算法分为两类：第一类以OMP算法为基础；第二类算法以SAMP算法[11]为代表。表1为本文中参与比较算法的简单性能介绍。

表1 本文中参与比较算法性能的简单介绍

2.1 算法描述

设Λt是t次迭代的索引集合，aj表示矩阵A的第j列，At={aj|j∈Ck}表示由索引集Ck选择出的矩阵A的列集合(列数为Lt)，θt为Lt×1的列向量，〈·,·〉表示向量的内积，abs[·]表示求模值(绝对值)。

步骤1初始化：r0=y，Λ0=∅，L=S，t=1。

步骤2计算u=abs[ATrt-1](即计算〈rt-1,aj〉,1≤j≤N)，在u中选择2L个最大值，其对应于矩阵A的列序号j构成集合Sk。

步骤3令Ck=Λt-1∪Sk，At={aj|j∈Ck}。

步骤4求y=Atθt的最小二乘解：

步骤8当‖rnew‖2≥‖rt-1‖2时，如果‖rnew‖2/‖rt-1‖2≥β，(β是步长变换条件参数，取值为1.2)更新步长，L=L+S,t=t+1返回步骤2，当时t=M，跳出迭代，进入步骤9；如果1≤‖rnew‖2/‖rt-1‖2<β，更新步长：L=L+aS，t=t+1，返回步骤2，其中自适应参数a∈(0,1)，当t=M时，停止迭代，进入步骤9。

2.2 算法流程

CSVssAMP算法流程如图1所示。在整个流程图中，要分别设置4个参数。步长S的值可以设置得大一些，以快速逼近K的真实值，从而缩短重构时间。步骤7中，相邻两次迭代的最小二乘解的差的2范数被用作判断迭代是否停止的条件，用α表示，通常取值为10-6。为了执行步长变换，需要β来比较新旧残差，使用自适应参数a来调整步长，实现以小步长精准逼近真实稀疏度。

图1 CSVssAMP算法流程图

2.3 算法应用

CSVssAMP算法的应用意义非常重要，特别是在需要高重构效率的领域，如卫星遥感数据的实时监测。研究人员实时监测卫星有效载荷和运行的状态，就是通过实时监测遥感数据完成的。为了实现精准的监控，需要测量多个参数，并进行长时间的实时数据采集，因此，需要考虑如何解决大量数据的采集和存储的问题。经大量相关研究，研究人员提出利用压缩感知方法在信号采集端实现同步采样和压缩。为了实时分析和监测卫星运行状态，测量数据通过无线传感器网络(WSN)实时传输到地面控制中心；为了传输的需要，测量数据将被压缩再传输给控制中心；为了保证能真实地反映卫星的运行状态，控制中心要对接收到的数据进行实时重构和信息交互。

3 实 验

本节将对CSVssAMP算法的重构效果进行评估。实验主要分为两部分，一是不同稀疏度下重构算法性能比较，二是不同观测值下的重构算法的性能比较分析。算法执行的硬件条件为Intel(R) Core(TM)(i5-3470 CPU)和MATLAB 7.0。

3.1 不同稀疏度下算法性能比较

本文选取高斯稀疏信号作为评价指标，通过信号在不同稀疏度K下的重构成功率和平均重构时间进行对比，对新算法的重构效果进行验证。实验设置数据长度N=256，测量值M=128。

3.1.1 重构成功概率比较

本文分别对第2节介绍的6种算法和本文算法进行了仿真，得出重构成功率-K值的变化趋势图，如图2所示。不同K值循环迭代1 000次，阈值γ=10-6。实验参数设定如下：CSVssAMP算法中S=5，α=10-6和β=1.2。

图2 不同K值下7种算法的重构成功概率比较

可以看出，对于所有重构算法，如果保持N和M始终不变，则重构成功的概率曲线将随着K值的增加而呈现下降趋势，这是由于具有较高不确定性的原始信号限制了信息的获取。总体而言，CSVssAMP算法的重构能力明显优于已有的重构算法，在相同的K值下，其重构能力也有相应的提高，100%重构时算法的K值最大。

3.1.2 平均重构时间比较

考虑到CSVssAMP算法以SAMP算法为主体进行了相应的改进，通过考察两种算法的重构时间，来验证本文算法的优越性。步长设置如下：SAMP算法中S=5，CSVssAMP算法中S=10。不同K值下两者的重构时间比较如图3所示。

图3 不同K值下SAMP算法和改进算法的重构时间比较

可以看出，当稀疏度K为45、50、55和60时，重构时间分别缩短了22.2%、38.4%、41.5%和45.8%。因此， CSVssAMP算法的重构效果更好。

3.2 不同测量值下算法性能比较

对于目标信号，由于传感器数据传输的数量有限，由迭代算法恢复的观测信号的长度将会受到限制。本文通过将稀疏度一定时信号在不同测量值M下的重构成功率和平均重构时间进行对比，对新提出算法的性能进行评估。

3.2.1 重构成功概率比较

目标信号的选取与3.1.1节的相同，实验设置数据长度N=256，稀疏度K=20，采用OMP、ROMP、CoSaMP、SP、StOMP、SAMP和本文算法在不同测量值M下进行仿真，其重构成功概率比较如图4所示。

图4 不同M值下7种算法的重构成功概率比较

为了更好地比较每种迭代算法的恢复还原能力，设置信号的测量值M∈[50,100]，通过分析和比较，重构成功率的变化曲线图随着M值的增加呈现上升趋势，即重构成功的概率随着测量值的增加而增加，因为随着测量值的增加，获得的原始信号的信息越来越多，则恢复出的原始信号精度更高。当测量值M相同时，SAMP算法优于其他5种算法，并且CSVssAMP算法的性能也得到进一步的提高。100%重构时CSVssAMP算法的M值最小。

3.2.2 平均重构时间比较

考虑到CSVssAMP算法是以SAMP算法为主体算法进行了相应的改进，通过考察两种算法的重构时间，来验证本文算法的优越性。随机选取5个测量值M分别进行对比，目标信号的平均重构时间如图5所示。步长设置如下：SAMP算法中S=4，CSVssAMP算法中S=8。

图5 不同测量值下SAMP算法和改进算法的重构时间比较

可以看出，当测量值M为50、55、60、65和70时，重构时间分别缩短了33.3%、29.6%、35.7%、33.8%和30.6%。因此，不同M值下，CSVssAMP算法具有更好的恢复性能。

3.3 不同步长下算法性能比较

为了更好地验证CSVssAMP算法具有更好的恢复能力，通过使用不同的步长，绘制M值与重构成功概率之间的关系曲线图，其中步长S为2和8的情况如图6所示。

图6 不同步长下SAMP算法和改进算法重构成功率比较

可以看出：总体上，重构成功率随着步长减小而增加，因为步长减小的同时可以实现以小步长逼近真实稀疏度值。在相同S下，CSVssAMP算法和SAMP算法的两条曲线非常接近，特别是当S=2时，前者略好于后者；当S=8时，可以更好地体现CSVssAMP算法的高重构性能。

4 结 语

本文通过对多种重构算法的重构性能进行分析和比较，发现第一类迭代算法无法解决稀疏度未知的信号的重构问题，并且它们均采用固定步长进行迭代实验。针对原始算法中存在的问题，以SAMP算法为主体算法，采用自适应调整方法来选择最优的稀疏度K。综上，本文提出了稀疏度变步长自适应压缩采样匹配追踪 (CSVssAMP)算法。与SAMP算法相比，本文算法采用了CoSaMP的思想(CoSaMP选2L个原子，而SAMP选L个)，保证了每次迭代都有2L个原子留下来，实现了在低噪声信号下高精度的重构。应用双阈值以实现步长的自适应变化，以更大的步长快速靠近真实的K值，然后再以小步长完成精准逼近，通过提高重构速率来实现更高的恢复精度。仿真结果表明，当稀疏度K和测量值M不同时，本文算法的性能均有明显提升。本文算法能够缩短重构时间，使用步长自适应对原始的固定步长进行了替换，重构效果得到进一步的提高。