一个稀疏概况自适应匹配追踪算法

文摘

匹配追踪算法的压缩传感、传统的重建算法需要知道稀疏信号。稀疏的自适应匹配追踪(桑普)算法可以自适应方法的信号稀疏稀疏时是未知的。然而,桑普算法从0开始,多次迭代固定步长近似稀疏,这就增加了运行时。提高运行速度,稀疏概况自适应匹配追踪(SPAMP)算法。首先,稀疏概况策略是用来估计稀疏,然后桑普的信号重构算法与概况稀疏的迭代初始值。概况稀疏的信号重构的方法,大大减少了迭代次数,加快了运行效率。

1。介绍

奈奎斯特抽样定理指定,以避免丢失信息的捕获信号时,一个人必须样品至少两倍的信号带宽。传统的信息采集和压缩过程伴随着大量数据浪费,导致设备成本的增加。随着大数据的时代,对一些高频信号,它是硬件设备很难满足采样的要求。迫切需要一种新的方法来捕获和表示信号速率明显低于奈奎斯特速率。压缩感知(CS) (1,2)一直是近年来上升的信号处理理论,它不同于奈奎斯特采样定理。作为一种新的信号处理理论,它吸引了大多数工业领域的研究人员的广泛关注。它已经被应用于不同的领域,取得了可喜的成果3- - - - - -7]。

大多数关于压缩传感的研究主要集中在三个方向:信号稀疏表示、测量矩阵,和重建算法。信号的稀疏表示是nonsparse信号转换成稀疏信号的转换,如离散余弦变换、离散傅里叶变换和小波变换。压缩的信号可以通过测量矩阵的稀疏信号相乘。必须小于的维数压缩信号的稀疏信号。大量的研究表明,高斯矩阵,伯努利矩阵,和部分阿达玛矩阵可以用作测量矩阵。重建算法重建稀疏信号压缩的信号,和重建算法直接影响重构信号的质量。近年来,取得了巨大成就领域的重建算法。然而,许多重建算法都有自己的局限性。由于昂贵的凸优化算法的计算成本(8,9),很难实现。贪婪的重建算法主要包括正交匹配追踪(OMP) (10,11),正规化OMP (ROMP) [12),压缩采样匹配追踪(CoSaMP) [13],子空间的追求(SP) [14广义OMP (gOMP) [],15),在舞台上OMP(踩)16],稀疏的自适应匹配追踪(桑普)[17]。与凸优化算法相比,贪婪算法具有更快的重建速度。在上面提到的贪婪的重建算法,OMP,玩耍,CoSaMP, SP和gOMP算法需要知道稀疏信号。如果信号稀疏是未知的,我们只能通过猜测稀疏重构信号。稀疏直接影响信号重建的质量。跺脚和桑普算法可以直接不知道信号稀疏重构原始信号。桑普算法重构信号通过设置一个固定的步长,通过多次迭代逼近真实的信号稀疏。桑普算法近似稀疏逐渐从0,其中包括许多迭代,广泛的计算,和重建时间长。提出了几种改进桑普算法(18- - - - - -20.]。加快重建速度,我们开发了一个稀疏的概况自适应匹配追踪(SPAMP)算法。首先,概况稀疏接近真正的稀疏。然后桑普算法重构信号。

的主要贡献是双重的:(1)提出了一种新的稀疏preestimation稀疏估算方法快速、准确。方法使用标准的稀疏低估和高估估计稀疏。(2)我们开发了一种改进的桑普算法,称为SPAMP。在第一阶段,由稀疏preestimation稀疏估计标准。在第二阶段,桑普用于重建信号。实验仿真表明,重建SPAMP性能几乎一样桑普算法,而运行速度明显快于桑普的算法。

本文的其余部分组织如下。节2介绍了压缩传感理论。部分3给出了标准稀疏的低估和高估。部分4解释了该算法。部分5说明了仿真结果。最后,我们得出本文的总结部分6。

符号。黑体大写字母符号表示矩阵,粗体小写字母代表向量。表示两个向量的内积;是一个向量的规范;的振幅是一个复杂的数量或一组的基数;是一个向量或矩阵的转置;表示实数领域; 代表一个高斯随机变量和的意思和方差 。

2。压缩传感

让是一个真正的信号的长度 ,也就是说, 。如果一个信号只有非零元素,我们可以说是 - - - - - -稀疏。一个测量向量计算使用 矩阵 ;也就是说, 在测量向量 和测量矩阵 。测量矩阵必须允许重建的长度-信号从测量(测量向量 )。自 ,这个问题似乎是坏脾气的。然而,如果众所周知,这个信号只有提供非零项,问题可以解决 。稳定的恢复过程提出了(21)表明,测量矩阵满足限制等容属性(RIP)如果存在 这样 成立。RIP是确保每一对的列是互相正交高概率。研究表明,测量矩阵的条目采样来自哪里 , ,极有可能满足RIP (22,23]。

重建原始信号的观测信号可以转换成最小的规范的解决

不幸的是,解决(3)是一个np难问题,需要一个详尽的列举可能的非零项的位置 。考虑到噪声的影响,优化问题(3)进一步成为 在哪里是一种微细。这种方法可以获得更快的速度为代价的重建精度。

规范优化相当于规范优化裂缝条件下;也就是说,

规范优化可以使用标准的凸优化方法来解决问题。该方法具有良好的重建精度高时间复杂度。

3所示。标准的稀疏Preestimation

稀疏的方法低估给出了一套具体的原子(24)为我们提供了一个解决方案。快速而准确地估计稀疏,稀疏低估和高估方法在这一节中。

符号。和分别表示概况稀疏和真正的稀疏。 表示测量矩阵的内积和测量向量 。 表示 - - - - - -th进入向量 。集由的最大元素的索引 ,和 。真正支持的信号是 ,和 。

3.1。标准的稀疏低估

命题1。假设满足RIP与 。如果 ,然后 。

证明。假设估计稀疏大于或等于真正的贫乏 ;也就是说, 。这意味着 。很明显, 是满意的。此外,由于 ,我们获得 基于RIP的奇异值在于 。让表示的特征值 ,我们有 。因此,我们可以获得 自 ,这个收益率 从(6)- (8),我们可以获得 完成证明。
匡威负命题的命题1,我们可以得到稀疏的标准低估。

假设满足RIP与 。如果 ,然后估计稀疏小于真实的稀疏;也就是说, 。

3.2。稀疏的标准过高

命题2。假设满足RIP与 。如果 ,然后 。

证明。假设估计稀疏小于或等于真正的贫乏 ;也就是说, 。这意味着 。很明显, 是满意的;由于 ,我们可以得出结论, 基于RIP的定义,特征值的满足 。我们获得 自 ,我们有 结合(10)- (12),我们可以得到以下结果: 因此, 完成证明。
匡威负命题的命题2,我们获得稀疏的标准过高。

假设满足RIP与 。如果 ,然后 。

在下面,稀疏估计基于稀疏的标准低估和高估稀疏。这可以防止概况稀疏太小或太大,甚至超过真正的稀疏。

4所示。该算法

在本节中,稀疏的实施概况自适应匹配追踪(SPAMP)算法。图1显示了SPAMP算法的流程图。算法的实现步骤1如下。

桑普和SPAMP的计算复杂度和 ,分别。观察维度,稀疏信号的长度,和是桑普和SPAMP算法的迭代次数,分别。由于稀疏preestimation SPAMP算法,小于 。SPAMP低于桑普的计算复杂度。

5。仿真实验

来验证该算法的有效性,进行一系列的仿真实验。在接下来的实验中,一个 - - - - - -采用稀疏随机信号。实验环境是CPU i7 - 6700 u,主要频率为3.40 GHz, 16 G内存。

5.1。实验参数的选择

在SPAMP算法的第一阶段,稀疏概况。稀疏的性能preestimation取决于两个参数:弱匹配参数和评估因素 。估计的因素决定了稀疏估计的准确性。疲软的匹配参数是一个参数的函数 ,这决定了稀疏的快速估计。上述仿真实验得到的参数。

一维35-sparse随机信号生成长度为256。测量矩阵是一个 高斯矩阵。测量向量是计算 。首先,估计系数是固定的 ,和软弱的匹配参数的变化。仿真曲线的影响弱匹配参数在稀疏估计如图2。

从图可以看出2不同参数下的仿真结果当弱者匹配参数都是一样的在的范围 。结果表明,参数的变化不影响结果的稀疏preestimation。

为了验证估计的影响因素稀疏preestimation,疲软的匹配参数是固定在0.5,估计的因素的变化。仿真曲线的不同估计的影响因素在稀疏估计图所示3。

从图可以看出3有很大的影响,不同的评估因素稀疏preestimation。估计系数的增加 ,概况稀疏也在不断增加。估计系数等于0.2时,概况稀疏超过真正的稀疏信号。高估了稀疏会降低第二阶段的恢复质量,增加恢复时间。为了确保概况稀疏不超过真正的稀疏,估计的因素设置为0.15。在接下来的仿真实验,疲软的匹配参数0.5,估计因素呢是0.15。

5.2。一维信号的实验

在本节中,我们首先比较稀疏的影响和观察维度在重建概率,然后比较各算法的重建时间。

当是固定的,变化,重建概率进行比较。步骤大小S桑普和SPAMP 3、5和7。随机信号的长度是256,范围从观察维度 到160年。测量矩阵是一个 - - - - - -维高斯矩阵。观察维度分别是128年和160年。当重建信号与原始信号之间的误差小于 ,我们考虑到信号重建成功。重建概率是成功重建的数量比实验的数量。仿真结果如图4和5。

从数据可以看出4和5随着信号稀疏的增加,与已知的稀疏重建传统的概率算法迅速减少。稀疏超过40时,传统算法不能精确重构信号。桑普和SPAMP算法还可以有高概率重构信号。重建SPAMP算法的概率几乎是一样桑普算法。他们有明显的优势与其他传统算法相比,它需要知道稀疏。

当是固定的,变化,重建概率进行比较。步大小S桑普和SPAMP 3、5、7分别。测量矩阵是一个 - - - - - -维高斯矩阵。稀疏的分别是30到40。仿真曲线如图6和7。

从数据可以看出6和7当稀疏是固定的,与观察维度的增加,曲线的桑普和SPAMP上升得更快,而传统的曲线算法,需要知道稀疏上升慢。这表明,传统的算法有更高的要求,信号的稀疏,和稀疏信号的选择更严格。稀少无法满足需求时,压缩信号不能被重建。然而,桑普和SPAMP算法稀疏的要求相对较低。

当信号长度是256和观察维度是128,平均运行时的仿真曲线与稀疏图所示8。

从图我们可以得出这样的结论8SPAMP算法的运行速度比桑普的算法,和时间增加与传统的算法相比,它需要知道稀疏。在SPAMP算法,概况稀疏的过程需要一定的时间,然后是桑普算法重构信号。SPAMP算法的运行速度比桑普的算法,这表明概况稀疏可以有效地减少桑普算法的迭代次数。

对于一维信号的重建,我们可以通过上述实验得出以下结论:(1)大小是相同的,当一步重建提出SPAMP算法的概率是几乎一样的桑普算法,和运行速度明显快于桑普的算法。SPAMP算法的稀疏概况,然后信号被桑普重建与固定步长算法,重建质量不会显著提高,且仅可以提高运行速度。(2)我们注意到该SPAMP和桑普算法的运行速度低于OMP,玩耍,SP, CoSaMP, gOMP算法。主要原因是SPAMP和桑普算法采用一种试探性的方式逐步重构信号。如果这一步太大,重建概率将减少;如果步长太小,重建时间将会增加。与此同时其他算法提前知道信号稀疏;因此SPAMP和桑普算法在重建时间没有明显的优势。

5.3。二维图像的实验

验证的有效性提出SPAMP算法在二维图像重建,进行仿真实验在不同的压缩比。莉娜形象 在这个实验中使用像素。因为图像是nonsparse信号,小波变换矩阵是用来获得稀疏信号。峰值信噪比(PSNR)和重建时间用于评估性能。PSNR (dB)和重建时间的不同算法如表所示1。

从表可以看出1随着压缩比的增加,PSNR值不同的算法也会增加。当SPAMP和桑普算法采用相同的步长和压缩比,SPAMP演算法的PSNR值略高于桑普的算法。同时,我们注意到SPAMP算法有效地减少了重建时间。实验结果表明,该SPAMP算法减少了重建时间和略提高重建质量。

二维图像重建的信号,我们可以得出以下结论:(1)在PSNR值,提出SPAMP算法比OMP, SP,闹剧算法和略优于桑普算法。在重建时间,SPAMP的速度明显快于桑普的算法。SPAMP算法,第一阶段的稀疏概况,并且,在第二阶段,桑普的信号重构算法。步长以来SPAMP桑普是一样的,它的质量是局限于桑普。(2)随着压缩比的增加,所有算法的PSNR和重建时间增加。压缩比的增加,也就是说,观察维度的增加,必然会导致重建质量的提高和重建时间的增加。

6。结论

提出了一种改进稀疏自适应匹配追踪算法。在第一阶段,SPAMP算法预测稀疏。在第二阶段,桑普算法采用重建信号。通过一维信号和二维图像的比较,可以看出SPAMP算法几乎相同的重建质量桑普算法,重建时间大大减少,和重建质量优于OMP,玩耍,SP算法。自从SPAMP算法可以重构信号不知道稀疏,它比经济更实用,玩耍,和其他算法。

数据可用性

使用的数据来支持本研究的发现可以从相应的作者。

的利益冲突

作者宣称没有利益冲突有关的出版。

确认

这项工作是辽宁省博士科研基金(批准号2020 - bs - 225)和优秀的人才培训计划的辽宁科技大学(批准号2017 rc10)。

引用

1. y . c .灵族和g . Kutyniok压缩传感:理论和应用程序英国剑桥,剑桥大学出版社,2012年。
2. d . l . Donoho“压缩传感,”IEEE信息理论,52卷,不。4、1289 - 1306年,2006页。视图:出版商的网站|谷歌学术搜索
3. l·李·d·李,“稀疏阵SAR三维图像连续场景基于压缩传感、”电子与信息技术杂志》上,36卷,不。9日,第2172 - 2166页,2014年。视图:谷歌学术搜索
4. f·s . Li k . Liu, l·肖和d·汉”红外远程视频凝视图像基于压缩传感网络稀疏,”《电子学报》,43卷,不。3、518 - 522年,2015页。视图:谷歌学术搜索
5. j . s . Li Yang W陈,x,“雷达成像技术的概述及应用基于压缩传感理论,“电子与信息技术杂志》上,38卷,不。2、495 - 508年,2016页。视图:出版商的网站|谷歌学术搜索
6. c·a·罗杰斯和d . c . Popescu“压缩传感MIMO雷达扩展目标探测系统,”IEEE系统杂志,15卷,不。1,第1389 - 1381页,2021。视图:出版商的网站|谷歌学术搜索
7. w·h . Wang, x,, y,“稀疏自适应压缩传感重建架构基于reed-solomon代码,”IEEE通信信,25卷,不。3、716 - 720年,2021页。视图:出版商的网站|谷歌学术搜索
8. i . w . Selesnick和Bayram,“稀疏信号估计的最大稀疏凸优化、”IEEE信号处理,卷62,不。5,1078 - 1092年,2014页。视图:出版商的网站|谷歌学术搜索
9. r . g . Baraniuk e .萤石m·兰德和y易马,“稀疏表示和压缩感知的应用(扫描的问题),”IEEE学报》,卷98,不。6,906 - 909年,2010页。视图:出版商的网站|谷歌学术搜索
10. j . a . Tropp和a·c·吉尔伯特”通过正交匹配追踪信号恢复从随机测量,”IEEE信息理论,53卷,不。12日,第4666 - 4655页,2007年。视图:出版商的网站|谷歌学术搜索
11. y . c . Pati r . Rezaiifar, p . s . Krishnaprasad“正交匹配追踪:递归函数近似应用小波分解,”学报》27日艾斯洛玛尔会议信号,系统和电脑页,40-44太平洋格罗夫、钙、美国,1993年11月。视图:出版商的网站|谷歌学术搜索
12. d . Needell和r . Vershynin”统一的不确定性原理和通过正则化正交匹配追踪信号恢复,”计算数学基础,9卷,不。3、317 - 334年,2009页。视图:出版商的网站|谷歌学术搜索
13. d . Needell和j . a . Tropp CoSaMP:迭代信号恢复不完整和不准确的样本,”应用和计算谐波分析,26卷,不。3、301 - 321年,2009页。视图:出版商的网站|谷歌学术搜索
14. w·戴和o . Milenkovic压缩传感信号子空间追求重建。”IEEE信息理论,55卷,不。5,2230 - 2249年,2009页。视图:出版商的网站|谷歌学术搜索
15. 美国Kwon j . Wang,垫片,“广义正交匹配追踪,”IEEE信号处理,60卷,不。12日,第6216 - 6202页,2012年。视图:出版商的网站|谷歌学术搜索
16. d . l . Donoho y Tsaig,德,和J.-L。斯塔克,”稀疏欠定线性方程组的解在舞台上正交匹配的追求,“IEEE信息理论,卷。58岁的没有。2、1094 - 1121年,2012页。视图:出版商的网站|谷歌学术搜索
17. t . d .丁字裤,g, n .南和d . t . Trac,“稀疏自适应匹配追踪算法实际压缩传感,”学报2008年第42艾斯洛玛尔会议信号,系统和电脑太平洋格罗夫,页581 - 587年,CA,美国,2008年10月。视图:出版商的网站|谷歌学术搜索
18. r . Shoitan z Nossair,易卜拉欣,和a . Tobal”提高稀疏重建效率的自适应匹配威尔金森矩阵的基础上,追求“前沿的信息技术和电子工程,19卷,不。4、503 - 512年,2018页。视图:出版商的网站|谷歌学术搜索
19. x Bi, z商、z羌族和h . Liu”改进稀疏自适应匹配追求基于变量的迭代步骤,”系统仿真学报,26卷,不。9日,第2121 - 2116页,2014年。视图:谷歌学术搜索
20. r·杨和x张”,一种改进稀疏自适应匹配追踪算法基础上,“南京大学学报(自然科学),54卷,不。3、538 - 542年,2018页。视图:谷歌学术搜索
21. s . Foucart“硬阈值的追求:一个算法压缩传感、”暹罗在数值分析》杂志上卷,49号6,2543 - 2563年,2011页。视图:出版商的网站|谷歌学术搜索
22. C.-M。Yu工程学系。谢长廷,H.-W。梁et al .,“压缩传感探测器设计空间移键控在MIMO系统中,“IEEE通信信,16卷,不。10日,1556 - 1559年,2012页。视图:出版商的网站|谷歌学术搜索
23. e . j .萤石和t .道,“由线性规划译码,”IEEE信息理论,51卷,不。12日,第4215 - 4203页,2005年。视图:出版商的网站|谷歌学术搜索
24. c .杨w·冯·h·冯,t·杨和h波,“压缩采样稀疏自适应子空间追踪算法,”《电子学报》,38卷,不。8,1914 - 1917年,2010页。视图:谷歌学术搜索

版权

版权©2021新河Zhang et al。这是一个开放的分布式下文章知识共享归属许可,它允许无限制的使用、分配和复制在任何媒介,提供最初的工作是正确引用。