快速高效支撑集恢复算法

龙程，李健，李智

（四川大学电子信息学院，成都 610065）

0 引言

Candès等于2006年提出压缩感知[1-2]（Compressed Sensing,CS），而后得到了快速发展。Mark A.Davenport等学者针对压缩采样得到的观测数据进行研究，分析压缩采样而不重构信号，直接使用压缩采样得到的数据在基带对信号进行参数估计、特征分析等[3]，具有重要的研究价值和应用前景。

Candès[4-5]等的开创性工作，他们证明了具有稀疏性或者可压缩性的有限维信号，可以通过一定的非线性优化方法从小规模随机投影的值来恢复原始信号。压缩感知在实际工程领域中有很多应用，如亚奈奎斯特采样系统[6]、压缩成像系统[7]、压缩传感网络[8]等。压缩感知在模拟域虽然发展缓慢，但也取得了许多重要科研成果，例如Joel Tropp,Marco Duarte等人提出随机解调器（Random Demodulator,RD）系统[10]并给出硬件实现[11]，Candès研究团队开发出 RMPI芯片[12-13]，M.Misha⁃li和Y.C.Eldar设计出调制宽带转换器[14-15]。

本文分析了压缩感知理论的原理以及MWC(Mod⁃ulated Wideband Converter)的实现原理，基于对RMMV和RSMV算法的理解与分析，提出了两种新的恢复算法：RMSP和RSSP，分别针对子频带数较多以及子频带数较少两种情况来降低连续到有限（Continue To Fi⁃nite，CTF）模块恢复时间，都跳过了特征值分解阶段，实验表明，两种算法在恢复时间和恢复成功率上得到了提高。

1 MWC系统

稀疏多带信号在频域[-fnyq/2,fnyq/2]是稀疏的，稀疏是指调制信号频带与整个宽带频谱相比只占用很小一部分。其中，fnyq是奈奎斯特频率，fs是采样率，fp=1/Tp，Tp是伪随机信号Pi(t)周期。信号每个子频带带宽小于BHz，且频带数为N（包括负频带），如图1所示为N=4稀疏多带信号频谱图。

图1 稀疏多带信号频谱图

1.1 MWC 采样原理及过程

MWC系统框图如图2所示，整个系统由m个采样通道构成，信号x(t)通过功分器进入m个不同采样通道与各伪随机信号pi(t)混频，将信号子频带搬移到基带，基带更易于处理；然后通过低通滤波器，再以速率采样，得到m个采样序列。

图2 MWC系统框图

周期信号pi(t)傅里叶级数展开表示为其中cil为傅里叶系数，第i个通道混频后信号傅里叶变换可化简为：

则第i个通道混频再采样后得到的序列离散时间傅里叶变换可化简为：

即原信号频谱等分每一段长为fp的L(L=2L0+1)段加权和可以表示每个通道采样值的离散时间傅里叶变换，其中式（2）中系数cil构成矩阵C，m个通道的表示为m维列向量y(f)，原信号各个频段X(f-lfp)表示为L维列向量z(f)，得出CS模型：

1.2 CTF 模块分析

CTF恢复算法能够视为式（3）中解稀疏解z͂(f)的方法之一，

但是传统CS恢复算法是处理单维测量向量Ax解稀疏解x͂，这是一个亟待解决的问题。首先，将式（3）视为一个线性系统：

式（3）中自变量f为无限连续变量，为求解支撑集，首先建立一个矩阵V，将向量y(f)等效为有限维的矩阵V，即将无限测量向量（Infinite Measurement Vec⁃tor,IMV）模型转换到多测量向量（Multiple Measurement Vector,MMV）模型，使得等式v(λ)=Cu(λ)的解u的支撑集与式y(f)=Cz(f)的解z(f)的支撑集相同，就可以用求解MMV模型的方法求解支撑集。证明矩阵V满足以下等式：

u的支撑集与z(f)的支撑集相同。前两个步骤统称为CTF模块，如图3所示：

图3 CTF模块

2 RMSP和RSSP算法

RMMV和RSMV算法[16]都是在CTF模块前端的观测矩阵V上做改进，在后端都是利用OMP算法进行支撑集恢复，而OMP算法恢复过程中，需要做很多次的V与C列的内积运算，时间消耗比较大且复杂度较高。而子空间追踪（SP）算法利用回溯思想使每次迭代选取的原子数目只有2K，在下次迭代中选择更接近原信号的原子进行替换，降低迭代次数，提高恢复效率，因此将SP算法运用到RMMV和RSMV上是有显著实际作用的。

2.1 RMSP 算法

RMSP算法核心是将采样值矩阵y[n]与一个高斯随机矩阵R相乘，得到一个新的观测矩阵，不仅跳过特征值分解步骤，而且只要控制高斯随机矩阵R的列数在较低水平，就能够进一步减少矩阵的列数，再引入SP算法，支撑集恢复时间大大减少。其压缩感知模型如下：

C是m×L感知矩阵，y[n]是m×n矩阵，z[n]是L×n矩阵，R是一个n×d高斯随机矩阵，n是采样序列的个数，d是高斯随机矩阵R的列数，也是得出的新观测矩阵的列数。参数d是非常重要的，它不仅关系着支撑集恢复速度，还关系着支撑集恢复成功率。最后，通过得到的新观测矩阵，利用SP算法恢复原信号频谱支撑集。

2.2 RSSP算法

RSSP算法核心是将采样值矩阵y[n]按行相加，得到一个新的观测向量Y，其原理与RMSP算法类似，将新的多列观测矩阵转换为新的单列观测向量，不仅跳过特征值分解步骤，观测向量Y是单维的，再引入SP算法，同样支撑集恢复时间大大降低。其压缩感知模型如下：

其中，Y=[Y1,Y2,...,Ym]T，Z=[Z1,Z2,...,ZL]T。经过矩阵变换之后支撑集不会发生变化，矩阵Z[n]是按行联合K-稀疏的，因此当i不在支撑集S中时，Zi=[zi1,zi2,...,zin]中全部值为 0，这时Zi=zi1+zi2+...+zin(1≤i≤L)等于 0，因此 supp(Z)=supp(z(Fp))，即支撑集不变。

令压缩采样值矩阵y[n]的第i行为yi[n](1≤i≤m)，将MMV压缩感知模型y[n]=Cz[n]扩展成实数矩阵模式，

将yi[n](1≤i≤m)相加，得到：

将m个通道采样数据全部相加，得到具体的矩阵形式，

定 义Yj=yj1+yj2+...+yjn(1≤j≤m)，Zj=zi1+zi2+...+zin(1≤i≤L)，得到：

这就是RSSP最终模型Y=CZ，其中Y=[Y1,Y2,...,Ym]T，Z=[Z1,Z2,...,ZL]T。RSMV得到的观测向量Y，同理，引入SP算法恢复支持集并获得更好的性能。

3 实验分析

对比实验是经过蒙特卡洛方法统计得出，所用的原信号是调制宽频窄带信号x(t)，

为了仿真抗噪性能，实际原信号加入了高斯白噪声，因此仿真信号为x(t)+w(t)，w(t)是高斯白噪声。信噪比下恢复成功率实验采用频带数N=10，其能量系数为，时间延时为τi={0.4,0.7,0.2,0.3,0.5}；各通道数下恢复时间实验采用频带数N=6，其能量系数为，时间延时为0.2}，所有仿真中Ei和τi都是不变的。每个信号的载波频率fi从[-fnyq/2,fnyq/2]中均匀随机选择，其中fnyq=10GHz，L=195是指采样率的压缩比。

3.1 RMSP 仿真实验

图4（a）通道数m=50固定不变，给出了各恢复算法以及信噪比对恢复成功率的影响；图4（b）信噪比SNR=30dB固定不变，给出了各恢复算法在各通道数下的恢复时间。

从图4（a）中可以看出，在信噪比条件下，支撑集恢复率RMSP整体上都要优于OMP，而RMMV比OMP还要差些；当SNR<0时，RMSP恢复率不稳定，当SNR>5时，RMSP恢复率逐渐稳定并接近于1；因此，RMSP算法在恢复成功率上得到了很大改进。从图4（b）中可以看出，RMSP和RMMV比OMP在恢复时间上都大大减少，当通道数小于60时，RMSP比RMMV恢复时间还要少2~3ms，通道数大于60时，两算法恢复时间相差不大；因此，RMSP算法在恢复时间上得到了改进。

3.2 RSSP仿真实验

图5（a）通道数m=50固定不变，给出了各恢复算法以及信噪比对恢复成功率的影响；图5（b）信噪比SNR=30dB固定不变，给出了各恢复算法在各通道数下的恢复时间。

从图 5（a）中可以看出，在信噪比条件下，当SNR<10时，RSSP在支撑集恢复率上比OMP差些，但优于RSMV；当SNR>10时，RSSP要优于OMP并接近于1，更比RSMV恢复率高接近10%；因此，RSSP算法在恢复成功率上得到了很大改进。从图5（b）中可以看出，RSSP和RSMV比OMP在恢复时间上都大大减少，当通道数小于30时，RSSP和RSMV恢复时间差别不大，通道数大于30时，RSSP比RSMV恢复时间多10ms左右；因此，RSSP算法在恢复时间上得到了改进。

图4

图5

4 结语

针对OMP算法恢复支撑集过程中计算速度较慢、复杂度较高问题，提出RMSP和RSSP算法。实验表明，这两种算法不论在恢复时间上还是在恢复效率上都得到了很大改进。今后，在成功恢复支撑集所需的最小通道数和信噪比等方面还存在改进空间。

参考文献：

[1]D.L.Donoho,Compressed sensing[J],IEEE Trans.Inf.Theory,Vol.52,No.4,April 2006,1289-1306.

[2]E.Candes,J.Romberg,T.Tao,Robust Uncertainty Principles:Exact Signal Reconstruction from Highly Incomplete Frequency Information[J].IEEE Trans.Inform.Theory,Vol.52,No.2,Feb.2006,489-509.

[3]Davenport M A,Boufounos P T,Wakin M B,et al.Signal Processing with Compressive Measurements[J].IEEE Journal of Selected Topics in Signal Processing,2010,4（2）:445-460.

[4]Candès E J.Compressive Sampling[J].Marta Sanz Solé,2006,17（2）:1433-1452.

[5]Candès E J,Romberg J K,Tao T.Stable Signal Recovery from Incomplete and Inaccurate Measurements[J].Communications on Pure&Applied Mathematics,2005,19（5）:410-412.

[6]Gedalyahu K,Eldar Y C.Time-Delay Estimation From Low-Rate Samples:A Union of Subspaces Approach[J].IEEE Transactions on Signal Processing,2010,58（6）:3017-3031.

[7]M.F.Duarte,M.A.Davenport,D.Takbar,et al.Single-Pixel Imaging Via Compressive Sampling[J].IEEE Signal Processing Magazine,2008,25（2）:83-91.

[8]Duarte M F,Sarvotham S,Baron D,et al.Distributed Compressed Sensing of Jointly Sparse Signals[C].Asilomar Conf.Signals,Sys.,Comput.2005:1537-1541.

[9]Tropp J A,Laska J N,Duarte M F,et al.Beyond Nyquist:Efficient Sampling of Sparse Bandlimited Signals[J].IEEE Transactions on Information Theory,2010,56（1）:520-544.

[10]Laska J N,Kirolos S,Duarte M F,et al.Theory and Implementation of an Analog-to-Information Converter using Random Demodulation[C].Circuits and Systems,2007.ISCAS 2007.IEEE International Symposium on.IEEE,1962:1959-1962.

[11]Becker S R,Candès E J,Grant M C.Templates for Convex Cone Problems with Applications to Sparse Signal Recovery[J].Mathematical Programming Computation,2010,3（3）:165-218.

[12]Becker S,Bobin J,Candès E J.NESTA:A Fast and Accurate First-order Method for Sparse Recovery[J].Siam Journal on Imaging Sciences,2009,4（1）:1-39.

[13]Mishali M,Eldar Y C.Reduce and Boost:Recovering Arbitrary Sets of Jointly Sparse Vectors[J].IEEE Transactions on Signal Processing,2008,56（10）:4692-4702.

[14]Mishali M,Eldar Y C,Dounaevsky O,et al.Sub-Nyquist Acquisition Hardware for Wideband Communication[C].Signal Processing Systems（SIPS）,2010 IEEE Workshop on.IEEE,2010:156-161.

[15]Cotter S F,Rao B D,Engan K,et al.Sparse Solutions to Linear Inverse Problems with Multiple Measurement Vectors[J].Signal Processing,IEEE Transactions on,2005,53（7）:2477-2488.

[16]Bo Yao,Zhi Li,Wei Hua,Bohua Deng.Efficient Recovery of Support Set in Modulated Wideband Converter System[J].Journal of Information and Computational Science,v 12,n 16,p 6043-6055,November 1,2015.