基于多觀測向量序列降采樣恢復的稀疏矩陣重構

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

(空軍工程大學防空反導學院, 陜西 西安 710051)

0 引 言

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

由于目標函數‖·‖0是非凸的,所以很難找到0范數優化問題的最優解。一個比較有效的方法是,將上述0范數優化問題轉換為它的凸近似,也即1優化問題,進而通過線性規劃來找到其最優解。相比于0范數的優化問題,1范數優化問題表示的凸松弛問題可以更為有效地得到解決,并且得到的最優解與0范數優化問題一致。

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

為實現復雜稀疏結構的稀疏矩陣重構,本文構造了降采樣矩陣,提出了一種基于多觀測向量模型的序列降采樣重構算法。仿真實驗表明,通過提出的序列降采樣方法(sequential down-sampling recovery algorithm, SDR)和MFOCUSS(SDR-MFOCUSS)算法,可以高概率地重構稀疏矩陣。基于序列降采樣算法和MSBL(SDR-MSBL)算法同樣有較好的性能,但是其計算量比SDR-MFOCUSS算法高很多。仿真實驗同時表明,當降采樣率較高時,所提出的SDR-MFOCUSS算法性能優于2D-SL0算法?；谀繕四婧铣煽讖嚼走_圖像的重構實驗表明,所提算法能有效地實現具有二維稀疏特性的圖像重構。

1 多觀測向量模型

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

(1)

多觀測向量模型可以表示為

X=AS

(2)

式中,S∈Rn×L。

在基于多觀測向量的稀疏表示問題中,L個稀疏信號有相同的稀疏結構?；谑?2),多觀測向量的稀疏表示問題可表示為

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

(3)

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

(4)

同樣還有其他關于S的函數作為目標函數,如文獻[12]所示,提出了基于凸優化問題的稀疏量測方法,表示為

(5)

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

；q≥1

(6)

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

2 多觀測向量的序列降采樣重構

當二維稀疏信號的稀疏度比較低時,現有的多觀測向量的稀疏重構算法,如MFOCUSS算法和MSBL算法,都有比較好的重構性能。然而,當稀疏矩陣的各向量有不同的稀疏結構,并且非零元個數較多時,上述方法將有可能在二維稀疏信號重構時失效。本文提出了一種基于多觀測向量的序列降采樣算法,來實現二維稀疏信號的重構。

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

X=ΨS

(7)

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

二維信號的重構可通過序列降采樣和序列觀測來實現。假設E∈Rn×n為單位陣,降采樣率為T并且ns=n/T。構造降采樣矩陣Pt∈Rn×n(t=1,2,…,T)。矩陣Pt的第T×r+t(0≤r≤ns-1)行與矩陣E對應行相同,而矩陣Pt其他行的元素都為零。因此,矩陣Pt可表示為

(8)

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

Xt=Ψt(PtS)=ΨtSt

(9)

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

在下面的分析中,假設矩陣Ψt對于所有的v∈Rn和部分常數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)

假設信號S∈Rn×L滿足supp(S)=Ω。ΨtΩ表示由Ω索引的矩陣Ψt的列構成的子矩陣,并且假設矩陣ΨtΩ是非奇異的,那么當滿足式(13)時,S是唯一的最優解。

?Ω

(13)

(14)

假設

?l?Ω

(15)

通過式(9)重構St的概率為

(16)

為重構信號S,需要序列地重構信號St(t=1,2,…,T)。

(17)

式中

(18)

式中,d(St)表示St中非零行的個數;λ是平衡估計效果的權重。

當完成St(t=1,2,…,T)的重構后,二維稀疏信號就可以重構出來,如圖1所示。

圖1 序列降采樣重構Fig.1 Sequential down-sampling recovery algorithm

根據上述分析,所提的多觀測向量的序列降采樣重構方法流程可表示如下:

步驟1構造降采樣矩陣Pt(t=1,2,…,T),得到觀測信號Xt;

步驟2利用MFOCUSS方法求解式(18)優化問題,重構信號St,其重構概率可用式(16)表示;

步驟3重復上述步驟,直至t=T,通過式(17)計算最終重構的稀疏矩陣信號。

3 仿真實驗及分析

3.1 模擬信號重構

本節通過對仿真產生的模擬信號的重構效果驗證本文算法的有效性。假設二維稀疏信號S各向量所包含的非零元素的位置和元素值是不相關的。‖S(l)‖0=k,l=1,2,…,L。k個非零元的位置是隨機確定的,非零元素的元素值服從標準高斯分布。假設n=100,L=5,m=50。在第1次仿真實驗中,假設降采樣率T=2。當k=10時,初始信號如圖2所示。

圖2 初始信號Fig.2 Initial signal

從圖2可以看出,稀疏矩陣不同向量間非零元所在位置不同,不滿足傳統的多觀測向量重構方法模型。

圖3 不同算法的二維稀疏信號重構概率Fig.3 2D sparse signal recovery probability with difference approaches versus sparsity

從圖3可以看出,利用本文提出的SDR-MFOCUSS算法可實現二維稀疏信號的精確高概率重構。

在第2個仿真實驗中,同樣假設降采樣率為T=2,對比了SDR-MFOCUSS算法和SDR-MSBL算法的計算時間,如圖4所示。

圖4 SDR-MSBL和SDR-MFOCUSS算法的運算時間Fig.4 Comparison of CPU times for SDR-MSBL and SDR-MFOCUSS algorithms

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

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

圖5 不同參數T時SDR-MFOCUSS算法重構概率Fig.5 Performance of SDR-MFOCUSS algorithm as a function of T

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

3.2 圖像重構

典型的飛機目標的逆合成孔徑雷達圖像通常滿足本文描述的二維稀疏特性,本節通過對該類圖像的重構來驗證本文算法在自然圖像重構中的有效性。

典型直升機目標的逆合成孔徑雷達初始圖像如圖6所示,可以看出目標在整個圖像域是二維稀疏的。

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

圖6 初始雷達圖像Fig.6 Initial radar image

對比不同方法對該類圖像的重構效果,結果如圖7所示。

圖7 不同算法的圖像重構效果Fig.7 Reconstructed images of different methods

參數算法SDR-MFOCUSSSDR-MSBLMFOCUSSMSBLMSE0.05130.04800.50460.4669時間/s0.13270.29790.69181.7274

從圖7及表1可以看出,基于SDR-MFOCUSS算法和SDR-MSBL算法對圖像的重構效果明顯優于MFOCUSS算法及MSBL算法,而SDR-MFOCUSS比SDR-MSBL有更低的運算量和更短的運算時間,證明了本文方法在圖像重構中的有效性和優越性。

4 結束語

本文引入了稀疏矩陣重構和多觀測向量的稀疏表示問題。當稀疏矩陣的各向量有不同的稀疏結構時,傳統的多觀測向量稀疏重構算法,如MFOCUSS和MSBL算法,將會有較高的重構誤差。本文構建了降采樣矩陣,提出了一種新的序列降采樣重構方法,結合MFOCUSS算法,可實現二維稀疏信號的精確重構。模擬信號及圖像重構實驗驗證了本文方法在模擬信號及圖像重構中的有效性和優越性。然而,當稀疏矩陣各向量間稀疏度相差很大時,所提方法重構誤差將會急劇增大。后續工作將集中于該類矩陣,尤其是非零元只分布于某些列的矩陣的重構問題。

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

[2] 王彩云,徐靜. 改進的壓縮感知測量矩陣優化方法[J]. 系統工程與電子技術,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] 司菁菁,候肖蘭,程銀波. 基于塊剪枝多路徑匹配追蹤的多信號聯合重構[J]. 系統工程與電子技術,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.