, 耿蓉 东北大学 计算机科学与工程学院, 辽宁 沈阳 110169
收稿日期：2020-04-10
基金项目：国家自然科学基金资助项目(61671141, 61701100)。
作者简介：季策(1969-), 女, 辽宁沈阳人, 东北大学副教授。
摘要：为进一步提高压缩感知重构算法的重构成功率和重构精度, 从原子匹配准则和预选阶段原子选择方式的角度出发, 提出一种基于Dice系数的弱选择回溯匹配追踪(weak-selection backtracking matching pursuit based on Dice coefficient, DWBMP)算法.首先, 采用Dice系数匹配准则度量两个向量之间的相似性, 选出最匹配的原子, 以优化支撑集; 然后, 结合回溯思想和弱选择思想剔除相似性较小的原子, 完成预选阶段原子的二次筛选.MATLAB仿真结果显示, 相同条件下, DWBMP算法较经典的压缩感知重构算法具有更优的重构精度和重构成功率.
关键词：压缩感知重构算法贪婪算法匹配准则Dice系数二次筛选
Weak-Selection Backtracking Matching Pursuit Algorithm Based on Dice Coefficient
JI Ce, WANG Jin-zhi
, GENG Rong School of Computer Science & Engineering, Northeastern University, Shenyang 110169, China
Corresponding author: WANG Jin-zhi, E-mail: 1421268228@qq.com.
Abstract: In order to further improve the success rate and accuracy of reconstruction of the compressed sensing reconstruction algorithm, a weak-selection backtracking matching pursuit based on Dice coefficient(DWBMP) algorithm is proposed from the perspective of atomic matching criteria and pre-selection stage's atom selection methods. First, the Dice coefficient matching criterion is used to measure the similarity between two vectors, and the best matching atom is selected to optimize the support set. Then, the backtracking idea is combined with weak-selection idea to eliminate the atoms with small similarity, thus completing the secondary selection of the atoms in the pre-selection stage. The MATLAB simulation results show that under the same conditions, the DWBMP algorithm has better success rate and accuracy of reconstruction than the classic compressed sensing reconstruction algorithm.
Key words: compressed sensingreconstruction algorithmgreedy algorithmmatching criteriaDice coefficientsecondary selection
随着认知无线电技术和超宽带技术的不断进步, 为突破更高的传输速率, 对采样技术的要求越发严苛, 若以传统的奈奎斯特采样定律进行信号采样, 最少需要两倍信号带宽, 这将需要更大的存储空间与传输资源, 同时也加大了采样系统的压力.为了解决以上难题, Donoho, Candes等多位****提出了压缩感知(compressed sensing, CS)理论[1-3], 即如果信号是可压缩的或具备稀疏性, 则可以根据较少的观测数以较高的成功率重构出原始信号, 可以在完成数据采集的同时完成数据压缩, 从而节省了软硬件资源和数据处理时间, 是一种全新的信号获取和处理方式.
信号重构算法作为CS理论的重要组成部分之一, 决定了CS理论能否应用于实践, 主要问题是如何从低维观测信号中以较高的成功率重构出高维原始信号.目前常用的重构算法主要有三大类, 即凸优化、组合及贪婪算法, 每一类算法都有优点和不足[4].凸优化算法的重构性能较好, 但算法的复杂度太高; 组合算法的计算速度较快, 但是需要采样的样本数目比较多, 失去了压缩采样的意义; 贪婪算法则均衡了效率和重构性能, 相比之下更适合解决实际的应用问题.典型的贪婪算法有正交匹配追踪(orthogonal matching pursuit, OMP)算法[5]、正则化正交匹配追踪(regularized matching pursuit, ROMP)算法[6]、压缩采样匹配追踪(compressive sampling matching pursuit, CoSaMP)算法[7]、子空间追踪(subspace pursuit, SP)算法[8]和分段弱正交匹配追踪(stage weak matching pursuit, SWOMP)算法[9].以上算法均采用内积匹配准则度量向量之间的相似性, 但该准则在匹配时会丢失部分原始信号信息, 同时, 经典的贪婪算法在预选阶段原子选择方式上也存在一些不足, 例如OMP算法在原子的预选阶段只选择一个最匹配的原子加入支撑集, 导致算法的复杂度较高; SWOMP算法利用设置阈值的方式选择多个原子加入支撑集, 由于所选原子并不是最匹配的原子, 所以降低了算法的重构成功率; CoSaMP和SP算法则是固定地分别选择最匹配的2K和K个原子加入候选集, 导致候选集的选择不够精确、灵活, 同时降低了算法的重构精度.因此, 为解决以上所述问题, 本文以现有贪婪算法的研究为基础, 提出一种新的贪婪算法——基于Dice系数的弱选择回溯匹配追踪(weak-selection backtracking matching pursuit based on Dice coefficient, DWBMP)算法.首先, DWBMP算法利用Dice系数匹配准则度量观测矩阵和残差之间的相似性, 从观测矩阵中选取最匹配的原子, 保证信号重构的质量, 然后在原子的预选阶段增加二次筛选, 有效地减少不必要原子的选择, 进一步提高信号的重构效果.
1 经典贪婪算法及其存在的问题压缩感知重构算法中的贪婪算法因算法复杂度较低、重构速度较快且重构精度也较高的优点应用最广泛, 其核心思想是利用迭代的方式选取与信号最匹配的一个或多个原子, 组成信号的支撑集, 然后以该支撑集为基础利用线性规划的方法估计出原始信号.经典的贪婪算法有OMP, ROMP, CoSaMP, SP, 以及SWOMP算法等.该类算法主要包括相似性计算、原子选择和支撑集更新、信号估计, 以及残差计算4个步骤[10].
相似性计算: 利用内积匹配准则度量观测矩阵Φ和残差r之间的相似性, 得到相似系数u.
原子选择和支撑集更新: 每次迭代根据相似系数u选择相似性最大的一个或者多个原子, 并更新支撑集.
信号估计: 基于已识别的支撑集, 采用最小二乘法计算稀疏信号
残差计算: 根据估计信号计算残差r, 然后继续迭代, 直到符合停止条件.
综上所述可以发现, 经典贪婪算法有一个共同的特点, 即利用内积匹配准则度量观测矩阵和残差之间的相似性, 并将计算得出的相似系数作为选取最匹配原子的依据, 但内积匹配准则会丢失部分原始信号信息, 影响重构的精度；而且, 经典贪婪算法中除CoSaMP和SP算法外其他算法均没有回溯思想, 即原子被加入支撑集之后始终存在于后续的迭代过程中, 对于错误选入的原子缺乏重判和剔除的功能, 从而影响了信号的重构.进一步的研究发现, CoSaMP和SP算法虽加入了回溯思想, 可以实现错误原子的修剪和剔除, 在一定程度上保证重构的质量, 但其固定地选择最匹配的2K/K个原子加入候选集, 使得候选集中存在很多不必要的原子, 降低了支撑集的准确性和算法的重构精度.
因此, 为解决以上存在的问题, 并进一步提高贪婪算法的重构成功率和重构精度, 从原子匹配准则和预选阶段原子选择方式的角度出发, 提出一种基于Dice系数的弱选择回溯匹配追踪(DWBMP)算法.
2 基于Dice系数的弱选择回溯匹配追踪算法2.1 Dice系数匹配准则经典贪婪类重构算法使用内积匹配的准则来度量观测矩阵Φ和残差r之间的相似性.假设x, y是2个任意的向量, 其中x =(x1, x2, …, xn), y=(y1, y2, …, yn), 则内积匹配准则定义为
 | (1) |
 | (2) |
本文算法利用Dice系数匹配准则度量观测矩阵和残差之间的相似性, 具体描述如下:
 | (3) |
 | (4) |
2.2 二次筛选经典的CoSaMP和SP算法与其他贪婪算法的区别在于加入了回溯思想.首先, 在迭代开始之前确定初始残差r0, 通过式(5)计算出观测矩阵Φ和残差r的相似系数u:
 | (5) |
 | (7) |
因此, 本文针对预选阶段原子选择存在的不足引入弱选择思想.首先, 根据相似系数选择最匹配的K个原子对应的索引存入索引集J, 在此基础上加入弱选择进行二次筛选, 在索引集J中选出相似性大于或等于阈值Th=β·max|D(Φj, r)|的原子对应的索引存入索引集F, 即原子的选择可以根据相似性的大小实现动态选择, 其中β为弱选择参数.对于参数β, 如果取值过大, 索引集中较高相似性的原子数将减少, 进而增加算法的运行时间; 如果取值过小, 索引集中就会包含相似性较低的原子和多余的原子, 进而影响算法的重构质量.基于上述分析, 本文选取β∈[0.6, 0.8].仿真结果表明, 在β=0.7和β=0.75时, 本文算法具有更好的重构效果, 同时两者的差异较小, 故本文随机选择β=0.75.改进之后的算法在预选阶段通过二次筛选可以选取最有可能属于原始信号支撑集的索引, 不仅在很大程度上减少了原子的浪费, 同时也提高了算法重构效果.
2.3 算法实现假设N×1维的原始信号x在稀疏矩阵Ψ上可以表示为稀疏信号, 即
 | (8) |
利用一个与Ψ不相关的观测矩阵来采样原始信号x, 得到观测信号y:
 | (9) |
根据式(8)整理得
 | (10) |
综合以上压缩感知过程, DWBMP算法的具体步骤如下:
输入: 观测矩阵Φ, 观测信号y, 稀疏度K, 参数β;
步骤1 ??初始化: 残差r0=y, 迭代次数n=1, 索引集F0=?, 支撑集T0=?;
步骤2 ??通过式(5)得相似系数u, 然后从u中选取K个最大值对应的索引加入索引集J;
步骤3 ??从索引集J中取出大于或等于阈值Th=β·max|D(Φ, rn-1)|的原子所对应的索引存入索引集Fn中;
步骤4 ??更新候选支撑集Cn=Tn－1∪Fn;
步骤5 ??利用最小二乘法计算稀疏信号
步骤6信 ??号估计
步骤7 ??n=n+1, 如果n≤K则返回步骤2继续迭代, 如果n>K或者残差
输出: 信号x的稀疏估计
3 算法仿真及分析为了验证DWBMP算法的重构性能, 本文在MATLAB R2016a环境下进行仿真.主要验证Dice系数匹配准则是否可行、有效, 以及一维随机信号的重构性能.实验采用的一维随机信号长度为N=256.为了避免随机因素对实验结果造成影响, 本文涉及的数据都是运行1 000次后求得的平均值.
3.1 Dice系数匹配准则可行性和有效性验证使用内积匹配和Dice系数匹配两种准则度量观测矩阵和残差之间的相似性, 选取最匹配的原子.
首先比较在两种原子匹配准则下, 信号重构的绝对误差λ1和相对误差λ2:
 | (11) |
 | (12) |
表 1(Table 1)
 表 1 重构的绝对误差和相对误差Table 1 Absolute and relative errors of reconstruction
| 表 1 重构的绝对误差和相对误差 Table 1 Absolute and relative errors of reconstruction |
由表 1可知, 相同的参数设置下, Dice系数匹配准则下的信号重构误差更小, 由此可以说明Dice系数匹配准则可以选取最匹配的原子, 从而提高信号重构的精度.
其次比较了两种原子匹配准则下, 不同稀疏度和观测数的信号重构成功率, 如图 1、图 2所示.其中, 重构成功率=成功重构次数的总和/1 000.
图 1(Fig. 1)
 | 图 1 不同匹配准则下算法重构成功率与稀疏度的关系Fig.1 Relationship between the success rate of algorithm reconstruction and sparsity under different matching criteria |
图 2(Fig. 2)
 | 图 2 不同匹配准则下算法重构成功率与观测数的关系Fig.2 Relationship between the success rate of algorithm reconstruction and the number of observations under different matching criteria |
由于同一信号的不同信号段可能有不同的稀疏度, 而且受传感器数量和信道容量的影响, 观测信号的长度会受到一定程度的影响, 不同条件下获得的观测信号长度会有所不同, 所以应确保Dice系数匹配准则在任何稀疏度和观测数下均可获得比较高的重构成功率.参数设置如下: 观测数M=128, 稀疏度K的取值区间为[10, 70]; 稀疏度K=20, 观测数M的取值区间为[50, 100]; 步长为5;观测矩阵为高斯矩阵、伯努利矩阵; 每组实验进行1 000次.
由图 1、图 2可以直观地看出, 当信号的观测数(稀疏度)一定时, 两种算法的信号重构成功率均随着稀疏度(观测数)的增加而逐渐减小(增加), 但是在同一稀疏度(观测数)下, 基于Dice系数匹配准则的算法的重构成功率明显高于基于内积匹配准则的算法; 而且, 当观测矩阵为伯努利矩阵时, Dice系数匹配准则的优越性更加明显.由此可以说明Dice系数匹配准则降低了错误原子被选择的概率, 提高了信号重构的成功率.
3.2 一维随机信号重构验证为了验证本文算法的重构性能, 本实验将对比DWBMP算法与OMP, SWOMP, CoSaMP, SP算法的性能.其中, 评价重构算法的主要指标是算法重构的精度和成功率.由于不同信号段可能存在不同的稀疏度和不同长度的观测信号, 因此本实验的内容是对比不同算法在相同条件下的重构误差和不同条件下的重构成功率.
首先, 对比五种算法在相同条件下的重构误差(见表 2).仿真参数设置: 观测数M=128, 稀疏度K=20, 观测矩阵为高斯矩阵, 每组实验进行50次取平均值.
表 2(Table 2)
表 2 算法的绝对误差与相对误差Table 2 Absolute and relative errors of the algorithm
| 表 2 算法的绝对误差与相对误差 Table 2 Absolute and relative errors of the algorithm |
由表 2可知, 上述五种算法中, 本文提出的算法具有最小的绝对误差和相对误差, 由此可以说明本文算法的重构精度优于其他四种算法.
其次, 对比五种算法在不同稀疏度下的重构成功率, 如图 3所示.仿真参数设置: 观测数M=128, 稀疏度K的取值区间为[10, 70], 步长为5, 观测矩阵为高斯矩阵和伯努利矩阵, 每组实验进行1 000次.
图 3(Fig. 3)
 | 图 3 1算法重构成功率与稀疏度的关系Fig.3 Relationship between the success rate of algorithm reconstruction and the sparsity |
由图 3可见, 当观测矩阵为高斯矩阵和伯努利矩阵时, 所有算法的重构成功率均随稀疏度的增大呈现出下降的趋势, 但DWBMP算法的重构成功率明显优于OMP, SWOMP, CoSaMP和SP算法; 而且当观测矩阵为伯努利矩阵时, DWBMP算法的优越性更加明显.据图 3a显示, 当稀疏度K=20时, OMP算法出现重构失败(即重构成功率开始从100%逐渐减小); 当稀疏度K=35时, SWOMP和SP算法出现重构失败; 当稀疏度K=45时, CoSaMP和DWBMP算法出现重构失败, 但是随着稀疏度K的增大, CoSaMP算法重构成功率呈现出直线下降的趋势, DWBMP算法重构成功率却一直保持稳定的下降.据图 3b显示, 当稀疏度K=10时, SWOMP算法重构成功率仅35%, OMP, CoSaMP和SP算法出现重构失败, 此时DWBMP算法可以完全重构; 当稀疏度K=40时, SWOMP和SP算法几乎无法重构, CoSaMP和OMP算法重构成功率在40%左右, 此时DWBMP算法仍然可以完全重构; 当稀疏度K>40时, DWBMP算法重构成功率才出现下降的趋势, 而且下降速率比较稳定.
最后, 对比五种算法在不同观测数下的重构成功率, 如图 4所示.仿真参数设置: 稀疏度K=20, 观测数M的取值区间为[50, 100], 步长为5, 观测矩阵为高斯矩阵和伯努利矩阵, 每组实验进行1 000次.
图 4(Fig. 4)
 | 图 4 算法重构成功率与观测数的关系Fig.4 Relationship between the success rate of algorithm reconstruction and the number of observations |
由图 4可知, 当观测矩阵为高斯矩阵和伯努利矩阵时, 所有算法的重构成功率均随观测数的增大呈现出上升的趋势, 但DWBMP算法的重构成功率明显优于OMP, SWOMP, CoSaMP和SP算法; 而且当观测矩阵为伯努利矩阵时, DWBMP算法的优越性更加明显.据图 4a显示, 当观测数M=75时, OMP算法重构成功率是60%, SWOMP, CoSaMP和SP算法重构成功率是80%, 而DWBMP算法重构成功率已达到99%.据图 4b显示, 当观测数M=80时, SWOMP和SP算法重构成功率均在10%以下, CoSaMP和OMP算法重构成功率分别是25%, 60%, 而DWBMP算法重构成功率已达到99%;当观测数M=85时, DWBMP算法已几乎可以实现完全重构, 而其他算法重构成功率并未实现大幅度的增加, 且当观测数M=100时, 其他算法也未能实现完全重构.
对于实际应用而言, 除了考虑算法重构的成功率和精度, 也需要考虑算法的运行时间, 在同等条件下, OMP, SWOMP, CoSaMP, SP和DWBMP算法的平均运行时间如图 5所示.
图 5(Fig. 5)
 | 图 5 算法运行时间Fig.5 Run time of algorithms |
由图 5可以看出, OMP, SWOMP, CoSaMP, SP和DWBMP算法的运行时间分别为0.265 2, 0.158 7, 0.219 3, 0.194 8和0.149 7 s.综上所述, DWBMP算法在保证较低运行时间的基础上实现了较好的重构性能.
4 结语本文针对经典贪婪算法存在的不足提出一种新的贪婪算法, 即DWBMP算法.该算法引入Dice系数匹配准则作为相似性度量准则, 同时结合回溯思想和弱选择思想对预选阶段的原子选择进行二次筛选, 充分保证了迭代过程中可以选取最匹配的原子, 不仅优化了支撑集的选择, 还减少了原子的浪费.经仿真验证, 同等条件下本文提出的算法在重构性能方面优于经典的OMP, SWOMP, CoSaMP和SP算法, 且效果明显.
参考文献
| [1] | Donoho D L. Compressed sensing[J]. IEEE Transactions on Information Theory, 2006, 52(4): 1289-1306. DOI:10.1109/TIT.2006.871582 |
| [2] | Candes E J, Romberg J, Tao T. Robust uncertainty principles: exact signal recognition from highly incomplete frequency information[J]. IEEE Transactions on Information Theory, 2006, 52(2): 489-509. DOI:10.1109/TIT.2005.862083 |
| [3] | Candes E J.Compressive sampling[C]// Proceedings of the International Congress of Mathematicians.Madrid, 2006: 1433-1452. |
| [4] | 杨凯. 基于压缩感知的信道估计技术研究[D]. 成都: 电子科技大学, 2018: 22-23. (Yang Kai.Research on channel estimation based on compressed sensing[D].Chengdu: University of Electronic Science and Technology of China, 2018: 22-23. ) |
| [5] | Tropp J A, Gilbert A C. Signal recovery from random measurements via orthogonal matching pursuit[J]. IEEE Transactions on Information Theory, 2007, 53(12): 4655-4666. DOI:10.1109/TIT.2007.909108 |
| [6] | Needell D, Vershynin R. Uniform uncertainty principle and signal recovery via regularized matching pursuit[J]. Foundations of Computational Mathematics, 2009, 9(3): 317-334. DOI:10.1007/s10208-008-9031-3 |
| [7] | Needell D, Tropp J A. CoSaMP: iterative signal recovery from incomplete and inaccurate samples[J]. Applied and Computational Harmonic Analysis, 2008, 26(3): 301-321. |
| [8] | Dai W, Milenkovic O. Subspace pursuit for compressive sensing signal reconstruction[J]. IEEE Transactions on Information Theory, 2009, 55(5): 2230-2249. DOI:10.1109/TIT.2009.2016006 |
| [9] | Blumensath T, Davies M E. Stagewise weak gradient pursuit[J]. IEEE Transactions on Signal Processing, 2009, 57(11): 4333-4346. DOI:10.1109/TSP.2009.2025088 |
| [10] | Abdel-Sayed M M, Khattab A, Abu-Elyazeed M F.Adaptive reduced-set matching pursuit for compressed sensing recovery[C]// IEEE International Conference on Image Processing.Phoenix, 2016: 25-28. |
| [11] | Zhu M D, Li M Y, Geng Z, et al.Dice coefficient matching-based sparsity adaptive matching pursuit algorithm for the digital predistortion model pruning[C]// IEEE 18th International Conference on Communication Technology.Chongqing, 2018: 1032-1035. |
| [12] | 王欣, 张严心, 黄志清. 基于变步长的正则化回溯自适应追踪算法[J]. 电子学报, 2018, 46(8): 1829-1834. (Wang Xin, Zhang Yan-xin, Huang Zhi-qing. Regularized backing adaptive pursuit algorithm based variable step-size[J]. Acta Electronica Sinica, 2018, 46(8): 1829-1834.) |
| [13] | Hu Y F, Zhao L Q. A fuzzy selection compressive sampling matching pursuit algorithm for its practical application[J]. IEEE Access, 2019, 7: 144101-144124. DOI:10.1109/ACCESS.2019.2941725 |
| [14] | 费洪涛, 何雪云, 梁彦. 基于自适应压缩感知的OFDM稀疏信道估计研究[J]. 南京邮电大学学报(自然科学版), 2019, 39(2): 49-54. (Fei Hong-tao, He Xue-yun, Liang Yan. OFDM sparse channel estimation based on adaptive compressed sensing[J]. Journal of Nanjing University of Posts and Telecommunications(Natural Science), 2019, 39(2): 49-54.) |
