基于多觀測(cè)向量序列降采樣恢復(fù)的稀疏矩陣重構(gòu)

何興宇, 童寧寧, 胡曉偉, 馮為可

(空軍工程大學(xué)防空反導(dǎo)學(xué)院, 陜西 西安 710051)

0 引 言

壓縮感知(compressed sensing,CS)理論表明,大多數(shù)信號(hào)都有稀疏表示,這意味著信號(hào)可以通過(guò)少數(shù)信號(hào)在特定稀疏基下的系數(shù)來(lái)表示。稀疏信號(hào)可以通過(guò)遠(yuǎn)低于信號(hào)維度的觀測(cè)信號(hào)來(lái)重構(gòu)[1-2]。壓縮感知的核心問(wèn)題是:假設(shè)s是一個(gè)稀疏向量s∈Rn,通過(guò)觀測(cè)矩陣A∈Rm×n和觀測(cè)向量x=As來(lái)重構(gòu)稀疏信號(hào)s。當(dāng)m

由于目標(biāo)函數(shù)‖·‖0是非凸的,所以很難找到0范數(shù)優(yōu)化問(wèn)題的最優(yōu)解。一個(gè)比較有效的方法是,將上述0范數(shù)優(yōu)化問(wèn)題轉(zhuǎn)換為它的凸近似,也即1優(yōu)化問(wèn)題,進(jìn)而通過(guò)線性規(guī)劃來(lái)找到其最優(yōu)解。相比于0范數(shù)的優(yōu)化問(wèn)題,1范數(shù)優(yōu)化問(wèn)題表示的凸松弛問(wèn)題可以更為有效地得到解決,并且得到的最優(yōu)解與0范數(shù)優(yōu)化問(wèn)題一致。

很多基于單觀測(cè)向量的重構(gòu)算法可以拓展到多觀測(cè)向量問(wèn)題中。文獻(xiàn)[4]表明,正交匹配追蹤(orthogonal matching pursuit,OMP)算法在一定條件下可以找到多觀測(cè)向量重構(gòu)問(wèn)題的稀疏解,文獻(xiàn)[5]分析了該方法的性能。文獻(xiàn)[6]研究了FOCUSS(focal underdetermined system solver)算法的拓展算法,分別提出了MFOCUSS(FOCUSS for multiple measurement vectors)算法和正則化MFOCUSS算法,來(lái)解決無(wú)噪聲和有噪聲情況下的多觀測(cè)向量重構(gòu)問(wèn)題。文獻(xiàn)[7]將稀疏貝葉斯學(xué)習(xí)(sparse Bayesian learning,SBL)算法拓展到多觀測(cè)向量模型下,提出了稀疏貝葉斯學(xué)習(xí)的多維響應(yīng)拓展(multiple response extension of SBL,MSBL)算法。然而,當(dāng)矩陣中各個(gè)向量的非零元素的位置不同時(shí),并且非零元素個(gè)數(shù)不是很少時(shí),這些算法的重構(gòu)誤差將會(huì)很大,甚至失效。文獻(xiàn)[8]基于SL0(smoothed L0)算法提出了一種2D-SL0(two-dimensional SL0)算法用于實(shí)現(xiàn)稀疏矩陣重構(gòu)。該算法可以用于具有任意稀疏結(jié)構(gòu)的稀疏矩陣重構(gòu)。

為實(shí)現(xiàn)復(fù)雜稀疏結(jié)構(gòu)的稀疏矩陣重構(gòu),本文構(gòu)造了降采樣矩陣,提出了一種基于多觀測(cè)向量模型的序列降采樣重構(gòu)算法。仿真實(shí)驗(yàn)表明,通過(guò)提出的序列降采樣方法(sequential down-sampling recovery algorithm, SDR)和MFOCUSS(SDR-MFOCUSS)算法,可以高概率地重構(gòu)稀疏矩陣?；谛蛄薪挡蓸铀惴ê蚆SBL(SDR-MSBL)算法同樣有較好的性能,但是其計(jì)算量比SDR-MFOCUSS算法高很多。仿真實(shí)驗(yàn)同時(shí)表明,當(dāng)降采樣率較高時(shí),所提出的SDR-MFOCUSS算法性能優(yōu)于2D-SL0算法?；谀繕?biāo)逆合成孔徑雷達(dá)圖像的重構(gòu)實(shí)驗(yàn)表明,所提算法能有效地實(shí)現(xiàn)具有二維稀疏特性的圖像重構(gòu)。

1 多觀測(cè)向量模型

x(l)=As(l),l=1,2,…,L

(1)

多觀測(cè)向量模型可以表示為

X=AS

(2)

式中,S∈Rn×L。

在基于多觀測(cè)向量的稀疏表示問(wèn)題中,L個(gè)稀疏信號(hào)有相同的稀疏結(jié)構(gòu)。基于式(2),多觀測(cè)向量的稀疏表示問(wèn)題可表示為

‖0,Λ={1,2,…,m}, s.t.AS=X

(3)

‖1,Λ={1,2,…,m}, s.t.AS=X

(4)

同樣還有其他關(guān)于S的函數(shù)作為目標(biāo)函數(shù),如文獻(xiàn)[12]所示,提出了基于凸優(yōu)化問(wèn)題的稀疏量測(cè)方法,表示為

(5)

式(5)中的混合范數(shù)‖·‖p,q定義為

；q≥1

(6)

式中,S(i)表示矩陣S的第i行。MFOCUSS算法即要求解式(5)問(wèn)題的最優(yōu)解。

2 多觀測(cè)向量的序列降采樣重構(gòu)

當(dāng)二維稀疏信號(hào)的稀疏度比較低時(shí),現(xiàn)有的多觀測(cè)向量的稀疏重構(gòu)算法,如MFOCUSS算法和MSBL算法,都有比較好的重構(gòu)性能。然而,當(dāng)稀疏矩陣的各向量有不同的稀疏結(jié)構(gòu),并且非零元個(gè)數(shù)較多時(shí),上述方法將有可能在二維稀疏信號(hào)重構(gòu)時(shí)失效。本文提出了一種基于多觀測(cè)向量的序列降采樣算法,來(lái)實(shí)現(xiàn)二維稀疏信號(hào)的重構(gòu)。

基于壓縮感知理論,重寫式(2)為

X=ΨS

(7)

式中,Ψ∈Rm×n表示測(cè)量矩陣,通常,m

二維信號(hào)的重構(gòu)可通過(guò)序列降采樣和序列觀測(cè)來(lái)實(shí)現(xiàn)。假設(shè)E∈Rn×n為單位陣,降采樣率為T并且ns=n/T。構(gòu)造降采樣矩陣Pt∈Rn×n(t=1,2,…,T)。矩陣Pt的第T×r+t(0≤r≤ns-1)行與矩陣E對(duì)應(yīng)行相同,而矩陣Pt其他行的元素都為零。因此,矩陣Pt可表示為

(8)

可以看出,矩陣Pt只有第T×r+t(0≤r≤ns-1)行的第T×r+t個(gè)位置存在非零元素“1”,降采樣的過(guò)程即是將降采樣矩陣與信號(hào)S相乘。第t次觀測(cè)信號(hào)可表示為

Xt=Ψt(PtS)=ΨtSt

(9)

式中,Ψt∈Rm×n;St∈Rn×L。假設(shè)St和S的稀疏度分別為kt和k,則kt≤k,通常情況下,kt

在下面的分析中,假設(shè)矩陣Ψt對(duì)于所有的v∈Rn和部分常數(shù)c>0,滿足

P(|‖Ψtv‖2-‖v‖2|≥ε‖v‖2)≤2exp(-cnε2/2)

(10)

矩陣S的支撐基定義為

(11)

式中,S(l)表示矩陣S的第l列。向量S(l)的支撐基定義為

supp(S(l))={j,Sjl≠0}

(12)

假設(shè)信號(hào)S∈Rn×L滿足supp(S)=Ω。ΨtΩ表示由Ω索引的矩陣Ψt的列構(gòu)成的子矩陣,并且假設(shè)矩陣ΨtΩ是非奇異的,那么當(dāng)滿足式(13)時(shí),S是唯一的最優(yōu)解。

?Ω

(13)

(14)

假設(shè)

?l?Ω

(15)

通過(guò)式(9)重構(gòu)St的概率為

(16)

為重構(gòu)信號(hào)S,需要序列地重構(gòu)信號(hào)St(t=1,2,…,T)。

(17)

式中

(18)

式中,d(St)表示St中非零行的個(gè)數(shù);λ是平衡估計(jì)效果的權(quán)重。

當(dāng)完成St(t=1,2,…,T)的重構(gòu)后,二維稀疏信號(hào)就可以重構(gòu)出來(lái),如圖1所示。

圖1 序列降采樣重構(gòu)Fig.1 Sequential down-sampling recovery algorithm

根據(jù)上述分析,所提的多觀測(cè)向量的序列降采樣重構(gòu)方法流程可表示如下:

步驟1構(gòu)造降采樣矩陣Pt(t=1,2,…,T),得到觀測(cè)信號(hào)Xt;

步驟2利用MFOCUSS方法求解式(18)優(yōu)化問(wèn)題,重構(gòu)信號(hào)St,其重構(gòu)概率可用式(16)表示;

步驟3重復(fù)上述步驟,直至t=T,通過(guò)式(17)計(jì)算最終重構(gòu)的稀疏矩陣信號(hào)。

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

3.1 模擬信號(hào)重構(gòu)

本節(jié)通過(guò)對(duì)仿真產(chǎn)生的模擬信號(hào)的重構(gòu)效果驗(yàn)證本文算法的有效性。假設(shè)二維稀疏信號(hào)S各向量所包含的非零元素的位置和元素值是不相關(guān)的?！琒(l)‖0=k,l=1,2,…,L。k個(gè)非零元的位置是隨機(jī)確定的,非零元素的元素值服從標(biāo)準(zhǔn)高斯分布。假設(shè)n=100,L=5,m=50。在第1次仿真實(shí)驗(yàn)中,假設(shè)降采樣率T=2。當(dāng)k=10時(shí),初始信號(hào)如圖2所示。

圖2 初始信號(hào)Fig.2 Initial signal

從圖2可以看出,稀疏矩陣不同向量間非零元所在位置不同,不滿足傳統(tǒng)的多觀測(cè)向量重構(gòu)方法模型。

圖3 不同算法的二維稀疏信號(hào)重構(gòu)概率Fig.3 2D sparse signal recovery probability with difference approaches versus sparsity

從圖3可以看出,利用本文提出的SDR-MFOCUSS算法可實(shí)現(xiàn)二維稀疏信號(hào)的精確高概率重構(gòu)。

在第2個(gè)仿真實(shí)驗(yàn)中,同樣假設(shè)降采樣率為T=2,對(duì)比了SDR-MFOCUSS算法和SDR-MSBL算法的計(jì)算時(shí)間,如圖4所示。

圖4 SDR-MSBL和SDR-MFOCUSS算法的運(yùn)算時(shí)間Fig.4 Comparison of CPU times for SDR-MSBL and SDR-MFOCUSS algorithms

從圖3和圖4可以看出,相比于MFOCUSS和MSBL算法,SDR-MFOCUSS算法和SDR-MSBL算法在稀疏矩陣重構(gòu)方面有著更好的性能。但是,本文提出的SDR-MFOCUSS算法的計(jì)算量遠(yuǎn)小于SDR-MSBL算法,主要原因是SDR-MSBL算法的迭代過(guò)程計(jì)算量很大,因而有更高的計(jì)算復(fù)雜度。

圖5對(duì)比了不同降采樣率T的條件下,SDR-MFOCUSS算法和2D-SL0算法在稀疏矩陣重構(gòu)中的重構(gòu)概率。

圖5 不同參數(shù)T時(shí)SDR-MFOCUSS算法重構(gòu)概率Fig.5 Performance of SDR-MFOCUSS algorithm as a function of T

從圖5中可以看出,當(dāng)T=2時(shí),SDR-MFOCUSS算法和2D-SL0算法有近似的重構(gòu)概率,而隨著降采樣率T的增大,SDR-MFOCUSS算法相比于2D-SL0算法有更高的重構(gòu)概率,證明了本文所提方法的優(yōu)越性。

3.2 圖像重構(gòu)

典型的飛機(jī)目標(biāo)的逆合成孔徑雷達(dá)圖像通常滿足本文描述的二維稀疏特性,本節(jié)通過(guò)對(duì)該類圖像的重構(gòu)來(lái)驗(yàn)證本文算法在自然圖像重構(gòu)中的有效性。

典型直升機(jī)目標(biāo)的逆合成孔徑雷達(dá)初始圖像如圖6所示,可以看出目標(biāo)在整個(gè)圖像域是二維稀疏的。

首先，統(tǒng)計(jì)車次信息。車次信息包含車次、出車方向、時(shí)間、股道約束、里程、是否為早/晚高峰等，如圖2所示。

圖6 初始雷達(dá)圖像Fig.6 Initial radar image

對(duì)比不同方法對(duì)該類圖像的重構(gòu)效果,結(jié)果如圖7所示。

圖7 不同算法的圖像重構(gòu)效果Fig.7 Reconstructed images of different methods

參數(shù)算法SDR-MFOCUSSSDR-MSBLMFOCUSSMSBLMSE0.05130.04800.50460.4669時(shí)間/s0.13270.29790.69181.7274

從圖7及表1可以看出,基于SDR-MFOCUSS算法和SDR-MSBL算法對(duì)圖像的重構(gòu)效果明顯優(yōu)于MFOCUSS算法及MSBL算法,而SDR-MFOCUSS比SDR-MSBL有更低的運(yùn)算量和更短的運(yùn)算時(shí)間,證明了本文方法在圖像重構(gòu)中的有效性和優(yōu)越性。

4 結(jié)束語(yǔ)

本文引入了稀疏矩陣重構(gòu)和多觀測(cè)向量的稀疏表示問(wèn)題。當(dāng)稀疏矩陣的各向量有不同的稀疏結(jié)構(gòu)時(shí),傳統(tǒng)的多觀測(cè)向量稀疏重構(gòu)算法,如MFOCUSS和MSBL算法,將會(huì)有較高的重構(gòu)誤差。本文構(gòu)建了降采樣矩陣,提出了一種新的序列降采樣重構(gòu)方法,結(jié)合MFOCUSS算法,可實(shí)現(xiàn)二維稀疏信號(hào)的精確重構(gòu)。模擬信號(hào)及圖像重構(gòu)實(shí)驗(yàn)驗(yàn)證了本文方法在模擬信號(hào)及圖像重構(gòu)中的有效性和優(yōu)越性。然而,當(dāng)稀疏矩陣各向量間稀疏度相差很大時(shí),所提方法重構(gòu)誤差將會(huì)急劇增大。后續(xù)工作將集中于該類矩陣,尤其是非零元只分布于某些列的矩陣的重構(gòu)問(wèn)題。

[1] BARANIUK R G. Compressive sensing[J]. IEEE Signal Process Magazine, 2007, 24(4): 118-121.

[2] 王彩云,徐靜. 改進(jìn)的壓縮感知測(cè)量矩陣優(yōu)化方法[J]. 系統(tǒng)工程與電子技術(shù),2015, 37(4): 752-756.

WANG C Y, XU J. Improved optimization algorithm for measurement matrix in compressed sensing[J]. Systems Engineering and Electronics, 2015, 37(4): 752-756.

[3] BERG E, FRIEDLANDER M P. Theoretical and empirical results for recovery from multiple measurements[J]. IEEE Trans.on Information Theory, 2010, 56(5): 310-316.

[4] CHEN J, HUO X. Theoretical results on sparse representations of multiple - measurement vectors[J]. IEEE Trans.on Signal Processing, 2006, 54(12): 4634-4643.

[5] WANG Y, FU T, GAO M, et al. Performance of orthogonal matching pursuit for multiple measurement vectors with noise[C]∥Proc.of the IEEE China Summit & International Conference on Signal and Information Processing, 2013: 67-71.

[6] COTTER S F, RAO B D, ENGAN K, et al. Sparse solutions to linear inverse problems with multiple measurement vectors[J]. IEEE Trans.on Signal Processing, 2005, 53(7): 2477-2488.

[7] WIPF D P, RAO B D. An empirical Bayesian strategy for solving the simultaneous sparse approximation problem[J]. IEEE Trans.on Signal Processing, 2007, 55(7): 3704-3716.

[8] GHAFFARI A, BABAIE-ZADEH M, JUTTEN C. Sparse decomposition of two dimensional signals[C]∥Proc.of the 34th IEEE International Conference on Acoustics, Speech Signal Processing, 2009: 3157-3160.

[9] 司菁菁,候肖蘭,程銀波. 基于塊剪枝多路徑匹配追蹤的多信號(hào)聯(lián)合重構(gòu)[J]. 系統(tǒng)工程與電子技術(shù),2016, 38(9): 1993-1999.

SI J J, HOU X L, CHENG Y B. Joint multi-signal reconstruction based on block pruning multipath matching pursuit[J]. Systems Engineering and Electronics, 2016, 38(9): 1993-1999.

[10] JIN Y, RAO B D. Support recovery of sparse signals in the presence of multiple measurement vectors[J]. IEEE Trans.on Information Theory, 2013, 59(5): 3139-3157.

[11] ELDAR Y C, RAUHUT H. Average case analysis of multichannel sparse recovery using convex relaxation[J]. IEEE Trans.on Information Theory, 2010, 56(1): 505-519.

[12] CHEN J, HUO X. Sparse representations for multiple measurement vectors (MMV) in an over-complete dictionary[C]∥Proc.of the 30th IEEE International Conference on Acoustics, Speech Signal Processing, 2005: 257-260.

[13] RAUHUT H, SCHNASS K, VANDERGHEYNST P. Compressed sensing and redundant dictionaries[J]. IEEE Trans.on Information Theory, 2008, 54(5): 2210-2219.