基于行列式隨機循環(huán)的壓縮感知測量矩陣研究

魏從靜，唐加山

(南京郵電大學 a.通信與信息工程學院；b.理學院，江蘇 南京 210023)

基于行列式隨機循環(huán)的壓縮感知測量矩陣研究

魏從靜a，唐加山b

(南京郵電大學 a.通信與信息工程學院；b.理學院，江蘇 南京 210023)

壓縮感知理論，從信號的自身特性出發(fā)，通過變換作用域和線性投影實現(xiàn)對信號的采樣和壓縮。測量矩陣是該理論中獲得的最優(yōu)測量，實現(xiàn)精確重構的關鍵。本文在介紹常用測量矩陣的基礎上，重點研究了結構化測量矩陣。鑒于測量矩陣設計的最重要的原則是降低矩陣元素間的相干性，借鑒循環(huán)矩陣和廣義輪換矩陣的優(yōu)點，提出了采用均勻隨機數(shù)對結構化測量矩陣進行隨機循環(huán)的構造方法。仿真實驗表明新矩陣在信號重建上具有更好的性能。

壓縮感知；測量矩陣；托普利茲矩陣；隨機循環(huán)

信號采樣架起了模擬信源和數(shù)字信息之間的橋梁，傳統(tǒng)的信號采樣方法以香農(nóng)定理為基礎。然而，隨著處理信號的帶寬和數(shù)據(jù)量越來越大，這種方式使有限帶寬假設的采樣方法受到了巨大挑戰(zhàn)。壓縮感知[1-2](Compressed Sensing，CS)理論基于信號在特定變換域下是稀疏的或可壓縮的前提，將高維信號通過線性測量映射到一個低維空間，實現(xiàn)對數(shù)據(jù)采樣的同時進行壓縮，并最終通過求解組合優(yōu)化問題從這些少量的低維信號中以高概率恢復出原始信號。

CS理論主要包括信號稀疏變換、測量矩陣設計和重構算法三個方面。測量矩陣的設計決定了此理論能否成功實現(xiàn)以及是否適合應用于實際。在各類測量矩陣中，Toeplitz結構矩陣由于存儲和計算的復雜度低，而且硬件實現(xiàn)容易，使得它們具有更為廣泛的實際應用，也是測量矩陣設計研究的重點。如近年提出的在特定條件下的基于粒子群優(yōu)化算法的Toeplitz結構矩陣改進方法[3]，以及在需要更多的測量值的代價下，以分段Toeplitz矩陣進行測量[4]。本文在研究Toeplitz矩陣[5]和廣義輪換矩陣[6]的基礎上，引入隨機循環(huán)的思想，提出對Toeplitz結構矩陣的改進方法。新矩陣與原矩陣相比，在相同的觀測值時，對原信號具有更好的重構性能。

1 壓縮感知理論框架

CS理論從信號的內(nèi)部結構出發(fā)，指出信號的采樣頻率不再取決于信號的帶寬，而依賴于兩個重要的特征：稀疏性和不相干性。

考慮一實值的有限長一維離散時間信號f，一維空間的N個離散采樣點可以看作為RN空間N×1維列向量。信號f本身可能是稀疏的或可壓縮的。然而，更一般的情況是信號f在某個適當?shù)幕蜃值渲杏幸粋€稀疏的展開式。例如，f可以表示成RN空間的一組標準正交基的線性組合

(1)

式中：Ψ為N×N維矩陣；向量Θ則是信號f在變換基Ψ下的系數(shù)，而變換后Θ的N個系數(shù)滿足稀疏性或可壓縮性。

CS理論的測量過程是用與系數(shù)變換基Ψ不相干的M×N(M≤N)維測量矩陣Φ去獲得M個觀測值，該過程是非自適應的。線性測量過程可以寫成如下形式：Y=Φf=ΦΨΘ=AcsΘ。變換基Ψ和測量矩陣Φ的互相干程度越小，重構信號所需的測量值越少，成功重構信號的概率就越高[7]。

信號的重構是指由M個觀測值去重構長度為N的稀疏信號過程。可以通過求解如下最優(yōu)化問題得到滿足條件的稀疏解

在種植小麥時期，應降低病蟲害基礎。在防止病蟲害時，可實行有效的防治手段，有效結合農(nóng)業(yè)和化學防治，進行精耕細作和晚播，進而增強麥苗的抵抗力，同時降低麥苗發(fā)病率。可以使用藥劑攪拌、包衣等方法，還應做好土壤處理，對于不同的病蟲害應使用對應的藥劑做包衣。比如紋枯病，應使用氟環(huán)唑或者是三唑酮殺毒及，然后噴灑水在莖部，定期噴藥，不僅能夠有效治療病癥，還可以防治其他疾病，或者可以使用除草、深耕的方法防治。當出現(xiàn)麥穗蚜病癥時，在使用快殺靈乳油三百到五百毫升，再噴灑水，使病蟲害的得到有效防控。

(2)

然而該問題在現(xiàn)實中是個NP-hard問題。如果感知矩陣Acs滿足受限等距性(Restricted Isometry Property， RIP)性質(zhì)[8]，式(2)等價于求解如下l2范數(shù)

(3)

求解式(3)的計算可行性方法有：基于貪婪類的算法和基于凸優(yōu)化的算法[9]。

2 壓縮感知測量矩陣

2.1 壓縮感知測量矩陣介紹

高斯隨機矩陣、貝努利隨機矩陣以及部分傅里葉矩陣都滿足UUP(Uniform Uncertainty Principle)條件，從而可以高概率的重構原信號[10]。然而在實際應用中，高斯隨機矩陣、貝努利隨機矩陣的完全隨機性給矩陣的存儲，硬件的設計等都帶來了困難，同時需要大量的獨立重復實驗來消除矩陣的隨機性帶來的仿真結果的不確定性。部分傅里葉矩陣只與時域稀疏信號不相干，然而時域稀疏的信號往往極少存在。

Toeplitz矩陣和循環(huán)矩陣[5]是其元素獨立的抽取于滿足特定概率分布的結構化隨機矩陣。Toeplitz矩陣的具體構造方法是：先生成一個M+N-1維行向量μ=(μ1,μ2，…，μN，…，μM+N-1)，其中μi服從式(4)的概率分布

(4)

然后通過循環(huán)移位生成形如式(5)的M×N維矩陣

(5)

2.2 基于行列式隨機循環(huán)的測量矩陣設計

形如式(5)的測量矩陣在實際應用中與其他類矩陣相比具有以下優(yōu)點：1)僅需O(N)個獨立隨機變量，減小了存儲量；2)矩陣的特殊結構使得矩陣相乘可以借助快速傅里葉變換實現(xiàn)；3)循環(huán)矩陣在某些特殊的應用能自然產(chǎn)生。因此，本文將對此類結構化隨機矩陣做進一步研究并加以改進，使其在信號重建上具有更好的性能。

測量矩陣需要滿足UUP條件，然而直接驗證測量矩陣滿足UUP條件通常是困難的，但測量矩陣Φ在滿足條件CS1～CS3時求解式(2)和式(3)是等價的[1]，也就是說滿足CS1～CS3條件的測量矩陣同樣可以恢復出原信號。本文測量矩陣的設計將以CS1～CS3為準則。

普通循環(huán)矩陣是基于矩陣第一行元素依次循環(huán)得到，即第二行在第一行的基礎上左移或右移一位，第三行在第二行的基礎上左移或右移一位(也可看成第三行是在第一行的基礎上左移或右移兩位)，其余行采用相同的方法依次產(chǎn)生。事實上，由滿足特定分布的隨機數(shù)生成的隨機矩陣或?qū)⒛骋徽痪仃嚨男辛羞M行隨機的互換而得到的矩陣與任一給定矩陣的不相干程度也非常大[7]。本文將在普通循環(huán)矩陣的基礎上引入隨機循環(huán)的思想，即矩陣的第2～M行元素將通過第一行元素的隨機循環(huán)得到。在隨機循環(huán)中，為了確保不產(chǎn)生重復的行向量，將根據(jù)生成的M-1個均勻隨機數(shù)來決定第i行相對于第一行的循環(huán)步數(shù)。廣義輪換矩陣[6]通過對部分矩陣元素乘以常數(shù)a(a>1)來提高列向量之間的不相干性。事實上，對Toeplitz結構的矩陣的部分元素有規(guī)律的乘以常數(shù)a(a>1) 可以增大矩陣的最小奇異值。矩陣的最小奇異值和其線性獨立性是密切相關的，增大矩陣的最小奇異值，可以使其線性獨立性增強；而當其最小奇異值趨于0時，其獨立性也逐漸消失[11]。綜上所述，本文在參照普通循環(huán)矩陣生成方法時，通過生成的均勻隨機數(shù)對行列式進行隨機循環(huán)以得到測量矩陣的其他行元素，同時結合廣義輪換矩陣的優(yōu)點構造出基于行列式隨機循環(huán)的測量矩陣。

具體構造過程如下：

1)采用[-1，1] 作為向量原子：使用RANDOMIZE-IN-PLACE算法(該方法可以產(chǎn)生N個數(shù)的均勻隨機排列[12])隨機生成值為1～N的N個隨機數(shù)，存在一維數(shù)組Arr中；然后將這N個隨機數(shù)中小于N/2的數(shù)置為-1，大于N/2的數(shù)置為1，從而確保Arr讓每個元素都滿足特定概率(P(μi=+1)=P(μi=-1)=0.5)的隨機數(shù)組。

2)同樣以RANDOMIZE-IN-PLACE算法隨機生成值為 1～(M-1) 的M-1個隨機數(shù)用于第2～M行的隨機循環(huán)，M-1 個隨機數(shù)存在一維數(shù)組Cir(數(shù)組下標從1開始)中。這些用于矩陣循環(huán)的均勻隨機數(shù)可以進一步增加測量矩陣與信號之間的非相干性，保證測量矩陣滿足CS1～CS3條件。

3)將Arr=[μ1,μ2，…，μN]作為測量矩陣的第一行。通過步驟1)生成的隨機數(shù)組使得矩陣行元素具有跟噪聲類似的獨立隨機性。

4)測量矩陣第i(i=2，3,…,M)行的構造方法是：從數(shù)組Cir中選取Cir[i-1]作為第i行的相對于第一行的循環(huán)步數(shù)，例如：第二行而相對第一行向右循環(huán)Cir[1]步；同時為了進一步增大元素間的不相干性，改進參考廣義輪換矩陣中的方法，在每次循環(huán)后將前Cir[i-1]個元素同時乘以常數(shù)a或b(如果i是偶數(shù)則乘以常數(shù)a，否則乘以常數(shù)b，且b>a>1)作為測量矩陣的第i行。如前所述，對每行的前Cir[i-1]個元素乘以常數(shù)a或b增大了矩陣的線性獨立性。

3 實驗結果與分析

本節(jié)主要對文中提及的常用測量矩陣和新測量矩陣進行仿真，對比并驗證新的基于行列式隨機循環(huán)矩陣在信號重構上是否具有良好性能。首先，用新矩陣在M/N=0.6時，對標準256×256的圖像(圖像來自于南加州大學USC-SIPI image database)進行采樣壓縮后用新矩陣作為測量矩陣并通過OMP算法進行重構(如圖1)，說明了新矩陣的可行性。然后，分別用高斯隨機矩陣、Toeplitz矩陣、循環(huán)矩陣、廣義輪換矩陣以及新矩陣對大小為256×256的圖像進行感知處理，并通過OMP算法[13]對壓縮感知后的圖像進行重構。將壓縮比分別為0.1，0.2，0.3，0.4和0.5 (M/N>0.5時，各類矩陣相對誤差差別較小) 的重構相對誤差繪制如表1。針對壓縮比M/N≤0.6 (仿真數(shù)據(jù)表明M/N=0.55時重構圖像和原圖像的匹配度已達到0.99)情況，將得到平均峰值信噪比(PSNR)繪制在圖2中。實驗在Windows7的32位操作系統(tǒng)，CPU主頻2.1 GHz配置下運行MATLAB R2009a，所得結果是50次獨立重復實驗的平均值。

圖1 實驗對比

測量矩陣不同壓縮比(M/N)下的重構相對誤差0102030405高斯矩陣1762312370020780015600064Toeplitz矩陣1900812945023900017400070循環(huán)矩陣1951012218028280015000051廣義循環(huán)矩陣0771200265000690003300017新矩陣0278500161000570003000016

圖2 常見壓縮感知測量矩陣和新矩陣在同一重構算法下的峰值信噪比(PSNR)比較

衡量各類矩陣在信號重建上的性能標準主要有峰值信噪比、信噪比、相對誤差、以及運算時間等。本文以能直觀反映重構圖像質(zhì)量的相對誤差和峰值信噪比作為比較標準。由圖1b可以看出，新矩陣可以理想的重建出原圖像，而所需的測量值僅為原始數(shù)據(jù)長度的0.6倍。由表1可以看出新矩陣的重構相對誤差在相同壓縮比時始終最小。由圖2可以看出Toeplitz矩陣、循環(huán)矩陣以及高斯隨機矩陣的性能相當。新矩陣的重建性能較常用測量矩陣(高斯隨機矩陣、Toeplitz矩陣和循環(huán)矩陣)有很大的改善，這很大程度上歸功于循環(huán)移位時所乘的常數(shù)，它們增大了矩陣的行向量間的獨立性。仿真結果表明，新矩陣重建信號的PSNR值要比常用矩陣高出4～18 dB，并且壓縮比越小新矩陣優(yōu)勢越明顯。新矩陣重建性能整體優(yōu)于廣義輪換矩陣，二者在結構上的區(qū)別在于：1)新矩陣的第2-M行是通過第一行隨機循環(huán)而得；2)使用a，b兩個不同的常數(shù)增大矩陣的非相干性。這種改進帶來的優(yōu)勢隨著重構矩陣所需的測量數(shù)增大而逐漸減弱，這是因為二者本質(zhì)上都來源于對循環(huán)矩陣的改進。

4 小結

本文在介紹壓縮感知理論的基礎上，研究了該理論中的測量矩陣設計。在介紹了常用的測量矩陣及其優(yōu)缺點后，對性能較好且容易實現(xiàn)的循環(huán)矩陣進行進一步的研究。本文在循環(huán)矩陣的基礎上，借鑒廣義輪換矩陣的優(yōu)點，提出基于行列式隨機循環(huán)的新矩陣，新矩陣在實際應用中具有和循環(huán)矩陣相同的優(yōu)點[5]，而新矩陣對信號的重建性能則有很大的改善。最后，通過對二維圖像的仿真，對比了文中提到的常用矩陣的性能，直觀地表述了新矩陣的良好性能。

[1] DAVID L DONOHO. Compressed Sensing[J]. IEEE Trans. Information Theory，2006， 52(4)：1289-1306.

[2] EMMANUEL J CANDE S. Compressive sampling[J]. Proceedings of the International Congress of Mathematicians，2006(3)：1433-1452.

[3] MASOMEH A，AGHAGOLZADEH A，MARVASTI F. Towards optimization of toeplitz matrices for compressed sensing[C]//Proc. 2013 Iran Workshop on Communication and Information Theory (IWCIT). Tehran： IEEE Press， 2013：1-5.

[4] LI K， CRISTIAN R R， SAIKAT C， et al. Piecewise toeplitz matrices-based sensing for rank minimization[C]//Proc. the 22nd European Signal Processing Conference. Lisbon： IEEE Press，2014：1836-1840.

[5] WAHEED U B，JARVIS D H，GIL M R， et al. Toeplitz-structured compressed sensing matrices [C]//Proc. the IEEE Workshop on Statistical Signal Processing.[S.l.]：IEEE Press，2007：294-298.

[6] 李浩. 用于壓縮感知的確定性測量矩陣研究[D].北京：北京交通大學，2011.

[7] EMMANUEL J C， MICHAEL B W. An introduction to compressive sampling[J]. IEEE Signal Processing Magazine， 2008， 25(2)： 21-30.

[8] EMMANUEL J C， TERENCE T. Decoding by linear programming[J]. IEEE Trans. Information Theory， 2005， 51(3)：4023-4215.

[9] JOEL A T， STEPHEN J W. Computational methods for sparse solution of linear inverse problems[J]. Proceedings of the IEEE， 2010，

98(16)：948-958.

[10] EMMANUEL J C， TERENCE T. Near-optimal signal recovery from random projections： universal encoding strategies? [J]. IEEE Trans. Information Theory，2006，52(12)：5406-5425.

[11] 傅迎華.可壓縮傳感重構算法與近似QR分解[J].計算機應用，2008，28(9)：2300-2302.

[12] THOMAS H C，CHARLES E L， RONALD L R，et al. Introduction to algorithms[M].3rd ed. Massachusetts，USA： MIT Press，2009.

[13] JOEL A T， ANNA C G. Signal recovery from random measurements via orthogonal matching pursuit [J]. IEEE Trans. Information Theory， 2007， 53(12)： 4655-4666.

Research on Measurement Matrix in Compressed Sensing Based on Random Circulant

WEI Congjinga， TANG Jiashanb

(a.CollegeofTelecommunications&InformationEngineering；b.CollegeofScience，NanjingUniversityofPostsandTelecommunications，Nanjing210023，China)

Compressed sensing， depending on the fact that signals are sparsely or compressive in some fixed basis， samples and compresses the signal by linear projection. Measurement matrix plays the positive role in the theory. The common measurement matrix is researched， especially the structured matrix. As minimizing the coherence is an important way to design measurement matrix， the advantages of circulant matrix and generalized rotation matrix are learned and a new method to design a measurement matrix which based on random circulant is proposed. The simulation results suggest the new matrix has better performance in signal’s reconstruction.

compressed sensing； measurement matrix； Toeplitz matrix；random circulant

TN911.7

A

10.16280/j.videoe.2015.19.002

魏從靜(1989— )，碩士生，主要研究方向為現(xiàn)代通信中的智能信號處理；

2015-03-17

【本文獻信息】魏從靜，唐加山.基于行列式隨機循環(huán)的壓縮感知測量矩陣研究[J].電視技術,2015，39(19).

唐加山(1968— )，教授，博士，主要研究方向為現(xiàn)代通信中的智能信號處理、應用統(tǒng)計等。

責任編輯：時 雯