魏從靜，唐加山

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

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

魏從靜a，唐加山b

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

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

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

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

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

1 壓縮感知理論框架

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

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

(1)

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

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

信號(hào)的重構(gòu)是指由M個(gè)觀測(cè)值去重構(gòu)長(zhǎng)度為N的稀疏信號(hào)過(guò)程。可以通過(guò)求解如下最優(yōu)化問(wèn)題得到滿足條件的稀疏解

在種植小麥時(shí)期，應(yīng)降低病蟲(chóng)害基礎(chǔ)。在防止病蟲(chóng)害時(shí)，可實(shí)行有效的防治手段，有效結(jié)合農(nóng)業(yè)和化學(xué)防治，進(jìn)行精耕細(xì)作和晚播，進(jìn)而增強(qiáng)麥苗的抵抗力，同時(shí)降低麥苗發(fā)病率?？梢允褂盟巹嚢?、包衣等方法，還應(yīng)做好土壤處理，對(duì)于不同的病蟲(chóng)害應(yīng)使用對(duì)應(yīng)的藥劑做包衣。比如紋枯病，應(yīng)使用氟環(huán)唑或者是三唑酮?dú)⒍炯埃缓髧姙⑺谇o部，定期噴藥，不僅能夠有效治療病癥，還可以防治其他疾病，或者可以使用除草、深耕的方法防治。當(dāng)出現(xiàn)麥穗蚜病癥時(shí)，在使用快殺靈乳油三百到五百毫升，再噴灑水，使病蟲(chóng)害的得到有效防控。

(2)

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

(3)

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

2 壓縮感知測(cè)量矩陣

2.1 壓縮感知測(cè)量矩陣介紹

高斯隨機(jī)矩陣、貝努利隨機(jī)矩陣以及部分傅里葉矩陣都滿足UUP(Uniform Uncertainty Principle)條件，從而可以高概率的重構(gòu)原信號(hào)[10]。然而在實(shí)際應(yīng)用中，高斯隨機(jī)矩陣、貝努利隨機(jī)矩陣的完全隨機(jī)性給矩陣的存儲(chǔ)，硬件的設(shè)計(jì)等都帶來(lái)了困難，同時(shí)需要大量的獨(dú)立重復(fù)實(shí)驗(yàn)來(lái)消除矩陣的隨機(jī)性帶來(lái)的仿真結(jié)果的不確定性。部分傅里葉矩陣只與時(shí)域稀疏信號(hào)不相干，然而時(shí)域稀疏的信號(hào)往往極少存在。

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

(4)

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

(5)

2.2 基于行列式隨機(jī)循環(huán)的測(cè)量矩陣設(shè)計(jì)

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

測(cè)量矩陣需要滿足UUP條件，然而直接驗(yàn)證測(cè)量矩陣滿足UUP條件通常是困難的，但測(cè)量矩陣Φ在滿足條件CS1～CS3時(shí)求解式(2)和式(3)是等價(jià)的[1]，也就是說(shuō)滿足CS1～CS3條件的測(cè)量矩陣同樣可以恢復(fù)出原信號(hào)。本文測(cè)量矩陣的設(shè)計(jì)將以CS1～CS3為準(zhǔn)則。

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

具體構(gòu)造過(guò)程如下：

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

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

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

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

3 實(shí)驗(yàn)結(jié)果與分析

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

圖1 實(shí)驗(yàn)對(duì)比

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

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

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

4 小結(jié)

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

[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] 李浩. 用于壓縮感知的確定性測(cè)量矩陣研究[D].北京：北京交通大學(xué)，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] 傅迎華.可壓縮傳感重構(gòu)算法與近似QR分解[J].計(jì)算機(jī)應(yīng)用，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— )，碩士生，主要研究方向?yàn)楝F(xiàn)代通信中的智能信號(hào)處理；

2015-03-17

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

唐加山(1968— )，教授，博士，主要研究方向?yàn)楝F(xiàn)代通信中的智能信號(hào)處理、應(yīng)用統(tǒng)計(jì)等。

責(zé)任編輯：時(shí) 雯