蘆存博 肖 嵩 權(quán) 磊

?

基于二進制序列族的壓縮感知測量矩陣構(gòu)造

蘆存博*肖 嵩 權(quán) 磊

(西安電子科技大學(xué)ISN國家重點實驗室 西安 710071)

構(gòu)造確定性測量矩陣對壓縮感知理論的推廣與應(yīng)用具有重要的意義。該文源于代數(shù)編碼理論，提出一種基于二進制序列族的確定性測量矩陣構(gòu)造算法。相關(guān)性是描述矩陣性質(zhì)的重要準(zhǔn)則，減小相關(guān)性可使重建性能提高。該文推導(dǎo)出所構(gòu)造測量矩陣的相關(guān)性小于同條件下的高斯隨機矩陣和伯努利隨機矩陣。理論分析和仿真實驗表明，該方式構(gòu)造的測量矩陣的重建性能優(yōu)于同條件下的高斯隨機矩陣和伯努利隨機矩陣；所構(gòu)造矩陣可由線性反饋移位寄存器結(jié)構(gòu)實現(xiàn)，易于硬件實現(xiàn)，有利于壓縮感知理論的實用化。

信號處理；壓縮感知；測量矩陣；二進制序列族

1 引言

壓縮感知(Compressed Sensing, CS)[1,2]的概念是2006年Donono和Candes等人提出的，它是一種不同于奈奎斯特(Nyquist)采樣定律的全新信號采樣框架。CS可實現(xiàn)以遠低于Nyquist的采樣率去采樣稀疏信號，其核心是利用測量矩陣將高維稀疏信號投影到一個低維空間上，然后利用信號的稀疏性，通過重建算法以高概率實現(xiàn)原始信號的精確重建。這種提高采樣效率的新思路引起了學(xué)術(shù)界的廣泛關(guān)注，CS在數(shù)字信號處理、信息論、通信、光學(xué)成像、雷達等領(lǐng)域受到高度關(guān)注。

CS過程分為兩部分：數(shù)據(jù)采樣和信號重建，在這兩部分中測量矩陣都起著至關(guān)重要作用。首先，在數(shù)據(jù)采樣中，好的測量矩陣可以以較少的測量數(shù)目達到相同的重構(gòu)精度。其次，在信號重建中，在相同的采樣率下得到的數(shù)據(jù)，好的測量矩陣對信號可以達到較高的重構(gòu)精度?？傮w來說，好的測量矩陣能夠在投影測量時保持原始信號的全部信息，并可結(jié)合測量值重構(gòu)出原始信號。測量矩陣的性質(zhì)決定了能否將原始信號的全局信息保存下來。文獻[3]提出了測量矩陣必須滿足的性質(zhì)-約束等距性(Restricted Isometry Property, RIP), 即只要測量矩陣滿足RIP特性，那么就能以高概率從低維的測量結(jié)果向量中準(zhǔn)確地恢復(fù)出原信號。相關(guān)性(coherence)是建立矩陣RIP的另一個重要方法，文獻[4]指出了相關(guān)性跟RIP的關(guān)系：低相關(guān)性的矩陣滿足RIP。矩陣的RIP[5,6]和相關(guān)性均是分析測量矩陣性質(zhì)的重要工具，本文將采用相關(guān)性對所構(gòu)造測量矩陣的性質(zhì)進行分析和說明。

測量矩陣可以分為隨機測量矩陣和確定性測量矩陣。在隨機矩陣中比較常用的是高斯矩陣和伯努利矩陣。由于隨機矩陣能夠以很大概率滿足RIP, 因此在科研上被廣泛應(yīng)用。但是在隨機矩陣中，每一個元素都是獨立同分布的，存在不確定性，使得每一個元素都要存儲，耗費大量的存儲資源，并且隨機數(shù)的產(chǎn)生對硬件要求很高，不利于硬件實現(xiàn)，使得其實際應(yīng)用受限。確定性測量矩陣的元素和值都是確定的，可以克服這些不足。許多研究者利用一些技術(shù)來構(gòu)造確定性測量矩陣。例如，文獻[7]指出好的原模圖低密度奇偶校驗碼(Low Density Parity Check, LDPC)校驗矩陣可以作為測量矩陣；文獻[8]采用m序列構(gòu)造出性能較好的測量矩陣；文獻[9]利用Berlekamp-Justesen碼構(gòu)造測量矩陣；文獻[10]采用范德蒙矩陣構(gòu)造出性能較好的測量矩陣；文獻[11]用混沌序列構(gòu)造測量矩陣；文獻[13]用Reed- Solomon碼構(gòu)造測量矩陣等。

本文將在文獻[14]中二進制序列族(Binary Sequence Family, BSF)的基礎(chǔ)上構(gòu)造一種確定性測量矩陣(Binary Sequence Family based Deterministic Measurement Matrix, BSFDMM)，它是一種由+1和-1組成的雙極性矩陣，并推導(dǎo)出了矩陣BSFDMM的相關(guān)性小于同條件下的高斯隨機矩陣和伯努利隨機矩陣。理論分析和仿真實驗表明，文中矩陣BSFDMM的重建性能優(yōu)于同條件下的高斯隨機矩陣和伯努利隨機矩陣。

2 基本理論

2.1 壓縮感知

上述求解問題是NP-hard。CS理論證明了在適當(dāng)?shù)臏y量矩陣下，該問題可以轉(zhuǎn)化為求解最小1范數(shù)優(yōu)化問題，即

該問題可以通過基追蹤(Basis Pursuit, BP)算法[15]，得到與式(1)等價的最稀疏估計。目前，有一些直接求解式(1)的貪婪追蹤類算法，該類算法通過迭代求解局部最優(yōu)解，最終逼近全局最優(yōu)，從而得到原始信號的精確估計。例如，正交匹配追蹤(Orthogonal Matching Pursuit, OMP)[16]。

2.2 跡函數(shù)

3 測量矩陣構(gòu)造

本文矩陣BSFDMM的具體實現(xiàn)步驟如下：

一旦給定數(shù)值轉(zhuǎn)換函數(shù)式(5)和有限域上的跡表示函數(shù)式(3)或式(4)，則能確定出所構(gòu)造矩陣的每一個元素值，避免了隨機矩陣的不確定性；BSFDMM矩陣的元素結(jié)構(gòu)使其非常便于硬件實現(xiàn)，數(shù)值轉(zhuǎn)換函數(shù)式(5)的本質(zhì)是元素替換，在硬件實現(xiàn)上只用改變相應(yīng)元素的輸出即可，非常簡單；又因為矩陣BSFDMM的生成過程中，使用的是文獻[14]的跡表示函數(shù)，從文獻[14]可得，BSFDMM矩陣可由LFSR結(jié)構(gòu)實現(xiàn)，易于硬件實現(xiàn)，有利于壓縮感知理論的實用化。

4 相關(guān)性分析

相關(guān)性是描述矩陣性質(zhì)的重要準(zhǔn)則，減小相關(guān)性可使重建性能提高。本節(jié)給出所構(gòu)造矩陣BSFDMM的相關(guān)性大小的上界，并推導(dǎo)出矩陣BSFDMM的相關(guān)性小于同條件下的高斯隨機矩陣和伯努利隨機矩陣，進而可從理論上證明矩陣BSFDMM的重建性能優(yōu)于同條件下的高斯隨機矩陣和伯努利隨機矩陣。

為了比較本文中的BSFDMM和同條件下的高斯隨機矩陣和伯努利隨機矩陣的重建性能，可以比較它們的相關(guān)性大小。首先引入以下文獻[18]的兩個引理：

減小相關(guān)性能使可重建信號的稀疏度增大，重建性能提高。由定理1和定理2可以得到以下結(jié)論：

結(jié)論2 矩陣BSFDMM的重建性能優(yōu)于同條件下的高斯隨機矩陣。

結(jié)論3 矩陣BSFDMM的重建性能優(yōu)于同條件下的伯努利隨機矩陣。

5 實驗仿真及分析

比較了本文矩陣BSFDMM與相同大小的高斯隨機測量矩陣Gauss和伯努利隨機測量矩陣Bernoulli在無噪聲條件和有噪聲條件下的重建性能，其中矩陣BSFDMM分為兩種情況：(1)對應(yīng)于是偶數(shù)的情況，此時矩陣大小為；(2)對應(yīng)于是奇數(shù)的情況，此時矩陣大小為。通過隨機選取支撐位置，且支撐值服從標(biāo)準(zhǔn)的高斯分布，來生成被采樣的稀疏信號，其長度為。對每個稀疏度，用MATLAB生成1000次，重構(gòu)算法選取OMP算法，若重建結(jié)果滿足，則重建實驗成功，重建概率即為精確重建次數(shù)與總次數(shù)的比值。Gauss矩陣的每一個元素取值服從獨立同分布的標(biāo)準(zhǔn)正態(tài)分布。Bernoulli矩陣的每一個元素取值服從獨立同分布的貝努利分布，且元素由+1和-1組成。

5.1無噪聲重建

圖1 BSFDMM大小為255512的情況

由圖1(a)的重建曲線可以看出，對于矩陣BSFDMM，當(dāng)信號稀疏度達到60時，才開始出現(xiàn)重建失敗的情況。然而，相同大小的Gauss矩陣和Bernoulli矩陣在稀疏度分別為35和30時，就已經(jīng)開始出現(xiàn)重建失敗的情況。當(dāng)信號稀疏度分別增大到130和125時，Gauss矩陣和Bernoulli矩陣就完全不能重建出原始信號。而矩陣BSFDMM在信號稀疏度增大到145時，依然有重建的可能。

從圖2(a)的重建曲線可以看出，對于矩陣BSFDMM，當(dāng)信號稀疏度達到30時，才開始出現(xiàn)重建失敗的情況。然而，相同大小的Gauss矩陣和Bernoulli矩陣在稀疏度都為15時，就已經(jīng)開始出現(xiàn)重建失敗的情況。當(dāng)信號稀疏度增大到70時，Gauss矩陣和Bernoulli矩陣兩者都完全不能重建出原始信號。而矩陣BSFDMM在信號稀疏度增大到80時，依然有重建的可能。

從圖1(a)和圖2(a)的邊界條件分析可見，矩陣BSFDMM的信號恢復(fù)效果比相同大小的Gauss矩陣和Bernoulli矩陣效果好，這是因為矩陣BSFDMM的相關(guān)性小于相同大小的Gauss矩陣和Bernoulli矩陣，可重建信號的稀疏度增大，重建性能提高。

5.2有噪聲重建

圖2 BSFDMM大小為127256的情況

從圖1(b)和圖2(b)可以看出，矩陣BSFDMM的信號恢復(fù)效果比相同大小的Gauss矩陣和Bernoulli矩陣效果好，這是因為矩陣BSFDMM的相關(guān)性小于后兩者，更有利于信號重構(gòu)。

從圖1(c)和圖2(c)可知，在不同輸入噪聲條件下，采用本文所構(gòu)造的BSFDMM矩陣，進行重建后的輸出信噪比比采用高斯隨機測量矩陣和伯努利隨機測量矩陣的都要高。隨著輸入信噪比的增加，3種矩陣的輸出信噪比都隨之增加。在圖1(c)中，當(dāng)輸入信噪比小于40 dB時，由于噪聲的影響，3種矩陣的輸出信噪比曲線整體區(qū)分并不是非常明顯，而從輸入信噪比大于40 dB開始，3種矩陣的輸出信噪比曲線區(qū)分開始明顯，此時BSFDMM矩陣相關(guān)性小的優(yōu)勢開始明顯體現(xiàn)。隨著輸入信噪比的增加，BSFDMM矩陣的輸出信噪比曲線與其它兩種矩陣的曲線的區(qū)分越來越明顯。從圖2(c)中也可以得到3種矩陣輸出信噪比曲線類似的規(guī)律。

通過上述仿真發(fā)現(xiàn)，BSFDMM矩陣比相同條件下的高斯隨機矩陣和伯努利隨機矩陣的抗噪聲性能都要好，說明本文矩陣不僅在無噪聲條件下表現(xiàn)良好，在噪聲環(huán)境中同樣具有良好的重建性能，即表明文中所提矩陣的實用性。

6 結(jié)論

在二進制序列族的基礎(chǔ)上，本文構(gòu)造了一種確定性測量矩陣- BSFDMM，它是一種由+1和-1組成的雙極性矩陣，并通過理論推導(dǎo)，得到所構(gòu)造矩陣的相關(guān)性小于同條件下的高斯隨機矩陣和伯努利隨機矩陣。理論分析和仿真實驗表明，在相同條件下，BSFDMM矩陣不僅在無噪聲條件下的重建性能優(yōu)于高斯隨機矩陣和伯努利隨機矩陣，而且在噪聲環(huán)境下其抗噪聲性能也比高斯矩陣和伯努利矩陣要好，說明了文中矩陣的實用性。矩陣BSFDMM可由LFSR結(jié)構(gòu)實現(xiàn)，易于硬件實現(xiàn)，有利于壓縮感知理論的實用化。

[1] CANDES E J, ROMBERG J, and TAO T. Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information[J]., 2006, 52(2): 489-509. doi: 10.1109/TIT.2005.862083.

[2] DONOHO D L. Compressed sensing[J]., 2006, 52(4): 1289-1306. doi: 10.1109 /TIT.2006.871582.

[3] CANDES E J and TAO T. Decoding by linear programming [J]., 2005, 51(12): 4203-4215. doi: 10.1109/TIT.2005.858979.

[4] BOURGAIN J, DILWORTH S, FORD K,. Explicit constructions of RIP matrices and related problems[J]., 2011, 159(1): 145-185. doi: 10.1215/ 00127094-1384809.

[5] GAN H, LI Z, LI J,. Compressive sensing using chaotic sequence based on chebyshev map[J]., 2014, 78(4): 2429-2438. doi: 10.1007/s11071-014-1600-1.

[6] CASTORENA J and CREUSERE C D. The restricted isometry property for banded random matrices[J]., 2014, 62(19): 5073-5084. doi: 10.1109/TSP.2014.2345350.

[7] ZHANG J, HAN G, and FANG Y. Deterministic construction of compressed sensing matrices from protograph LDPC codes[J]., 2015, 22(11): 1960-1964. doi: 10.1109/LSP.2015.2447934.

[8] 黨骙, 馬林華, 田雨, 等. m序列壓縮感知測量矩陣構(gòu)造[J].西安電子科技大學(xué)學(xué)報, 2015, 42(2): 186-192. doi: 10.3969/ j.issn.1001-2400.2015.02.031.

DANG Kui, MA Linhua, TIAN Yu,. Construction of the compressive sensing measurement matrix based on m sequences[J]., 2015, 42(2): 186-192. doi: 10.3969/j.issn.1001-2400.2015.02.031.

[9] 夏樹濤, 劉璐, 劉鑫吉. 基于Berlekamp-Justesen碼的壓縮感知確定性測量矩陣的構(gòu)造[J]. 電子與信息學(xué)報, 2015, 37(4): 763-769. doi: 10.11999/JEIT140875.

XIA Shutao, LIU Lu, and LIU Xinji. Deterministic constructions of compressive sensing matrices based on berlekamp-justesen codes[J].&, 2015, 37(4): 763-769. doi: 10. 11999/JEIT140875.

[10] 趙瑞珍, 王若乾, 張鳳珍, 等. 分塊的有序范德蒙矩陣作為壓縮感知測量矩陣的研究[J]. 電子與信息學(xué)報, 2015, 37(6): 1317-1322. doi: 10.11999/JEIT140860.

ZHAO Ruizhen, WANG Ruoqian, ZHANG Fengzhen,. Research on the blocked ordered vandermonde matrix used as measurement matrix for compressed sensing[J].&, 2015, 37(6): 1317-1322. doi: 10.11999/JEIT140860.

[11] ZENG L, ZHANG X, CHEN L,. Deterministic construction of toeplitzed structurally chaotic matrix for compressed sensing[J].,,, 2015, 34(3): 797-813. doi: 10.1007/s00034-014- 9873-7.

[12] LI S and GE G. Deterministic sensing matrices arising from near orthogonal systems[J]., 2014, 60(4): 2291-2302. doi: 10.1109/ TIT.2014.2303973.

[13] MOHADES M M, MOHADES A, and TADAION A. A reed-solomon code based measurement matrix with small coherence[J]., 2014, 21(7): 839-843. doi: 10.1109/LSP.2014.2314281.

[14] YU N Y and GONG G. A new binary sequence family with low correlation and large size[J]., 2006, 52(4): 1624-1636. doi: 10.1109/ TIT.2006.871062.

[15] CHEN S S, DONOHO D L, and SAUNDERS M A. Atomic decomposition by basis pursuit[J]., 1998, 20(1): 33-61. doi: 10.1137/ S1064827596304010.

[16] TROPP J. Greed is good: algorithmic results for sparse approximation[J]., 2004, 50(10): 2231-2242. doi: 10.1109/TIT.2004.834793.

[17] DONOHO D L and ELAD M. Optimally sparse representation in general (nonorthogonal) dictionaries via1minimization[J]., 2003, 100(5): 2197-2202. doi: 10.1073/pnas. 0437847100.

[18] HAUPT J, BAJWA W U, RAZ G,. Toeplitz compressed sensing matrices with applications to sparse channel estimation[J]., 2010, 56(11): 5862-5875. doi: 10.1109/TIT.2010.2070191.

Construction of Compressed Sensing Measurement Matrix Based on Binary Sequence Family

LU Cunbo XIAO Song QUAN Lei

(,,’710071,)

It is significant to construct deterministic measurement matrix for the promotion and application of the Compressed Sensing (CS) theory. Originating from the algebraic coding theory, a construction algorithm of Binary Sequence Family (BSF) based deterministic measurement matrix is presented. The coherence is an important criterion to describe the property of matrices. Lower coherence leads to higher reconstruction performance. The coherence of the proposed measurement matrix is derived to be smaller than the corresponding Gaussian random matrix and Bernoulli random matrix. Theoretical analysis and simulation results show that the proposed matrix can obtain better reconstruction results than the corresponding Gaussian random matrix and Bernoulli random matrix. The proposed matrix can make the hardware realization convenient and easy by means of Linear Feedback Shift Register (LFSR) structures, thus being conductive to practical compressed sensing.

Signal processing; Compressed Sensing (CS); Measurement matrix; Binary Sequence Family (BSF)

TN911.72

A

1009-5896(2016)07-1682-07

10.11999/JEIT151076

2015-09-21；改回日期：2016-01-20；網(wǎng)絡(luò)出版：2016-03-25

蘆存博 444180647@qq.com

國家自然科學(xué)基金(61372069)，高等學(xué)校學(xué)科創(chuàng)新引智計劃(111計劃)(B08038)

The National Natural Science Foundation of China (61372069), The Programme of Introducing Talents of Discipline to Universities (111 Project) (B08038)

蘆存博： 男，1989年生，博士生，研究方向為無線網(wǎng)絡(luò)編碼、壓縮感知加密算法.

肖 嵩： 女，1977年生，教授，博士生導(dǎo)師，研究方向為網(wǎng)絡(luò)編碼、視頻/圖像聯(lián)合信源信道編碼.

權(quán) 磊： 男，1989年生，博士生，研究方向為無線傳感器網(wǎng)絡(luò)、壓縮感知.