论文部分内容阅读
摘要：针对未知稀疏度信号重构和欠估计或过估计问题，在SAMP算法基础上提出了一种改进的变步长稀疏自适应正则化匹配追踪算法。首先利用原子匹配测试法得到稀疏度的初始估计，随后根据变步长分阶段思想和改进的抛物线型函数设计步长，利用大步长和小步长相结合的方式提高重构精度，最后根据测量向量与信号能量比率来设定阈值，最终重建信号。实验表明，该算法在解决欠估计或过估计问题上起到了很大的作用，未知稀疏信号的重建精度较高且效率较高。
关键词：贪婪算法；稀疏自适应；变步长；正则回溯；SAMP算法
中图分类号：TP391 文献标识码：A 文章编号：1009-5039（2018）16-0251-02
A Modified Variable Step Size Sparsity Adaptive Regularized Matching Pursuit Algorithm
SUN Run-run
（College of Computer Science and Engineering， Anhui University of Science and Technology， Huainan 232001， China）
Abstract： For solving the problem of unknown sparsity signal reconstruction and underestimation or over estimation， a modified variable step size adaptive regularized matching pursuit algorithm is proposed on the basis of sparse adaptive matching pursuit algorithm. Firstly， the algorithm uses the method of atomic matching test to get the initial estimation. Then an improved parabolic function is used to design the step length. Finally，the the ratio of measurement vector’s energy and the reconstruction signal’s energy is used to set the threshold. The experiment shows that the algorithm solves the problem caused by unsuitable selection of fixed step length， and realizes the accurate reconstruction of the unknown sparsity signal.
Key words： greedy algorithm；sparse adaptive； variable step size；regularized backtracking；SAMP algorithm
1 引言
近几年来，Donoho，Cande和Tao等人提出了一种崭新的信号采样处理理论，即压缩感知理论。该理论研究表明，如果信号是稀疏的或在某一个稀疏域是稀疏的，那么可以通过低于甚至远低于奈奎斯特采样标准对其实现采样压缩并用的模式，可精确地实现原始信号重建。既节约了硬件资源，又节约了运算成本和存储空间[1]。
重构是压缩感知理论研究的是重要的组成部分，使用低维数据以高精度的方法重构出高维数据是研究人员研究的重点。对于稀疏性或某一稀疏域上稀疏的信号重构算法的研究主要集中于组合算法、凸优化算法和贪婪迭代算法[2]。组合算法是将非凸问题转化成凸问题，运行效率高但计算复杂度大，应用不广泛。贪婪追踪算法在减少采样频率的同时增加运行效率，因为其计算复杂度低，重构效果好且计算结构简单，与其他两种算法相比应用广泛。针对未知稀疏度信号的重构，本文在研究上述算法基础上，提出一种改进的变步长稀疏自适应正则化匹配追踪算法。仿真实验表明，本文算法重构精度较高，性能优于SAMP算法且应用范围更广。
2 改进的变步长稀疏自适应正则化匹配追踪算法
2.1 算法描述
2.1.1 稀疏度估计
由于选择合适的初始稀疏估计值能减少算法运行时间，提高运行精度，本文使用原子匹配测试方式计算出初始稀疏度估计值，该稀疏估计值即为初始固定步长，其中估计值小于且接近K值，然后得到一个假定支撑集，其原子个数略小于稀疏度K。
文献[3]和[4]证明了命题“设如果测量矩阵满足RIP有限等距性质，如果[ΦTF0y2≤1-δk1 δky2]，则K0[≤]K”是真命题。利用该命题可以获取合适的初始稀疏值K0。具体方法为：设置K0初始值，如果满足上述公式，则K0自增直到不等式成立，此时K0为K的初始估计。
2.1.2 步长选择
本文算法突破了传统的匹配追踪中需要稀疏度已知的局限，即实现稀疏度自适应，通过在迭代过程中逐渐改变步长，逼近稀疏度K。变步长分阶段思想使得在增加重构精度的同时减小运算时间。而当支撑集原子个数不断增加的过程中，原始信号的能量差在相邻阶段是先不断减小在趋于平稳，根据这一规律来进行步长的函数选择。步长的大小选择也是至关重要的，步长过小可能会导致迭代次数过大且运算时间增大，引起过估计问题；步长过大可能会导致重构精度不高或欠估计问题，因此在变步长稀疏自适应追踪算法中固定步长的选择至关重要。
对比文献[5]的对数型和抛物线型稀疏度自适应匹配追踪算法，比较其中使用的步长设计公式，可以看出拋物线函数在初始阶段的变化率大于对数函数。大的变化率可以进一步加大初始阶段的步长，可以更快速地接近稀疏度，所以抛物线步长有效解决了“大步长”阶段步长变化小的问题，能够获得比对数型更优越。在抛物线型平方根和立方根函数中，由于后者在步长上升阶段变化率大，在步长减小的阶段变化率更平缓。所以设计步长S如下：[S（x）=ax3 b]，Stage为总阶段数，a和b为参数。再根据x为1时步长为初始步长S0，x为总阶段数时步长为N。即可得出a、b。文献[6]中定义相邻阶段重建信号能量差的斜率为R：阶段能量差除以阶段值。设置阈值R1、R2。迭代过程分为两部分：当R>R1时，[S（x）=N-S0Stage3-1N xN-X3 S0Stage3-NStage3-1]将能量快速下降的过程定义为大步长阶段，采用大步长快速逼近，可减少迭代次数和运算时间。当R2 定义 X为原始稀疏信号，Y为测量向量，如果观测矩阵满足有限等距性质，得到测量向量与稀疏信号能量比率的范围（0.63，1.307）。
证明：文献[7]和[8]给出证明过程。如果保证测量矩阵和变换基不相干，则传感矩阵满足有限等距性质。在信号重建过程中，根据该能量比率设定步长阶段的阈值。
2.2 算法的步骤
输入：观测值y，观测矩阵，初始步长S0。输出：x的近似稀疏解。初始化残差为y，支撑集为空， K0=1。
1）稀疏度估计：集合U为观测矩阵和y的内积绝对值，取U中前K0个子集。判断是否满足估计公式，如果结果为真，则K0增1，反之K0为所求的稀疏度
估计，即为初始步长。其中K0为接近且小于K的值。即为初始步长。
2）计算内积，并将L个最大原子存入S；得到候选支撑集Ck；
3）正则化：选择S对应的向量Xs。找出所有S的子集，使得所有的列向量满足[xm≤2xn]，选择具有最大能量的集合Si。
4）合并集合F和S，更新残差r。
5）如果R>R1，继续步骤g，反之继续步骤f。
6） 如果R2 7）如果R 8） 如果测量向量与稀疏信号能量比率大于1.38，进入“大步长”阶段，Stage自增1，根据公式计算新步长step，并更新步长L，t自增1，转至步骤b；反之继续步骤h。
9） 更新残差，t自增，保存集合，转至步骤b。
3 总结
压缩感知理论一经提出就引起广泛关注，基于压缩感知的应用层出不穷，解决了数据采样、传输和存储等诸多问题，为很多领域都带来了技术革新。不仅是在信号/图像处理领域，也分布在医疗成像、射电天文、模式识别、光学/雷达成像、信道编码等诸多领域。压缩感知与传统采样有很大不用，包括非直接采样、非均匀采样、通过稀疏性决定采样个数等。压缩感知主要理论关键点在于稀疏基、采样矩阵设计理论、范数最小化和低维观测和信号重构算法。当前压缩感知理论研究的重难点主要是信号重构，改进重构算法也是本文的研究核心。
在稀疏自适应匹配追踪算法迭代过程中，由于使用固定步长且步长选择不当导致的过估计或欠估计问题。针对该问题，根据原始信号的能量差在相邻阶段是先不断减小在趋于平稳的规律，即初始阶段变化率大，随后趋于平稳。本文在抛物线型步长选择方式的基础之上进行改进，选择不同的抛物线函数，利用抛物线变化率先大后小的趋势选择步长，并设置双阈值限定步长阶段，后根据测量向量和原始信号的能量比率为迭代条件，提出了一种改进的变步长稀疏自适应正则化匹配追踪算法。实验结果表明，该算法的重建效果较为突出，重建精度较高。
参考文献：
[1] DonohoD L. Compressed sensing[J]. IEEETransactions on Information Theory， 2006， 52（4）：1289-1306.
[2] Varadarajan B， Khudanpur S， Tran T D. Stepwise optimal subspace pursuit for improving sparse recovery[J]. IEEE Signal Processing Letters， 2010， 18（1）：27-30.
[3] 杨成， 冯巍， 冯辉，等. 一种压缩采样中的稀疏度自适应子空间追踪算法[J]. 电子学报， 2010， 38（8）：1914-1917.
[4] 朱延万， 赵拥军， 孙兵. 一种改进的稀疏度自适应匹配追踪算法[J]. 信号处理， 2012， 28（1）：80-86.
[5] 毕学霞， 尚振宏， 强振平，等. 一种基于变步长的稀疏度自适应匹配追踪算法[J]. 系统仿真学报， 2014， 26（9）：2116-2120.
[6] 杜秀丽， 胡興， 顾斌斌， 等. 基于变步长的正则回溯 SAMP 压缩感知重构算法[J/OL]. [2017-03-31]. http：//www.arocmag.com/article/02-2018-04-010.html.
[7] 李保珠， 邵建华， 聂梦雅，等. 基于能量的稀疏自适应匹配追踪算法[J]. 计算机应用与软件， 2015， 32（11）：121-125.
[8] Cai T T， Wang L， Xu G. New Bounds for Restricted Isometry Constants[J]. IEEE Transactions on Information Theory It， 2009， 56（9）：4388-4394.
关键词：贪婪算法；稀疏自适应；变步长；正则回溯；SAMP算法
中图分类号：TP391 文献标识码：A 文章编号：1009-5039（2018）16-0251-02
A Modified Variable Step Size Sparsity Adaptive Regularized Matching Pursuit Algorithm
SUN Run-run
（College of Computer Science and Engineering， Anhui University of Science and Technology， Huainan 232001， China）
Abstract： For solving the problem of unknown sparsity signal reconstruction and underestimation or over estimation， a modified variable step size adaptive regularized matching pursuit algorithm is proposed on the basis of sparse adaptive matching pursuit algorithm. Firstly， the algorithm uses the method of atomic matching test to get the initial estimation. Then an improved parabolic function is used to design the step length. Finally，the the ratio of measurement vector’s energy and the reconstruction signal’s energy is used to set the threshold. The experiment shows that the algorithm solves the problem caused by unsuitable selection of fixed step length， and realizes the accurate reconstruction of the unknown sparsity signal.
Key words： greedy algorithm；sparse adaptive； variable step size；regularized backtracking；SAMP algorithm
1 引言
近几年来，Donoho，Cande和Tao等人提出了一种崭新的信号采样处理理论，即压缩感知理论。该理论研究表明，如果信号是稀疏的或在某一个稀疏域是稀疏的，那么可以通过低于甚至远低于奈奎斯特采样标准对其实现采样压缩并用的模式，可精确地实现原始信号重建。既节约了硬件资源，又节约了运算成本和存储空间[1]。
重构是压缩感知理论研究的是重要的组成部分，使用低维数据以高精度的方法重构出高维数据是研究人员研究的重点。对于稀疏性或某一稀疏域上稀疏的信号重构算法的研究主要集中于组合算法、凸优化算法和贪婪迭代算法[2]。组合算法是将非凸问题转化成凸问题，运行效率高但计算复杂度大，应用不广泛。贪婪追踪算法在减少采样频率的同时增加运行效率，因为其计算复杂度低，重构效果好且计算结构简单，与其他两种算法相比应用广泛。针对未知稀疏度信号的重构，本文在研究上述算法基础上，提出一种改进的变步长稀疏自适应正则化匹配追踪算法。仿真实验表明，本文算法重构精度较高，性能优于SAMP算法且应用范围更广。
2 改进的变步长稀疏自适应正则化匹配追踪算法
2.1 算法描述
2.1.1 稀疏度估计
由于选择合适的初始稀疏估计值能减少算法运行时间，提高运行精度，本文使用原子匹配测试方式计算出初始稀疏度估计值，该稀疏估计值即为初始固定步长，其中估计值小于且接近K值，然后得到一个假定支撑集，其原子个数略小于稀疏度K。
文献[3]和[4]证明了命题“设如果测量矩阵满足RIP有限等距性质，如果[ΦTF0y2≤1-δk1 δky2]，则K0[≤]K”是真命题。利用该命题可以获取合适的初始稀疏值K0。具体方法为：设置K0初始值，如果满足上述公式，则K0自增直到不等式成立，此时K0为K的初始估计。
2.1.2 步长选择
本文算法突破了传统的匹配追踪中需要稀疏度已知的局限，即实现稀疏度自适应，通过在迭代过程中逐渐改变步长，逼近稀疏度K。变步长分阶段思想使得在增加重构精度的同时减小运算时间。而当支撑集原子个数不断增加的过程中，原始信号的能量差在相邻阶段是先不断减小在趋于平稳，根据这一规律来进行步长的函数选择。步长的大小选择也是至关重要的，步长过小可能会导致迭代次数过大且运算时间增大，引起过估计问题；步长过大可能会导致重构精度不高或欠估计问题，因此在变步长稀疏自适应追踪算法中固定步长的选择至关重要。
对比文献[5]的对数型和抛物线型稀疏度自适应匹配追踪算法，比较其中使用的步长设计公式，可以看出拋物线函数在初始阶段的变化率大于对数函数。大的变化率可以进一步加大初始阶段的步长，可以更快速地接近稀疏度，所以抛物线步长有效解决了“大步长”阶段步长变化小的问题，能够获得比对数型更优越。在抛物线型平方根和立方根函数中，由于后者在步长上升阶段变化率大，在步长减小的阶段变化率更平缓。所以设计步长S如下：[S（x）=ax3 b]，Stage为总阶段数，a和b为参数。再根据x为1时步长为初始步长S0，x为总阶段数时步长为N。即可得出a、b。文献[6]中定义相邻阶段重建信号能量差的斜率为R：阶段能量差除以阶段值。设置阈值R1、R2。迭代过程分为两部分：当R>R1时，[S（x）=N-S0Stage3-1N xN-X3 S0Stage3-NStage3-1]将能量快速下降的过程定义为大步长阶段，采用大步长快速逼近，可减少迭代次数和运算时间。当R2
证明：文献[7]和[8]给出证明过程。如果保证测量矩阵和变换基不相干，则传感矩阵满足有限等距性质。在信号重建过程中，根据该能量比率设定步长阶段的阈值。
2.2 算法的步骤
输入：观测值y，观测矩阵，初始步长S0。输出：x的近似稀疏解。初始化残差为y，支撑集为空， K0=1。
1）稀疏度估计：集合U为观测矩阵和y的内积绝对值，取U中前K0个子集。判断是否满足估计公式，如果结果为真，则K0增1，反之K0为所求的稀疏度
估计，即为初始步长。其中K0为接近且小于K的值。即为初始步长。
2）计算内积，并将L个最大原子存入S；得到候选支撑集Ck；
3）正则化：选择S对应的向量Xs。找出所有S的子集，使得所有的列向量满足[xm≤2xn]，选择具有最大能量的集合Si。
4）合并集合F和S，更新残差r。
5）如果R>R1，继续步骤g，反之继续步骤f。
6） 如果R2
9） 更新残差，t自增，保存集合，转至步骤b。
3 总结
压缩感知理论一经提出就引起广泛关注，基于压缩感知的应用层出不穷，解决了数据采样、传输和存储等诸多问题，为很多领域都带来了技术革新。不仅是在信号/图像处理领域，也分布在医疗成像、射电天文、模式识别、光学/雷达成像、信道编码等诸多领域。压缩感知与传统采样有很大不用，包括非直接采样、非均匀采样、通过稀疏性决定采样个数等。压缩感知主要理论关键点在于稀疏基、采样矩阵设计理论、范数最小化和低维观测和信号重构算法。当前压缩感知理论研究的重难点主要是信号重构，改进重构算法也是本文的研究核心。
在稀疏自适应匹配追踪算法迭代过程中，由于使用固定步长且步长选择不当导致的过估计或欠估计问题。针对该问题，根据原始信号的能量差在相邻阶段是先不断减小在趋于平稳的规律，即初始阶段变化率大，随后趋于平稳。本文在抛物线型步长选择方式的基础之上进行改进，选择不同的抛物线函数，利用抛物线变化率先大后小的趋势选择步长，并设置双阈值限定步长阶段，后根据测量向量和原始信号的能量比率为迭代条件，提出了一种改进的变步长稀疏自适应正则化匹配追踪算法。实验结果表明，该算法的重建效果较为突出，重建精度较高。
参考文献：
[1] DonohoD L. Compressed sensing[J]. IEEETransactions on Information Theory， 2006， 52（4）：1289-1306.
[2] Varadarajan B， Khudanpur S， Tran T D. Stepwise optimal subspace pursuit for improving sparse recovery[J]. IEEE Signal Processing Letters， 2010， 18（1）：27-30.
[3] 杨成， 冯巍， 冯辉，等. 一种压缩采样中的稀疏度自适应子空间追踪算法[J]. 电子学报， 2010， 38（8）：1914-1917.
[4] 朱延万， 赵拥军， 孙兵. 一种改进的稀疏度自适应匹配追踪算法[J]. 信号处理， 2012， 28（1）：80-86.
[5] 毕学霞， 尚振宏， 强振平，等. 一种基于变步长的稀疏度自适应匹配追踪算法[J]. 系统仿真学报， 2014， 26（9）：2116-2120.
[6] 杜秀丽， 胡興， 顾斌斌， 等. 基于变步长的正则回溯 SAMP 压缩感知重构算法[J/OL]. [2017-03-31]. http：//www.arocmag.com/article/02-2018-04-010.html.
[7] 李保珠， 邵建华， 聂梦雅，等. 基于能量的稀疏自适应匹配追踪算法[J]. 计算机应用与软件， 2015， 32（11）：121-125.
[8] Cai T T， Wang L， Xu G. New Bounds for Restricted Isometry Constants[J]. IEEE Transactions on Information Theory It， 2009， 56（9）：4388-4394.