快速高效支撐集恢復(fù)算法

龍程，李健，李智

（四川大學(xué)電子信息學(xué)院，成都 610065）

0 引言

Candès等于2006年提出壓縮感知[1-2]（Compressed Sensing,CS），而后得到了快速發(fā)展。Mark A.Davenport等學(xué)者針對(duì)壓縮采樣得到的觀測數(shù)據(jù)進(jìn)行研究，分析壓縮采樣而不重構(gòu)信號(hào)，直接使用壓縮采樣得到的數(shù)據(jù)在基帶對(duì)信號(hào)進(jìn)行參數(shù)估計(jì)、特征分析等[3]，具有重要的研究價(jià)值和應(yīng)用前景。

Candès[4-5]等的開創(chuàng)性工作，他們證明了具有稀疏性或者可壓縮性的有限維信號(hào)，可以通過一定的非線性優(yōu)化方法從小規(guī)模隨機(jī)投影的值來恢復(fù)原始信號(hào)。壓縮感知在實(shí)際工程領(lǐng)域中有很多應(yīng)用，如亞奈奎斯特采樣系統(tǒng)[6]、壓縮成像系統(tǒng)[7]、壓縮傳感網(wǎng)絡(luò)[8]等。壓縮感知在模擬域雖然發(fā)展緩慢，但也取得了許多重要科研成果，例如Joel Tropp,Marco Duarte等人提出隨機(jī)解調(diào)器（Random Demodulator,RD）系統(tǒng)[10]并給出硬件實(shí)現(xiàn)[11]，Candès研究團(tuán)隊(duì)開發(fā)出 RMPI芯片[12-13]，M.Misha?li和Y.C.Eldar設(shè)計(jì)出調(diào)制寬帶轉(zhuǎn)換器[14-15]。

本文分析了壓縮感知理論的原理以及MWC(Mod?ulated Wideband Converter)的實(shí)現(xiàn)原理，基于對(duì)RMMV和RSMV算法的理解與分析，提出了兩種新的恢復(fù)算法：RMSP和RSSP，分別針對(duì)子頻帶數(shù)較多以及子頻帶數(shù)較少兩種情況來降低連續(xù)到有限（Continue To Fi?nite，CTF）模塊恢復(fù)時(shí)間，都跳過了特征值分解階段，實(shí)驗(yàn)表明，兩種算法在恢復(fù)時(shí)間和恢復(fù)成功率上得到了提高。

1 MWC系統(tǒng)

稀疏多帶信號(hào)在頻域[-fnyq/2,fnyq/2]是稀疏的，稀疏是指調(diào)制信號(hào)頻帶與整個(gè)寬帶頻譜相比只占用很小一部分。其中，fnyq是奈奎斯特頻率，fs是采樣率，fp=1/Tp，Tp是偽隨機(jī)信號(hào)Pi(t)周期。信號(hào)每個(gè)子頻帶帶寬小于BHz，且頻帶數(shù)為N（包括負(fù)頻帶），如圖1所示為N=4稀疏多帶信號(hào)頻譜圖。

圖1 稀疏多帶信號(hào)頻譜圖

1.1 MWC 采樣原理及過程

MWC系統(tǒng)框圖如圖2所示，整個(gè)系統(tǒng)由m個(gè)采樣通道構(gòu)成，信號(hào)x(t)通過功分器進(jìn)入m個(gè)不同采樣通道與各偽隨機(jī)信號(hào)pi(t)混頻，將信號(hào)子頻帶搬移到基帶，基帶更易于處理；然后通過低通濾波器，再以速率采樣，得到m個(gè)采樣序列。

圖2 MWC系統(tǒng)框圖

周期信號(hào)pi(t)傅里葉級(jí)數(shù)展開表示為其中cil為傅里葉系數(shù)，第i個(gè)通道混頻后信號(hào)傅里葉變換可化簡為：

則第i個(gè)通道混頻再采樣后得到的序列離散時(shí)間傅里葉變換可化簡為：

即原信號(hào)頻譜等分每一段長為fp的L(L=2L0+1)段加權(quán)和可以表示每個(gè)通道采樣值的離散時(shí)間傅里葉變換，其中式（2）中系數(shù)cil構(gòu)成矩陣C，m個(gè)通道的表示為m維列向量y(f)，原信號(hào)各個(gè)頻段X(f-lfp)表示為L維列向量z(f)，得出CS模型：

1.2 CTF 模塊分析

CTF恢復(fù)算法能夠視為式（3）中解稀疏解z?(f)的方法之一，

但是傳統(tǒng)CS恢復(fù)算法是處理單維測量向量Ax解稀疏解x?，這是一個(gè)亟待解決的問題。首先，將式（3）視為一個(gè)線性系統(tǒng)：

式（3）中自變量f為無限連續(xù)變量，為求解支撐集，首先建立一個(gè)矩陣V，將向量y(f)等效為有限維的矩陣V，即將無限測量向量（Infinite Measurement Vec?tor,IMV）模型轉(zhuǎn)換到多測量向量（Multiple Measurement Vector,MMV）模型，使得等式v(λ)=Cu(λ)的解u的支撐集與式y(tǒng)(f)=Cz(f)的解z(f)的支撐集相同，就可以用求解MMV模型的方法求解支撐集。證明矩陣V滿足以下等式：

u的支撐集與z(f)的支撐集相同。前兩個(gè)步驟統(tǒng)稱為CTF模塊，如圖3所示：

圖3 CTF模塊

2 RMSP和RSSP算法

RMMV和RSMV算法[16]都是在CTF模塊前端的觀測矩陣V上做改進(jìn)，在后端都是利用OMP算法進(jìn)行支撐集恢復(fù)，而OMP算法恢復(fù)過程中，需要做很多次的V與C列的內(nèi)積運(yùn)算，時(shí)間消耗比較大且復(fù)雜度較高。而子空間追蹤（SP）算法利用回溯思想使每次迭代選取的原子數(shù)目只有2K，在下次迭代中選擇更接近原信號(hào)的原子進(jìn)行替換，降低迭代次數(shù)，提高恢復(fù)效率，因此將SP算法運(yùn)用到RMMV和RSMV上是有顯著實(shí)際作用的。

2.1 RMSP 算法

RMSP算法核心是將采樣值矩陣y[n]與一個(gè)高斯隨機(jī)矩陣R相乘，得到一個(gè)新的觀測矩陣，不僅跳過特征值分解步驟，而且只要控制高斯隨機(jī)矩陣R的列數(shù)在較低水平，就能夠進(jìn)一步減少矩陣的列數(shù)，再引入SP算法，支撐集恢復(fù)時(shí)間大大減少。其壓縮感知模型如下：

C是m×L感知矩陣，y[n]是m×n矩陣，z[n]是L×n矩陣，R是一個(gè)n×d高斯隨機(jī)矩陣，n是采樣序列的個(gè)數(shù)，d是高斯隨機(jī)矩陣R的列數(shù)，也是得出的新觀測矩陣的列數(shù)。參數(shù)d是非常重要的，它不僅關(guān)系著支撐集恢復(fù)速度，還關(guān)系著支撐集恢復(fù)成功率。最后，通過得到的新觀測矩陣，利用SP算法恢復(fù)原信號(hào)頻譜支撐集。

2.2 RSSP算法

RSSP算法核心是將采樣值矩陣y[n]按行相加，得到一個(gè)新的觀測向量Y，其原理與RMSP算法類似，將新的多列觀測矩陣轉(zhuǎn)換為新的單列觀測向量，不僅跳過特征值分解步驟，觀測向量Y是單維的，再引入SP算法，同樣支撐集恢復(fù)時(shí)間大大降低。其壓縮感知模型如下：

其中，Y=[Y1,Y2,...,Ym]T，Z=[Z1,Z2,...,ZL]T。經(jīng)過矩陣變換之后支撐集不會(huì)發(fā)生變化，矩陣Z[n]是按行聯(lián)合K-稀疏的，因此當(dāng)i不在支撐集S中時(shí)，Zi=[zi1,zi2,...,zin]中全部值為 0，這時(shí)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]擴(kuò)展成實(shí)數(shù)矩陣模式，

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

將m個(gè)通道采樣數(shù)據(jù)全部相加，得到具體的矩陣形式，

定 義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算法恢復(fù)支持集并獲得更好的性能。

3 實(shí)驗(yàn)分析

對(duì)比實(shí)驗(yàn)是經(jīng)過蒙特卡洛方法統(tǒng)計(jì)得出，所用的原信號(hào)是調(diào)制寬頻窄帶信號(hào)x(t)，

為了仿真抗噪性能，實(shí)際原信號(hào)加入了高斯白噪聲，因此仿真信號(hào)為x(t)+w(t)，w(t)是高斯白噪聲。信噪比下恢復(fù)成功率實(shí)驗(yàn)采用頻帶數(shù)N=10，其能量系數(shù)為，時(shí)間延時(shí)為τi={0.4,0.7,0.2,0.3,0.5}；各通道數(shù)下恢復(fù)時(shí)間實(shí)驗(yàn)采用頻帶數(shù)N=6，其能量系數(shù)為，時(shí)間延時(shí)為0.2}，所有仿真中Ei和τi都是不變的。每個(gè)信號(hào)的載波頻率fi從[-fnyq/2,fnyq/2]中均勻隨機(jī)選擇，其中fnyq=10GHz，L=195是指采樣率的壓縮比。

3.1 RMSP 仿真實(shí)驗(yàn)

圖4（a）通道數(shù)m=50固定不變，給出了各恢復(fù)算法以及信噪比對(duì)恢復(fù)成功率的影響；圖4（b）信噪比SNR=30dB固定不變，給出了各恢復(fù)算法在各通道數(shù)下的恢復(fù)時(shí)間。

從圖4（a）中可以看出，在信噪比條件下，支撐集恢復(fù)率RMSP整體上都要優(yōu)于OMP，而RMMV比OMP還要差些；當(dāng)SNR<0時(shí)，RMSP恢復(fù)率不穩(wěn)定，當(dāng)SNR>5時(shí)，RMSP恢復(fù)率逐漸穩(wěn)定并接近于1；因此，RMSP算法在恢復(fù)成功率上得到了很大改進(jìn)。從圖4（b）中可以看出，RMSP和RMMV比OMP在恢復(fù)時(shí)間上都大大減少，當(dāng)通道數(shù)小于60時(shí)，RMSP比RMMV恢復(fù)時(shí)間還要少2~3ms，通道數(shù)大于60時(shí)，兩算法恢復(fù)時(shí)間相差不大；因此，RMSP算法在恢復(fù)時(shí)間上得到了改進(jìn)。

3.2 RSSP仿真實(shí)驗(yàn)

圖5（a）通道數(shù)m=50固定不變，給出了各恢復(fù)算法以及信噪比對(duì)恢復(fù)成功率的影響；圖5（b）信噪比SNR=30dB固定不變，給出了各恢復(fù)算法在各通道數(shù)下的恢復(fù)時(shí)間。

從圖 5（a）中可以看出，在信噪比條件下，當(dāng)SNR<10時(shí)，RSSP在支撐集恢復(fù)率上比OMP差些，但優(yōu)于RSMV；當(dāng)SNR>10時(shí)，RSSP要優(yōu)于OMP并接近于1，更比RSMV恢復(fù)率高接近10%；因此，RSSP算法在恢復(fù)成功率上得到了很大改進(jìn)。從圖5（b）中可以看出，RSSP和RSMV比OMP在恢復(fù)時(shí)間上都大大減少，當(dāng)通道數(shù)小于30時(shí)，RSSP和RSMV恢復(fù)時(shí)間差別不大，通道數(shù)大于30時(shí)，RSSP比RSMV恢復(fù)時(shí)間多10ms左右；因此，RSSP算法在恢復(fù)時(shí)間上得到了改進(jìn)。

圖4

圖5

4 結(jié)語

針對(duì)OMP算法恢復(fù)支撐集過程中計(jì)算速度較慢、復(fù)雜度較高問題，提出RMSP和RSSP算法。實(shí)驗(yàn)表明，這兩種算法不論在恢復(fù)時(shí)間上還是在恢復(fù)效率上都得到了很大改進(jìn)。今后，在成功恢復(fù)支撐集所需的最小通道數(shù)和信噪比等方面還存在改進(jìn)空間。

參考文獻(xiàn)：

[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.