一种改进的正则化自适应匹配追踪算法
王芳星;刘顺兰
【摘 要】针对压缩感知中未知稀疏度信号的重构问题，提出了一种改进的正则化自适应匹配追踪算法。它通过自适应变步长迭代对信号稀疏度进行估计，并将其作为初始支撑集长度，然后在分阶段迭代中正则化筛选原子，最终实现信号的精确重构。仿真结果表明，该算法重构信号的性能和效率均优于子空间追踪算法、正交匹配追踪算法和稀疏度自适应匹配追踪算法。%This paper presents a modified regularization adaptive matching pursuit ( MRAMP) algorithm for the problem that reconstruct signals with unknown sparsity in compressed sensing .The proposed algorithm adaptively estimates the sparsity with difference steps through stage by stage and set it to the length of the initial support , then gets the accurate target signal by regularization screening of atoms in every stage . Simulation results show that the performance and efficiency of the proposed algorithm is better than subspace pursuit(SP) algorithm, orthogonal matching pursuit(OMP) algorithm and SAMP algorithm.
【期刊名称】《杭州电子科技大学学报》
【年(卷),期】2015(000)001
【总页数】5页(P79-83)
【关键词】信号重构;压缩感知;稀疏度;自适应;正则化
【作 者】王芳星;刘顺兰
【作者单位】杭州电子科技大学通信工程学院，浙江杭州310018;杭州电子科技大学通信工程学院，浙江杭州310018
【正文语种】中 文
【中图分类】TN911.72
压缩感知(Compressive Sensing， CS)理论充分利用了信号的稀疏度来获取和处理信号[1]。重构算法是压缩感知理论的关键技术，其中贪婪算法结构简单，运算少，因此得到很好的运用。正交匹配追踪(Orthogonal Matching Pursuit，OMP)算法[2]是传统的贪婪算法，它在每次迭代中选取一个原子更新支撑集，效率较低。然而，正则化正交匹配追踪(Regularized Ort
hogonal Matching Pursuit， ROMP)算法[3]在每次迭代过程中选取多个支撑集原子重构信号，其重构速度比OMP算法快。之后出现的子空间追踪(Subspace Pursuit， SP)算法[4]引入了回溯思想，重构复杂度较低。但上述算法必须已知信号稀疏度，而稀疏度自适应匹配追踪(Sparsity Adaptive Matching Pursuit， SAMP)算法[5]不需要稀疏度作为先验信息。本文针对未知稀疏度信号的重构，将SAMP算法的自适应、SP算法的回退筛选和ROMP算法的正则化原子选择相结合，提出了一种改进的正则化自适应匹配追踪(MRAMP)算法并将其与OMP、SAMP和SP算法进行了性能比较。仿真结果表明，MRAMP算法对信号的重构性能和效率优于其它几种算法。
压缩感知理论的应用需要信号是稀疏或者近似稀疏的，设X是有限长离散时间信号，可看作空间RN内N×1维列向量，假定Ψ={ψ1，ψ2，...，ψN}是RN内一组标准正交基，则信号X可表示为：
式中，Ψ为N×N矩阵，α为投影系数[αi]=[〈X，ψi〉]构成的N×1维列向量。可见，X和α是同一个信号的不同表示。如果α中非零元素个数为K(K<<N)，则信号X是K-稀疏的。
设计一个与变换基不相关的M×N(M<N)维观测矩阵Φ，将信号X投影到矩阵Φ上得到M个测量
值组成的M×1维列向量Y：
式中，Θ=ΦΨ为M×N矩阵，称为恢复矩阵。
本文通过原子匹配测试的方法给出初始稀疏度的估计。下面先给出两个命题。
命题1　当Φ以参数(K，δK)满足约束等距性质(RIP)时，如果K0≥K，则2是真命题[6]。其中，K0表示估计的初始稀疏度，K表示真实稀疏度，F0表示Φ中与残差最匹配的K0个原子对应索引的集合，(·)T表示(·)的转置，ΦF0表示Φ中对应索引集F0的原子集合。
命题2　即命题1的逆否命题，当Φ以参数(K，δK)满足RIP性质时，如果，则K0≤K也是真命题[7]。
在SAMP算法中，初始稀疏度设为1或阶段步长取一个较小值，则需要多次匹配、更新、信号估计和残差更新，降低了算法效率。若初始稀疏度随便设为某一常数或取一个较大的阶段步长则会影响算法的精度。针对以上问题，根据命题2可不断增加K0的值来对稀疏度进行初始估计，当条件不满足时，K0为稀疏度初始估计值，同时可得到初始残差和初始阶段步长。
SP算法主要思想是回溯迭代，每次迭代首先计算残差r，然后选择观测矩阵Φ的各个原子φi中与残差最匹配的原子，得到相关系数u：
将u中最大值对应的索引S并入支撑集索引F，更新支撑集ΦF，并采用最小二乘法进行信号估计以及更新残差：
式中，为原始信号X的估计值，rnew为更新的残差值，F为ΦF的伪逆。
MRAMP算法不需要信号稀疏度为先验条件，它利用命题2得出信号稀疏度初始估计值K0并将其作为初始支撑集长度，同时得到初始阶段迭代步长变化值step和初始残差r。该算法沿用了SP算法的原子筛选思想，但其把每次迭代过程分成多个阶段并自动调整每次筛选原子数(size)。利用式(3)选取size个相关系数最大的原子对应的索引存入索引集S，根据不等式i，j∈S，将选出的size个相关系数分成若干组，选能量最大的一组对应原子的索引值存入S0中，完成正则化过程。然后将索引集S0并入当前支撑集索引，更新支撑集并根据式(4)估计信号，再选size个原子作为新的支撑集。下面给出MRAMP算法具体步骤。
输入：M维测量向量Y，M×N观测矩阵Φ，阶段迭代步长step≠0，δK。
1)初始稀疏度K0=1，稀疏度估计步长step1=step，索引集F0=∅，S=∅(空集)；
2)通过式(3)计算相关系数u，并从u中取出K0个最大值对应的索引值存入索引集F0中；
3)如果，则step1=step1，K0=K0+step1，转步骤2；
正则化参数的自适应估计
4)初始残差；
5)初始化阶段stage=1，初始化迭代次数n=1，初始阶段步长step=「0.5step1⎤，初始支撑集长度size=K0，索引集F=F0；
6)通过式(3)计算u，取出u中size个最大值对应的索引值存入S中；
7)将选出的size个相关系数进行正则化并将得到的索引值存入S0中，然后将S0并入索引集F，更新支撑集ΦF；
8)通过式(4)得到估计信号值，根据回溯思想，将中前size个最大元素所对应的索引值存入F中，其他元素设为零，更新支撑集ΦF；
9)通过式(4)得到信号估计，并通过式(5)更新残差rnew；
10)设定阀值ε，如果2≤ε，则停止迭代，否则转步骤11；
11)如果2，则stage=stage+1，step=「0.5step⎤，size=size+step，转步骤6；否则，r=rnew，n=n+1，转步骤6；
输出：信号X的K稀疏估计。
MRAMP算法流程图如图1所示，其前半部分是信号的稀疏度估计和迭代变量的初始化，后半部分是SAMP算法框架下的分阶段迭代，初始残差Y并且将稀疏度估计值作为初始支撑集长度弥补了稀疏度估计所需计算量，提高了执行效率。步骤10中前后两次信号估计值差小于阀值ε，则终止迭代，否则进入下一阶段。步骤11中的迭代步长是根据前5个步骤得出且每次迭代步长变化取前一阶段的一半，兼顾了重构效率和精度。MRAMP算法稀疏度估计部分的计算量主要是进行M次投影，运算量相对较小。整个算法的主要计算量是通过最小二乘法来估计信号，而采用初始稀疏度估计正好减少了SAMP算法前期迭代中信号估计次数，从而降低了计算复杂度。
为了说明MRAMP算法的正确性和有效性，本文采用正弦信号进行实验。
式中，f1=100 Hz，f2=200 Hz，f3=300 Hz，采样频率fs=800 Hz，ts=1/fs。测量向量长度M=64，原始信号长度N=256，观测矩阵Φ和稀疏变换矩阵Ψ分别取高斯随机矩阵和傅里叶变换矩阵。稀疏度估计步长step1=1，参数δK=0.35，ε=10-6。
MRAMP算法重构信号的仿真结果如图2所示，从图2可以看出该算法能够很好的重构原始信号，并且重构均方误差较小。
M取不同值时，各个算法300次重构实验的平均运行时间如图3所示。由图3可以看出，MRAMP算法的平均运行时间要明显少于OMP算法、SAMP算法和SP算法。
500次实验，MRAMP算法、OMP算法、SAMP算法和SP算法对信号准确重构率比较如图4所示。当信号与X中对应位置元素的误差能量小于某一给定的阀值[7]，则可认为信号对信号X能够准确重构，这里阈值取10-12。由图4可以看出信号准确重构概率随着采样点数M的增大而增大，M>36时几种算法均能准确重构信号。当10<M<36时，MRAMP算法重构效果明显优于其他算法。
测量向量长度M=64，高斯白噪声环境中，不同信噪比(Signal Noise Ratio， SNR)下各算法
对信号的重构概率如图5所示。由图5可知，各算法的准确重构概率随着信噪比的增大而增大，MRAMP算法的准确重构概率优于SP、OMP、SAMP算法，当信噪比大于10 dB时，所有算法均能准确重构信号。当信噪比为7 dB时，MRAMP、OMP、SAMP和SP算法的重构概率分别为0.780 0、0.720 0、0.594 0和0.682 0，表明同一信噪比下，MRAMP算法的重构概率高于其它几种算法。因此，在噪声环境下，MRAMP算法的重构性能优于OMP、SAMP和SP算法。
本文在已有的压缩感知重构算法研究的基础上，将信号的稀疏度估计、SAMP算法的自适应、SP算法的回退筛选和ROMP算法的正则化原子选择相结合，提出了MRAMP算法。算法通过原子匹配测试得出初始稀疏度作为初始支撑集长度和小能量残差作为初始残差，减少了整个算法迭代次数，使算法效率得到提高。在变步长分阶段迭代过程中逐渐减小迭代步长并利用正则化选取能量最大的原子来更新支撑集，从而更快更精确地逼近信号稀疏度，当前后两次估计信号的差值达到某一设定的阀值以下便能精确的重构未知稀疏度的信号。仿真结果表明，MRAMP算法重构性能和效率明显优于OMP、SAMP和SP算法。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。