基于改进子空间追踪算法的冲击波信号采集

王可心，韩太林，高杨，王啸

（长春理工大学 电子信息工程学院，长春 130022）

近年来，Donoho、Candès和Tao等人提出了一种全新的信号采集与处理理论——压缩感知理论（Compressive Sensing，简称CS）[1-3]。该理论表明，以低于甚至远低于奈奎斯特准则的采样率对稀疏域中稀疏或可压缩的信号进行随机采样，可精确重构原始信号。这一理论可同时对信号进行采样和压缩，既节约了采集系统的硬件资源，又降低了处理海量数据时软件的压力[4]。而本文所研究的冲击波信号，频率成分复杂，其中含有高频分量，因此用以奈奎斯特采样定理作为基础理论的采集系统采集冲击波信号，必须保持较高的采样率，而持续的高采样率产生的海量数据会给后续的数据存储、传输和处理带来巨大压力；且冲击波信号具有上升时间短、衰减速度快等特点，属瞬态信号，其所含信息相对集中，即在整个采集过程中，信息密度较低，可以认为存在某稀疏域能够对冲击波信号进行稀疏表示，并应用压缩感知理论对该信号进行测量。因此，本文引入压缩感知理论用于冲击波信号测试，摆脱对高采样速率的依赖，极大地降低了高采样率所带来的压力，具有现实意义。

压缩感知理论的关键技术主要有三部分：数据稀疏化、观测矩阵的构建和重构算法[5-6]，其中重构算法是非常重要的的一环。对于在某一稀疏域可压缩的信号恢复重建问题的研究，国内外已有多篇相关论文发表，目前，常用的重构算法主要有凸优化类算法、组合优化算法以及贪婪算法等几类。凸优化类算法具有良好的重建效果，但时间复杂度较大，难以处理大规模数据，实用性比较差。组合优化类算法的运行效率特别高，但这类算法对采样结构要求严格，实用性也比较差。而贪婪类算法的计算量较小，重建效果好，且这类算法比较容易实现，因此应用最为广泛。

当前贪婪类算法[7]以匹配追踪（Matching Pursuit，MP）算法和正交匹配追踪（Orthogonal Matching Pursuit，OMP）算法为代表，除此之外还衍生了许多OMP的改进算法，主要包括正则化正交匹配追踪（Regularized OMP，ROMP）算法、分段匹配追踪（Stagewise OMP，StOMP）算法、压缩采样匹配追踪（Compressive Sampling MP，CoSaMP）算法、子空间追踪（Subspace Pursuit，SP）[8-9]算法和稀疏度自适应匹配追踪（Sparsity Adaptive Matching Pursuit，SAMP）算法等。由于工程实践中对冲击波信号的重构效果要求较高，因此针对已知稀疏度信号的重构，本文在研究上述算法的基础上，重点结合OMP的原子选择思想和SP初始支撑集优化思想提出一种改进算法，主要提高了重构算法的两个性能：算法的重建效果与算法的执行效率。理论分析和实验仿真结果证明，本文算法的重建效果优于未改进前的算法，且算法执行效率有很大提高。

1 压缩感知与重建算法

设原始信号x是长度为N稀疏度为K的稀疏信号，通过测量矩阵φM×N（M＜N），得到长度为M的观测信号y，观测方程为y=φx。当K、M及N间满足关系（K＜＜M＜＜N）时，可精确重建原始信号x。而如何用观测信号y重建出原始信号x是重建算法需主要解决的问题，通常采用如下方式进行求解：

因为实际情况下允许存在一定程度的误差，求解公式（1）的最优化问题可用简单的近似求解形式替代，如式（2），其中ε是一个非常小的常量：

式（1）和式（2）的求解是l0范数最小化求解问题，是NP-hard问题，这类问题无法直接求解，但间接求解方法较多，其中贪婪迭代类算法因其算法结构简单，且运算量小，应用较为广泛。这类算法最早的求解形式是MP算法，OMP是MP算法改进后的一种情况，OMP每次迭代时仅向估计信号x̂的支撑集F中增加一个原子，因而算法效率较低。后来，从提高选取原子效率的角度出发，提出了ROMP算法和StOMP算法，这两种算法在每次迭代时根据其相关准则可向支撑集F中添加多个原子，提高了算法效率。后来回退筛选思想被引入压缩感知理论，出现了SP和CoSaMP算法，这两种算法的重构效果较好且算法复杂度低。

在实际应用中重构算法的信号重建效果与算法执行效率的好坏是评价算法优劣的重要指标，且工程实践中对冲击波信号的重构效果要求较高，针对这一情况，本文提出一种改进算法，该算法通过将OMP选择原子思想引入SP算法，优化SP算法初始支撑集，提高了子空间追踪算法的重建效果和执行效率。

2 子空间追踪算法及其改进算法

2.1 子空间追踪算法

MP、OMP、ROMP选择原子时都有一个弊端：一旦选择出原子，那么无论它是否正确，都将保留在支撑集中。这种弊端严重影响了算法的准确重建概率，为了解决这一问题，提出了子空间追踪算法。子空间追踪算法是一种可以消除错误原子的匹配追踪算法，该算法需要稀疏度作为先验信息，能够准确地重构满足RIP条件的信号。它的基本思想是在子空间中选择具有最高可靠性的K个原子，计算待识别K稀疏信号与空间中选择的原子之间的距离，然后根据其可靠性值去除并添加新的原子，直到确认一个足够接近的候选原子集[10-11]。

假设压缩观测y=φx，其中y为观测所得向量M×1，x为原信号N×1（M＜＜N），测量矩阵为φ，初始残差值为r0=y，信号的稀疏度为K。SP算法的基本步骤为：

输入：测量矩阵φ，观测的信号y，被测信号的稀疏度K；

迭代：

步骤1：令k=1，找出与当前残差最为匹配的K个原子；

步骤2：找到集合u中最大的K个值，将它们的下标存入集合I；

步骤3：更新支撑集Λk=Λk-1⋃I；

步骤5：残差更新：rk=y-φΛkφy；

并结束迭代过程；否则令k=k+1，继续迭代。

输出：原信号的重构信号。

图1 SP算法的算法框图

2.2 改进的子空间追踪算法

前文讨论的SP算法，不仅对不同信号的重建效率有很大差别，在重构同一信号的背景下，选取不同初始支撑集也会对算法的重建质量和效率造成不小差别，一个好的迭代初始支撑集对SP算法有着至关重要的作用[12]。针对SP算法的这一特点，本文提出一种预先优化SP算法初始支撑集的算法，为方便表示，本文算法命名为Orthogonal Matching Subspace Pursuit，简称OMSP（以下均采用此名称表示本文算法）。此算法采用正交匹配追踪算法选择原子思想，迭代K次产生的K个原子作为SP算法的初始支撑集，再进行原子筛选。

重构K稀疏信号时，重构算法的作用是在过完备字典中找到对应的K个原子，并将它们添加到支撑集。为了达到这一目的，OMP算法每次迭代仅选择一个原子，并将选择的原子添加到支撑集中，这样K次迭代后支撑集中有K个原子，构成OMP算法的支撑集。而SP法从最开始就直接选择出具有最高可靠性的K个原子构成初始支撑集，而后以现有支撑集内原子的可靠性为参考，利用回溯选择思想去寻找是否有可靠性更高的原子，如果有，则用新选的原子代替旧的原子；否则，这就是最后的支撑集。因此，当对重建算法的重建效果要求很高时，可应用本文提出的这种改进算法，它得到的候选支撑集比未改进前的SP算法更接近于原信号，此外该算法初始支撑集的选取引入了OMP算法原子选择思想，可靠性非常高，比较接近于原信号，所以SP算法不需要很多次迭代去剔除错误原子，因此本文算法的效率相对于未改进前的SP算法也会有所提升。

本文算法的具体实现步骤如下：

输入：测量矩阵φ，观测的信号y，被测信号的稀疏度K；

初始化：x0=0，初始残差r0=y，初始支撑集Λ0为空集；

迭代一：当k≤K时重复以下步骤：

步骤1：找出与当前的残差r最匹配的原子，将此原子系数加入到信号支撑集j=1,2,3,…,N；

步骤2：更新索引集Λk=Λk-1⋃λk；

步骤5：将迭代一得到的Λk作为SP算法的初始支撑集，进入迭代二；，测量矩阵φ。

迭代二：

步骤1：令k'=1，找出与当前残差最为匹配的K个原子；

步骤2：找到集合u中最大的K个值，将它们的下标存入集合I；

图2 本文算法的算法框图

3 实验数据处理结果

将SP算法与本文算法应用在冲击波信号采集中。为了验证SP算法与本文算法的重构效果，分别将其在5psi、50psi两种冲击波实测信号上进行实验和仿真，其中5psi传感器测得信号叠加有明显动态误差干扰，会产生约72kHZ的震荡，信号高频成分较强；50psi传感器实测信号，由于50psi传感器动态性能较好，信号几乎不含有动态误差[13]。

实验选用5psi、50psi冲击波实测信号作为原始信号，其中稀疏方式采用小波稀疏，观测矩阵采用高斯随机矩阵[14]。

实验参数配置：截取冲击波信号的有效部分，对其进行精确截取、降频等预处理，最后得到的每组信号长度N为4096点，稀疏度K取500，观测点数M取2048点。

3.1 SP算法重构

SP算法作为压缩感知重构算法：

图3 SP算法重构5psi传感器实测数据

图4 SP算法重构50psi传感器实测数据

图3（a）为5psi传感器实测原始信号，通过SP算法重构得到如图3（b）所示的重建信号，重构误差如图3（c）所示；图4（a）为50psi传感器实测原始信号，通过SP算法重构得到如图4（b）所示的重建信号，重构误差如图4（c）所示。

3.2 本文算法重构

本文算法作为压缩感知重构算法如图5、图6所示。

图5 本文算法重构5psi传感器实测数据

图6 本文算法重构50psi传感器实测数据

图5（a）为5psi传感器实测原始信号，通过OMSP算法重构得到如图5（b）所示的重建信号，重构误差如图5（c）所示；图6（a）为50psi传感器实测原始信号，通过OMSP算法重构得到如图6（b）所示的重建信号，重构误差如图6（c）所示。

3.3 两种算法重建结果对比

实验参数配置：设置测试M序列长度为1000-4000，测量值M取 1000，1500，2000，…，4000，分别进行50次模拟实验，取两种算法每一组的重构误差均值绘制曲线图，得到的实验结果如图7和图8所示。

图7 5psi实测数据测量数M与重构误差关系

图8 50psi实测数据测量数M与重构误差关系

经过曲线图对比可以发现，在两种测试数据下SP算法与本文算法的重构误差均随着测量数的增加而减小；测量数M相同时，本文算法的重构误差均小于SP算法；SP算法在M值小于2000时，重构误差才趋于一个较小的稳定值，而本文算法M值为选取的初始点1000时，重构误差就已经稳定在了一个比较小的值。因此，在重建误差的比较上，本文算法优于SP算法。

3.4 两种算法的算法效率对比

统计测量数M取不同值时两种算法的运行时间，并计算算法效率的提高比率：

统计及计算结果如表1、2所示。

经过上述两表对比可以发现，在两种测试数据下，M值取1000，1500，2000，…，4000时，本文算法的算法运行时间均远小于未改进前的SP算法，约为SP的四分之一左右，经计算得出结论：经计算改进后的SP算法运行效率提高了70%左右。

表1 两种算法重构5psi传感器实测信号的算法效率对比表

表2 两种算法重构50psi传感器实测信号的算法效率对比表

4 结论

本文引入压缩感知理论用于冲击波信号测试，深入研究了压缩感知理论的经典重建算法—子空间追踪算法，并提出了一种改进的子空间追踪算法，此算法引入了正交匹配追踪算法选择原子的思想，经过K次迭代选出K列原子，将此K列原子作为SP算法的初始支撑集，替换传统SP算法选择出的内积值最大的K列构成的支撑集，将改进算法与原始算法做比较，分析改进前和改进后的优势和劣势。实验表明：算法重建误差的比较上，本文算法优于SP算法；算法运行效率的比较上，本文算法优于SP算法，提高了70%左右。