基于Berlekamp-Justesen碼的壓縮感知確定性測量矩陣的構(gòu)造

夏樹濤劉 璐 劉鑫吉

(清華大學深圳研究生院 深圳 518055)

(清華大學計算機科學與技術(shù)系 北京 100084)

基于Berlekamp-Justesen碼的壓縮感知確定性測量矩陣的構(gòu)造

夏樹濤*劉 璐 劉鑫吉

(清華大學深圳研究生院 深圳 518055)

(清華大學計算機科學與技術(shù)系 北京 100084)

確定性測量矩陣構(gòu)造是近期壓縮感知領(lǐng)域的一個重要研究問題。該文基于Berlekamp-Justesen(B-J)碼，構(gòu)造了兩類確定性測量矩陣。首先，給出一類相關(guān)性漸近最優(yōu)的稀疏測量矩陣，從而保證其具有較好的限定等距性(RIP)。接著，構(gòu)造一類確定性復測量矩陣，這類矩陣可以通過刪除部分行列使其大小靈活變化。第1類矩陣具有很高的稀疏性，第2類則是基于循環(huán)矩陣，因此它們的存儲開銷較小，編碼和重構(gòu)復雜度也相對較低。仿真結(jié)果表明，這兩類矩陣常常有優(yōu)于或相當于現(xiàn)有的隨機和確定性測量矩陣的重建性能。

壓縮感知；Berlekamp-Justesen碼；漸近最優(yōu)；復測量矩陣；限定等距性

1 引言

自2006年Candès等人[1]提出壓縮感知(Compressive Sensing, CS)以來，這種提高海量數(shù)據(jù)壓縮采樣效率的新思路引起了海內(nèi)外學者的廣泛關(guān)注。壓縮感知過程分為兩部分：壓縮采樣和信號重構(gòu)[2]。壓縮采樣過程主要關(guān)注的是如何構(gòu)建有效且魯棒的測量矩陣，這也是本文的重點研究內(nèi)容。信號重構(gòu)重點考慮從低維壓縮采樣數(shù)據(jù)中恢復出原始的高維信號，可靠重建的相關(guān)算法可見文獻[1,3]。

限定等距性(Restricted Isometry Property, RIP)[1,4]是保證壓縮感知信號重建魯棒性的一個很重要的概念。如果一個測量矩陣滿足限定等距性，那么這個矩陣就可以用來對信號進行采樣，并在信號重構(gòu)中保證原始信號的穩(wěn)定和魯棒恢復。

相關(guān)性(coherence)是建立矩陣RIP的一個重要方法。Bourgain等人[5]指出m×n的矩陣Φ的相關(guān)系數(shù)μΦ與限定等距常量δk存在關(guān)系：矩陣Φ滿足k＜1/μΦ+1階RIP，即δk≤μΦ(k?1)。然而，根據(jù)Welch界[6]，當n?m時，μΦ的下界漸近為μΦ≥ 1/。因此，如果從矩陣的相關(guān)性角度來看，至多能構(gòu)造出滿足k=O()階RIP的確定性測量矩陣，稱這類矩陣為相關(guān)性意義下的漸近最優(yōu)測量矩陣。

很多隨機矩陣已經(jīng)被證明是很好的壓縮感知測量矩陣[7]。一些大小為m×n隨機測量矩陣，很大概率上滿足k=O(m/log2(n/m))階RIP[8]，這些矩陣很容易就可以實現(xiàn)，也能很好地恢復稀疏信號。但是，它們的存儲開銷相對較高，且在硬件上較難實現(xiàn)。因此，構(gòu)造存儲量小且性能等價于或優(yōu)于隨機測量矩陣的確定性測量矩陣就顯得意義重大。

目前國內(nèi)外已經(jīng)有不少學者提出了很多確定性測量矩陣構(gòu)造方法。文獻[9]提出了一種基于Chirp函數(shù)的2m×m復測量矩陣；文獻[10]利用光正交碼構(gòu)建了一類三元測量矩陣；文獻[11]基于Reed-Solomon碼構(gòu)建了一類相關(guān)性較小的測量矩陣。近期，浙江大學李抒行等人[12]基于有限幾何構(gòu)造了一大類稀疏的二元測量矩陣。文獻[13]對現(xiàn)有的壓縮感知確定性測量矩陣的構(gòu)造給出了一個比較完善的綜述。

基于Berlekamp-Justesen (B-J)碼，文獻[14]構(gòu)造了一類性能優(yōu)異的低密度奇偶校驗(Low Density Parity Check, LDPC)碼，并將這類LDPC碼的校驗矩陣直接作為測量矩陣應用到壓縮感知中[15]，這類矩陣稱為B-J矩陣。本文基于此B-J矩陣，提出了兩類確定性測量矩陣的構(gòu)造方法。一類通過在B-J矩陣中嵌入Hadamard矩陣或DFT矩陣，使測量矩陣保持稀疏性，并且相關(guān)性達到漸近最優(yōu)。而另一類則構(gòu)建了矩陣大小較為靈活的確定性復測量矩陣[16]，這類矩陣基于循環(huán)矩陣，因此存儲開銷也較小。本文中針對提出的兩類測量矩陣進行仿真實驗，實驗結(jié)果表明這兩類矩陣常常比一些隨機矩陣和確定性測量矩陣效果更好。

2 二元B-J矩陣的構(gòu)造

本節(jié)簡單介紹有限域內(nèi)q -元B-J碼的構(gòu)造和二元B-J測量矩陣的構(gòu)造。更多的細節(jié)可以見文獻[14]。

2.1 q -元B-J碼

令q=2，其中是一個整數(shù)，令CBJ為q-元B-J碼。通過對多項式xq+1?1的分解，CBJ的生成多項式可以寫為

CBJ中的所有碼字為

2.2 第1類B-J矩陣：通過q -元組替換B-J碼

已知GF(q)={0,1,α,α2,…,αq?2}，且αq?1=1，記α?∞=0。定義αj(j=?∞,0,1,…,q?2)在GF(q)中的位置向量為y(αj)=(y?∞,y0,y1,…,yq?2)，其中yj=1，其他元素均為0。

對于i =?∞,0,1,…,q?2，定義CBJ中的碼字子集為

其中g(shù) =(1,g1,g2,…,gq?1,0),g '=(0,1,g1,g2,…,gq?1)。

設(shè)Ai(1)為GF(q)上C(i1)中的所有碼字作為行組成的矩陣。對i=?∞,1,2,…,q+1，用q -元組替換Ai(1)中每個元素，則得到q×(q+1)q 的矩陣Bi(1)= (JiPi(,11)…Pi(,q1))。最后的矩陣H(1)=(B?(1∞)B0(1)B(1)…B(1?))T。

1q2

2.3 第2類B-J矩陣：通過(q -1)-元組替換B-J碼

定義αj(j=0,1,…,q?2)在GF(q)中的位置向量為y(αj)=(y0,y1,…,yq?2)，其中yj=1，其他元素均為0，GF(q)中的0位置向量則為全0的(q -1)-元組。

對i=1,2,…,q +1，定義C*BJ中的一個碼字子集為

3 相關(guān)性漸近最優(yōu)的稀疏矩陣構(gòu)造

本節(jié)基于B-J矩陣提出一類相關(guān)性漸近最優(yōu)的稀疏矩陣構(gòu)造方法。通過采用Hadamard矩陣或者DFT(Discrete Fourier Transform)矩陣對B-J矩陣進行擴展，對于固定的m值，增加矩陣的列生成稀疏測量矩陣。這種列的增加就生成了適用于壓縮感知測量矩陣的相關(guān)性漸近最優(yōu)的稀疏矩陣。

定義1 (相關(guān)性) 設(shè)φi, φj是測量矩陣Φm×n的任意兩列，則矩陣的相關(guān)性為

3.1 構(gòu)造方法

將B-J矩陣與其他相關(guān)性很小的矩陣(例如Hadamard矩陣和DFT矩陣)嵌套生成新的矩陣，利用特殊方式嵌套生成的矩陣可以使相關(guān)性達到漸近最優(yōu)。這種特殊的嵌套方式在文獻[17]中最先提出。

首先，構(gòu)造列重相同的二元矩陣A，本文中即為B-J矩陣，令q=2，則生成的兩類B-J矩陣列重均為q。其次，構(gòu)造相關(guān)性很小的q×q矩陣B。最后，將矩陣A的每一列中第i個1替換成矩陣B的第i行(i=1,2,…,q )，從而生成相關(guān)性漸近最優(yōu)的稀疏矩陣C。記這種嵌套模式為A⊙B ，如圖1所示。

圖1 矩陣結(jié)合模式：A是有常數(shù)列重的二元矩陣，B的行數(shù)與此常數(shù)列重相同

引理1[17]給定一個列重為wm的二元矩陣Am×n1，相關(guān)性為μA。矩陣B的大小為wm×n2，相關(guān)性為μB。令Cm×(n1n2)=Am×n1⊙Bwm×n2，則其相關(guān)性μC=max(μA,μB)。

3.2 嵌套Hadamard矩陣生成相關(guān)性漸近最優(yōu)的測量矩陣

Hadamard矩陣[18]是由元素1和-1生成的方陣，矩陣的任意兩列都是正交的。2階的Hadamard矩陣為：。

如果H2k?1是一個2k?1階的Hadamard矩陣，則：，其中，

證明 H(1)的任意兩列的1中最多有一個位置相同，任意兩行的1中也最多有一個位置相同。所以，矩陣的任意兩列內(nèi)積的最大值為1，即：，其中hi與hj為矩陣H(1)的任意兩列。

另外，因為H(1)的列重為q，顯然，H(1)的相關(guān)性為：μH(1)=1/q 。

因為Hadamard矩陣的相關(guān)性為0。根據(jù)引理1，Φ(1)的相關(guān)性μ=1/q，達到了漸近最優(yōu)。 證畢

證明 矩陣H(2)的任意兩列內(nèi)積的最大值為1，且H(2)的列重為q，則H(2)的相關(guān)性為：μH(2)=1/q。根據(jù)引理1, Φ(2)的相關(guān)性μ=1/q，達到了漸近最優(yōu)。 證畢

3.3 嵌套DFT矩陣生成相關(guān)性漸近最優(yōu)的測量矩陣隨機傅里葉(DFT)矩陣定義[19]：

記Ψq為階為q的DFT矩陣，則Ψq為

定理3 設(shè)q=2，令Φ(3)=H(1)⊙Ψq，則Φ(3)大小為q2×(q3+q2)，相關(guān)性μ=1/q，達到了漸近最優(yōu)。

證明 矩陣H(1)的相關(guān)性為：μH(1)=1/q ，DFT矩陣的相關(guān)性為0。則Φ(3)的相關(guān)性μ=1/q。

證畢

定理4 設(shè)q=2，令Φ(4)=H(2)⊙Ψq，則Φ(4)大小為(q2?1)×(q3?q)，相關(guān)性μ=1/q，達到了漸近最優(yōu)。

證明 矩陣H(2)的相關(guān)性為：μH(2)=1/q ，DFT矩陣相關(guān)性為0。則Φ(4)的相關(guān)性μ=1/q。

證畢

表1總結(jié)了上述相關(guān)性意義下漸近最優(yōu)的測量矩陣，其中μ是矩陣相關(guān)性，k是稀疏性，q是素數(shù)冪。

3.4 矩陣大小調(diào)整

對于一些確定性測量矩陣，刪除部分行列后得到的子矩陣恢復效果相對較差，但是本節(jié)提出的漸近最優(yōu)矩陣在刪除部分行列后性能仍常常較好，仿真效果詳見5.1節(jié)。下面簡單介紹一下矩陣行列的刪除方法。

表 1 大小為m×n的感知矩陣總結(jié)

針對第2類二元B-J矩陣，對任意2≤γ≤ρ≤q , 0≤u≤q?1，當ρ=q+1時，u=0，則調(diào)整大小后的矩陣H(2)(γ,ρ,u)為

其中Li,u(i=1,2,…,γ)是從中刪除最后q?1?u列得到的。的最后(ρ?γ)(q?1)+u列。則最終得到的子矩陣大小為γ(q?1)×[ρ(q?1)+u]l。

選取Hadamard矩陣或者DFT矩陣的前l(fā)列得到子矩陣，從子矩陣中選取前γ?1行嵌入到第2類B-J矩陣的子矩陣(2)(γ,ρ,u) H的前γ(q?1)列，然后從子矩陣中選取前γ行嵌入到子矩陣(2)(γ,ρ,u) H中

4 復測量矩陣的構(gòu)造

本節(jié)基于B-J矩陣，提出一類復測量矩陣的構(gòu)造方法。此類矩陣為循環(huán)矩陣，因此，矩陣的存儲量小，而且矩陣大小調(diào)整更為靈活。

其中g(shù)i≠0∈GF(q )，并且xq+1=1。設(shè)A(λ)是GF(q)上以C(λ)的所有碼字作為行生成的(q+1)×(q+1)矩陣。已知GF(q)={0,α,α2,…,αq?2}，αq?1=1，然后將每個A(λ)中的元素αi替換成i(i∈[1,q?1])，將A(λ)中的0替換成0。A(λ)是循環(huán)矩陣，這樣在實際應用中可以大大節(jié)省存儲空間。

從矩陣A(λ)中選取前m行和前n列，得到子矩陣A(m,n,λ)，m和n根據(jù)本文的需求來定。最后，將矩陣A(m,n,λ)中每一個整數(shù)k∈[0,q?1]通過式(8)轉(zhuǎn)化成復平面單位圓上的點，并將結(jié)果矩陣標準化，這樣就生成了復測量矩陣(2)(m,n,λ) A：

其中i為復數(shù)虛數(shù)單位，akj為矩陣A(m,n,λ)的第k行第j列元素。

因為g(x)所生成的碼字為一個偽隨機序列，則A(λ)矩陣的每一行均相當于一個偽隨機序列，所以，得到的矩陣性能較好。構(gòu)建算法見表2。

表 2 復測量矩陣構(gòu)建算法步驟

這類矩陣的構(gòu)造算法復雜度稍高，但是確定性測量矩陣只需要生成一次，而因為其循環(huán)特性大大減小了存儲量，同時對稀疏信號的恢復效果也比較好，詳見5.2節(jié)仿真部分。

5 仿真實驗

本節(jié)對提出的相關(guān)性漸近最優(yōu)稀疏矩陣和復值矩陣作為測量矩陣進行實驗，將信號恢復效果與一些隨機矩陣和確定性測量矩陣相比較。其中隨機矩陣包括：隨機高斯矩陣和隨機DFT矩陣(隨機選擇DFT矩陣的行)，確定性測量矩陣包括：BCH矩陣[17]和基于Chirp函數(shù)構(gòu)造的矩陣[9]。

5.1 相關(guān)性漸近最優(yōu)稀疏矩陣

5.1.1 嵌套Hadamard矩陣生成的相關(guān)性漸近最優(yōu)稀疏矩陣 令q=24，第1類B-J矩陣H(1)的大小為256×272，通過嵌套16階的Hadamard矩陣得到的相關(guān)性漸近最優(yōu)的稀疏矩陣Φ(1)大小為256×4352，矩陣的相關(guān)性為1/16。令γ=12,ρ=16,l=12，得到的子矩陣大小為192×3072。為了更好地進行評估，本文實現(xiàn)相同大小的隨機矩陣作為測量矩陣進行信號恢復：隨機高斯矩陣(在圖中標為“Rnd”)。利用這些測量矩陣進行信號恢復所得到的信號完全恢復百分比結(jié)果見圖2(相關(guān)性漸近最優(yōu)稀疏矩陣標注為“BJ1+Had”)?？梢?，此矩陣信號恢復效果比隨機矩陣效果好。

令q=24，第2類B-J矩陣H(2)的大小為255×255，通過嵌套16階的Hadamard矩陣得到的相關(guān)性漸近最優(yōu)稀疏矩陣Φ(2)大小為255×4080，矩陣的相關(guān)性為1/16。令γ=12, ρ=16, u=0, l=12，得到的子矩陣大小為180×3060。信號恢復所得到的信號完全恢復百分比結(jié)果見圖3(相關(guān)性漸近最優(yōu)稀疏矩陣標注為“BJ2+Had”)。容易看出，此矩陣信號恢復效果比隨機矩陣效果好。

5.1.2 嵌套DFT矩陣生成的相關(guān)性漸近最優(yōu)稀疏矩陣 令q=24，第1類B-J矩陣H(1)的大小為256×272，通過嵌套16階的DFT矩陣得到的相關(guān)性漸近最優(yōu)稀疏矩陣Φ(3)大小為256×4352，矩陣的相關(guān)性為1/16。令γ=12, ρ=16, l=12，得到的子矩陣大小為192×3072。為了更好地進行評估，本文使用相同大小的復值隨機矩陣作為測量矩陣進行信號恢復：復值隨機高斯矩陣(在圖中標為“ComRnd”)和隨機DFT矩陣(在圖中標為“RndDFT”)。利用這些測量矩陣進行信號恢復所得到的信號完全恢復百分比結(jié)果見圖4(相關(guān)性漸近最優(yōu)稀疏矩陣標注為“BJ1+DFT”)。從圖4可以看出，此矩陣信號恢復效果比隨機矩陣效果好。

令q=24，第2類B-J矩陣H(2)的大小為255×255，通過嵌套16階的DFT矩陣得到的相關(guān)性漸近最優(yōu)稀疏矩陣Φ(4)大小為255×4080，矩陣的相關(guān)性為1/16。令γ=12, ρ=16, u=0, l=12，得到的子矩陣大小為180×3060。信號恢復所得到的信號完全恢復百分比結(jié)果見圖5(相關(guān)性漸近最優(yōu)稀疏矩陣標注為“BJ2+DFT”)。可見，此矩陣信號恢復效果比隨機矩陣效果好。

5.2 復測量矩陣

對復測量矩陣進行仿真實驗，將信號恢復效果與復值隨機高斯矩陣、BCH矩陣[17]、基于Chirp函數(shù)的矩陣[9]和隨機DFT矩陣(隨機選擇DFT矩陣的行)相比較。

令q=210, m=248, n=1023, λ=1，復測量矩陣A(2)(248,1023,1)的大小為248×1023。為了更好地進行評估，我們使用相同大小的復值矩陣作為測量矩陣進行信號恢復：BCH矩陣(在圖中標為“BCH”)、基于Chirp函數(shù)的矩陣(在圖中標為“Chirp”)、復值隨機高斯矩陣(在圖中標為“ComRnd”)和隨機DFT矩陣(在圖中標為“RndDFT”)。利用這些測量矩陣進行信號恢復所得到的信號完全恢復百分比結(jié)果見圖6(最后的復測量矩陣標注為“q-ary Complex”)。圖6顯示出此矩陣信號恢復效果比隨機矩陣效果好。

圖2 256×4352相關(guān)性漸近最優(yōu)矩陣Φ(1)和192×3072的子矩陣作為測量矩陣得到的信號完全恢復百分比隨稀疏度變化

圖3 255×4080相關(guān)性漸近最優(yōu)矩陣Φ(2)和180×3060的子矩陣作為測量矩陣得到的信號完全恢復百分比隨稀疏度變化

圖4 256×4352相關(guān)性漸近最優(yōu)矩陣Φ(3)和192×3072的子矩陣作為測量矩陣得到的信號完全恢復百分比隨稀疏度變化

圖5 255×4080相關(guān)性漸近最優(yōu)矩陣Φ(4)和180×3060的子矩陣作為測量矩陣得到的信號完全恢復百分比隨稀疏度變化

圖6 248×1023的復測量矩陣A(2)(248,1023,1)作為測量矩陣得到的信號完全恢復百分比隨稀疏度變化

最后，本文對512×512的辣椒圖進行信號恢復，見圖7。原始圖像信號通過DCT塊變換，圖像壓縮采樣率為0.2(k/n=0.2)(自然圖像的塊恢復壓縮感知算法見文獻[20])。將圖像分為16×16塊，本文利用205×1024復測量矩陣A(2)(205,1024,1)對每一塊圖像壓縮采樣，并進行圖像恢復。從圖7可以看出，復測量矩陣恢復圖像的PSNR值比其他矩陣要好。

與圖7仿真實驗相同，對512×512的辣椒圖進行信號恢復，原始圖像進行DCT變換。將圖像分為16×16塊，圖像壓縮采樣率為γ，對每一塊辣椒圖分別通過大小為1024γ×1024的不同測量矩陣進行壓縮采樣，并進行信號恢復，結(jié)果見圖8。從圖8可以看出，在壓縮采樣率比較小的情況下(小于0.5)，復測量矩陣恢復圖像的PSNR值比其他矩陣要好。

圖7 利用不同測量矩陣對圖像壓縮采樣所得到的圖像恢復效果

圖8 復測量矩陣圖像恢復得到的PSNR隨壓縮采樣率變化

6 結(jié)束語

本文基于Berlekamp-Justesen(B-J)碼，構(gòu)造了兩種確定性測量矩陣：一種是相關(guān)性漸近最優(yōu)的確定性稀疏測量矩陣，另一種是確定性復測量矩陣。本文對相關(guān)性漸近最優(yōu)的確定性稀疏測量矩陣給出了靈活調(diào)整矩陣大小的方法；而確定性復測量矩陣可以通過簡單刪除部分行和列使其大小靈活變動。另外，這兩類矩陣中第1類有很高的稀疏性，第2類基于循環(huán)矩陣，所以具有存儲開銷較小、編碼和重構(gòu)復雜度相對較低等優(yōu)良特性。仿真結(jié)果表明，在許多情況下，本文提出的兩種矩陣比一些隨機矩陣和確定性測量矩陣效果更好。

[1] Candès E J, Romberg J, and Tao T. Robust uncertainty principles: Exact signal reconstruction from highlyincomplete frequency information[J]. IEEE Transactions on Information Theory, 2006, 52(2): 489-509.

[2] 金堅, 谷源濤, 梅順良. 壓縮采樣技術(shù)及其應用[J]. 電子與信息學報, 2010, 32(2): 470-475. Jin Jian, Gu Yuan-tao, and Mei Shun-liang. An introduction to copressive sampling and its applications[J]. Journal of Electronics & Information Technology, 2010, 32(2): 470-475.

[3] Tropp J A and Gilbert A C. Signal recovery from random measurements via orthogonal matching pursuit[J]. IEEE Transactions on Information Theory, 2007, 53(12): 4655-4666.

[4] Candès E J and Tao T. Decoding by linear programming[J]. IEEE Transactions on Information Theory, 2005, 51(12): 4203-4215.

[5] Bourgain J, Dilworth S, Ford K, et al.. Explicit constructions of RIP matrices and related problems[J]. Duke Mathematical Journal, 2011, 159(1): 145-185.

[6] Welch L. Lower bounds on the maximum cross correlation of signals[J]. IEEE Transactions on Information Theory, 1974, 20(3): 397-399.

[7] Baraniuk R, Davenport M, DeVore R, et al.. A simple proof of the restricted isometry property for random matrices[J]. Constructive Approximation, 2008, 28(3): 253-263.

[8] Candès E J and Tao T. Near-optimal signal recovery from random projections: universal encoding strategies?[J]. IEEE Transactions on Information Theory, 2006, 52(12): 5406-5425.

[9] Applebaum L, Howard S D, Searle S, et al.. Chirp sensing codes: deterministic compressed sensing measurements for fast recovery[J]. Applied and Computational Harmonic Analysis, 2009, 26(2): 283-290.

[10] Yu Nam Yul and Zhao Na. Deterministic construction of real-valued ternary sensing matrices using optical orthogonal codes[J]. IEEE Signal Processing Letters, 2013, 20(11): 1106-1109.

[11] Mohades M, Mohades A, and Tadaion A. A Reed-Solomon code based measurement matrix with small coherence[J]. IEEE Signal Processing Letters, 2014, 21(7): 839-843.

[12] Li Shu-xing and Ge Gen-nian. Deterministic construction of sparse sensing matrices via finite geometry[J]. IEEE Transactions on Signal Processing, 2014, 62(11): 839-843.

[13] 王強, 李佳, 沈毅. 壓縮感知中確定性測量矩陣構(gòu)造算法綜述[J]. 電子學報, 2013, 41(10): 2041-2050. Wang Qiang, Li Jia, and Shen Yi. A survey on deterministic measurement matrix construction algorithms incompressive sensing[J]. Acta Electronica Sinica, 2013, 41(10): 2041-2050.

[14] Ge Xin and Xia Shu-tao. LDPC codes based on Berlekamp-Justesen codes with large stopping distances[C]. Preceedings of IEEE Information Theory Workshop (ITW), Chengdu, 2006: 214-218.

[15] Li Dan-dan, Liu Xin-ji, and Xia Shu-tao. A class of deterministic construction of binary compressed sensing matrices[J]. Journal of Electronics (China), 2012, 29(6): 493-500.

[16] Liu Lu, Liu Xin-ji, and Xia Shu-tao. Deterministic complex-valued measurement matrices based on Berlekamp-Justesen codes[C]. Proceedings of IEEE China Summit & International Conference on Signal and Information Processing (ChinaSIP), Xi'an, China, 2014: 723-727.

[17] Amini A, Montazerhodjat V, and Marvasti F. Matrices with small coherence using p-ary block codes[J]. IEEE Transactions on Signal Processing, 2012, 60(1): 172-181.

[18] Pratt W, Kane J, and Andrews H C. Hadamard transform image coding[J]. Proceedings of the IEEE, 1969, 57(1): 58-68.

[19] Kalogerias D S and Petropulu A P. RIP bounds for naively subsampled Scrambled Fourier sensing matrices[C]. Proceedings of 48th Annual Conference on Information Sciences and Systems (CISS), Princeton, USA, 2014: 1-6.

[20] Gan Lu. Block compressed sensing of natural images[C]. Proceedings of 15th International Conference on Digital Signal Processing (DSP), Cardiff , UK, 2007: 403-406.

夏樹濤： 男，1972年生，教授，博士生導師，研究方向為信道編碼、網(wǎng)絡(luò)編碼和壓縮感知等.

劉 璐： 女，1989年生，碩士生，研究方向為壓縮感知確定性測量矩陣構(gòu)造.

劉鑫吉： 男，1989年生，博士生，研究方向為壓縮感知、編碼理論和分布式存儲.

Deterministic Constructions of Compressive Sensing Matrices Based on Berlekamp-Justesen Codes

Xia Shu-tao Liu Lu Liu Xin-ji
(Graduate School at Shenzhen, Tsinghua University, Shenzhen 518055, China)
(Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China)

Nowadays the deterministic construction of sensing matrices is a hot topic in compressed sensing. Two classes of deterministic sensing matrices based on the Berlekamp-Justesen (B-J) codes are proposed. Firstly, a class of sparse sensing matrices with near-optimal coherence is constructed. It satisfies the Restricted Isometry Property (RIP) well. Afterwards, a class of deterministic complex-valued matrices is proposed. The row and column numbers of these matrices are tunable through the row and column puncturing. Moreover, the first proposed matrices are high sparsity and the second matrices are able to obtain from the cyclic matrices, thus the storage costs of them are relatively low and both the sampling and recovery processes can be simpler. The simulation results demonstrate that the proposed matrices often perform comparably to, or even better than some random matrices and deterministic measurement matrices.

Compressive Sensing (CS); Berlekamp-Justesen (B-J) codes; Near-optimal; Complex matrix; Restricted Isometry Property (RIP)

TN911.72

： A

：1009-5896(2015)04-0763-07

10.11999/JEIT140875

2014-07-02收到，2014-12-02改回

國家973計劃項目(2012CB315803)，國家自然科學基金(61371078)和高等學校博士學科點專項科研基金(20130002110051)資助課題

*通信作者：夏樹濤 xiast@sz.tsinghua.edu.cn