楊俊坡，劉文遠(yuǎn)

(陜西科技大學(xué) 電子信息與人工智能學(xué)院, 陜西 西安 710021)

0 引言

2006年，壓縮感知(Compressed sensing，CS)的相關(guān)理論首次由Donoho和Candès等[1,2]學(xué)者提出，以遠(yuǎn)低于信號頻率的采樣率完成稀疏信號的采樣和重構(gòu)，從而實(shí)現(xiàn)與Nyquist采樣定理不同的全新采樣算法.由于其信號采樣率不再受Nyquist采樣定理的限制，壓縮感知的理論研究受到了學(xué)術(shù)界的廣泛關(guān)注.一般而言，壓縮感知算法的計(jì)算過程主要可分為數(shù)據(jù)采樣和信號重構(gòu).在數(shù)據(jù)采樣過程中，優(yōu)秀的測量矩陣可將高維原始信號投影至低維空間，以較低的計(jì)算強(qiáng)度獲取相同精度的數(shù)據(jù)；在信號重構(gòu)過程中，優(yōu)秀的測量矩陣以更高的概率精確地重構(gòu)原始的稀疏信號.總之，測量矩陣直接決定了壓縮感知算法的信號采樣和重構(gòu)質(zhì)量.

隨著壓縮感知理論研究和應(yīng)用技術(shù)的逐漸深入，很多學(xué)者做出了大量的研究[3-13].其中，Candes和Tao[14]在文獻(xiàn)中提出了測量矩陣的約束等距性(Restricted Isometry Property，RIP)，結(jié)果表明，測量矩陣需要滿足RIP性質(zhì)，才可以以較高的概率精確地重構(gòu)原始信號.根據(jù)這一結(jié)論，文獻(xiàn)[4-6]分別基于LDPC(Low Density Parity Check)碼、Berlekamp-Justesen碼和Vandermonde矩陣提出了確定性測量矩陣的構(gòu)造方法，極大地豐富了確定性測量矩陣的種類.然而，這些測量矩陣均存在硬件實(shí)現(xiàn)復(fù)雜的缺點(diǎn)，這導(dǎo)致壓縮感知算法的實(shí)際應(yīng)用受到較大的限制.

為了解決確定性測量矩陣硬件實(shí)現(xiàn)復(fù)雜的問題，文中從m序列的采樣序列出發(fā)，引入了具有較低相關(guān)性的二進(jìn)制偽隨機(jī)序列，在此基礎(chǔ)上，利用該序列的雙極性矩陣構(gòu)造確定性的測量矩陣.仿真實(shí)驗(yàn)表明，在同條件的壓縮感知算法中，本文提出的測量矩陣的重構(gòu)性能優(yōu)于Gaussian隨機(jī)矩陣.

1 預(yù)備知識

1.1 壓縮感知

在壓縮感知算法中，不妨用Φ表示M×N維的測量矩陣(M×N)，此外，X表示N維的原始信號，且該信號是k稀疏的，Y表示經(jīng)過采樣的M維觀測信號.在信號采樣過程中，原始信號、測量矩陣和觀測信號之間存在線性的關(guān)系：

Y=ΦX

(1)

而在壓縮感知算法中，信號的重構(gòu)計(jì)算屬于非線性的NP困難問題，即通過使用最小1范數(shù)優(yōu)化方法，將觀測信號Y重構(gòu)成原始信號X，其計(jì)算過程如式(2)所示：

(2)

目前，應(yīng)用最小1范數(shù)優(yōu)化方法的具體算法主要包括基追蹤(Basis Pursuit，BP)、貪婪追蹤類和正交匹配追蹤(Orthogonal Matching Pursuit，OMP)等算法.一般而言，OMP等追蹤算法利用多輪迭代的方法得到局部最優(yōu)解，盡量逼近全局最優(yōu)解，從而最終獲取原始信號的精確估計(jì)值.

定義1對于維度為M×N的測量矩陣Φ，不妨設(shè)φ0,φ1,…,φN-1表示Φ的列向量，即Φ=[φ0,φ1,…,φN-1]，則其測量矩陣Φ的相關(guān)性μ(Φ)定義如式(3)所示

(3)

其中，〈φi,φj〉表示列向量φi與φj之間的內(nèi)積，‖φi‖表示第i+1個列向量的模長.

由引理1可知，如果降低測量矩陣的相關(guān)性，則可重構(gòu)信號x′的稀疏度k可以增加.總之，在構(gòu)造過程中，測量矩陣的相關(guān)性應(yīng)該盡量降低，從而改善壓縮感知算法的重構(gòu)性能.

1.2 有限域

由于測量矩陣的構(gòu)造需要使用偽隨機(jī)序列，所以文中仍需要介紹一些有限域的基本知識.這里不妨使用Fp表示包含p個元素的有限域，其中p是素數(shù)，其本原元元素為α.n為正整數(shù)且q=pn，則Fq是有限域Fp的擴(kuò)域，所含元素的表示為{0,1,…,q-1}.此外，F(xiàn)q{0}是包含q-1個元素的乘法群，其群元素表示為{1,α1,α2,…,αpn-2}.

定義2設(shè)p為素數(shù)，n和m均為正整數(shù)，且m|n，x∈Fpn，則從域Fpn到其子域Fpm的跡函數(shù)公式為

(4)

2 測量矩陣

為了構(gòu)造具有優(yōu)秀信號重構(gòu)功能的確定性測量矩陣，基于傳統(tǒng)的m序列，通過調(diào)整其采樣系數(shù)，分別獲取了奇數(shù)和偶數(shù)情況下的二進(jìn)制偽隨機(jī)序列，并且使用跡函數(shù)的方式，構(gòu)造具有雙極性特征的確定性測量矩陣.

2.1 矩陣構(gòu)造

偽隨機(jī)序列是具有隨機(jī)特性的確定序列，一般由m序列經(jīng)過采樣或組合形成.其中，采樣的m序列可以直接使用有限域中的跡函數(shù)進(jìn)行表示，而跡函數(shù)中自變量的指數(shù)，即為偽隨機(jī)序列的采樣系數(shù).利用這樣的方法，文中分別引入奇數(shù)和偶數(shù)情況下的二進(jìn)制偽隨機(jī)序列，在此基礎(chǔ)上，利用跡函數(shù)的結(jié)構(gòu)，提出雙極性測量矩陣的構(gòu)造方法和相應(yīng)公式.

定義3設(shè)l和ρ是正整數(shù)且ρ∈[1,l]，設(shè)定由有限域元素組成的矩陣Λ2nρ×ρ，令λi,j(0≤i≤2nρ-1,

0≤j≤ρ-1)表示第i+1行第j+1列的矩陣元素，這兩者之間的關(guān)系如式(5)所示.

Λ2nρ×ρ={λi,j|λi,j∈F2n,0≤i≤2nρ-1,

0≤j≤ρ-1}

(5)

構(gòu)造1設(shè)l和ρ是正整數(shù)，l≥2且1≤ρ≤l，則奇數(shù)n=2l+1,則可以構(gòu)造大小為M×N(M=2n-1，N=2nρ)的壓縮感知測量矩陣Φ，其具體公式如式(6)所示

Φ=[φ0,φ1,…,φ2nρ-1]

(6)

其中，φi(0≤i≤2nρ-1)是測量矩陣Φ的第i+1個分量，同時也是一個周期為2n-1的二進(jìn)制采樣m序列，如式(7)所示

φi=(si,0,si,1,…,si,2n-2)T

(7)

而φi的第j+1個分量si,j(0≤j≤2n-2)也是采樣m序列的第j個變量，其計(jì)算如式(8-9)所示

si,j=(-1)fodd(i,j)

(8)

(9)

其中，α是有限域F2n中的本原元.

構(gòu)造2與奇數(shù)情況類似，令l≥2,1≤ρ≤l和n=2l，大小為M×N(M=2n-1，N=2nρ)的壓縮感知矩陣Φ為

Φ=[φ0,φ1,…,φ2nρ-1]

(10)

而其第i+1個分量如式(11)所示

φi=(si,0,si,1,…,si,2n-2)T

(11)

而φi的第j+1個分量si,j如式(12)所示

si,j=(-1)feven(i,j)

(12)

(13)

在構(gòu)造1和2中，文中分別提出了奇數(shù)和偶數(shù)變元情況的雙極性測量矩陣的構(gòu)造方法.由于測量矩陣構(gòu)造是在m采樣序列的基礎(chǔ)上構(gòu)造的，所以其硬件和軟件實(shí)現(xiàn)方式更加容易，即基于偽隨機(jī)序列的測量矩陣具有優(yōu)秀的實(shí)用性.

2.2 相關(guān)性

根據(jù)引理1可知，矩陣相關(guān)性是測量矩陣的重要衡量指標(biāo)，降低其相關(guān)性，可以提高算法的信號重構(gòu)性能.針對基于偽隨機(jī)序列的測量矩陣構(gòu)造，文中計(jì)算了測量矩陣的最大相關(guān)性，并從理論上與Gaussian隨機(jī)矩陣進(jìn)行了充分的對比和分析.

證明：由構(gòu)造1可知，當(dāng)n=2l+1或n=2l時，測量矩陣Φ均包含2nρ個列向量φi(i∈[0,2nρ-1])，而這些列向量的模長‖φi‖均為固定值，其計(jì)算公式如下所示

(14)

(15)

(1)當(dāng)n=2l+1時，

(16)

其中，

g(i,j,z)=Tr((λi,0+λj,0)z)+

(17)

(18)

(2)當(dāng)n=2l時,

(19)

2.3 相關(guān)性比較

為了進(jìn)一步衡量本文測量矩陣構(gòu)造的具體性質(zhì)，文中分析了Gaussian隨機(jī)矩陣的相關(guān)性數(shù)值，并與構(gòu)造1和2的測量矩陣進(jìn)行了細(xì)致的比較.

引理2不妨設(shè)gi和hi是Gaussian隨機(jī)矩陣Gp×q的任意兩個列向量，這兩個列向量是符合N(0,σ2)的獨(dú)立同分布的高斯隨機(jī)序列，則列向量之間相關(guān)性的概率分布滿足式(20).

(20)

定理2在同樣的條件下，對于構(gòu)造1和2中(2n-1)×2nρ的測量矩陣Φ，其相關(guān)性μ(Φ)小于同樣大小的Gaussian隨機(jī)矩陣G.

(21)

f(n)是關(guān)于n的減函數(shù)，關(guān)于ρ的增函數(shù)，這表明，當(dāng)ρ=1且n=5時，f(n)取得最大值，f(n)≤f(5)=6.77×10-4，此時，

(22)

當(dāng)n是偶數(shù)時，經(jīng)過推導(dǎo)可以得到與奇數(shù)情況下相同的結(jié)論，所以定理2得證.

3 仿真與分析

結(jié)合定理1和2的結(jié)果可知，從理論分析的角度出發(fā)，與Gaussian隨機(jī)矩陣相比，基于偽隨機(jī)序列的測量矩陣具有更低的相關(guān)性，這也意味著其重構(gòu)性能更加優(yōu)秀.為了進(jìn)一步證明和驗(yàn)證測量矩陣的信號重構(gòu)性能，通過對不同稀疏度的信號采樣和仿真，文中實(shí)現(xiàn)了Gaussian隨機(jī)矩陣和確定性測量矩陣的重構(gòu)性能比較.

在仿真的矩陣構(gòu)造階段，對于確定性測量矩陣，令ρ=2，文中構(gòu)造和實(shí)現(xiàn)偶數(shù)情況n=8和奇數(shù)情況n=7的矩陣，其測量矩陣大小分別為255×65 536和127×16 384；同樣地，文中生成了大小為255×65 536和127×16 384的獨(dú)立同分布Gaussian隨機(jī)矩陣，用于仿真比較和分析.在仿真的信號重構(gòu)階段，文中選用了正交匹配追蹤(OMP)算法，作為信號的重構(gòu)算法.此外，需要說明的是，文中隨機(jī)生成了不同稀疏度k的信號x，其維度分別為65 536×1和16 384×1，奇數(shù)情況n=7和偶數(shù)情況n=8下，測量矩陣信號重構(gòu)性能仿真的具體情況和分析如下：

3.1 奇數(shù)測量矩陣仿真

當(dāng)n=7時，信號稀疏度k設(shè)置在區(qū)間[10,40]內(nèi)，以間隔為3進(jìn)行信號重構(gòu)實(shí)驗(yàn).在每次實(shí)驗(yàn)過程中，利用Matlab軟件重復(fù)運(yùn)行1 000次，統(tǒng)計(jì)信號重構(gòu)成功的次數(shù)，從而得到測量矩陣在不同稀疏度情況下信號重構(gòu)成功的頻率，其具體數(shù)據(jù)統(tǒng)計(jì)如圖1所示.

圖1 大小為127×16 384的測量矩陣的信號重構(gòu)成功頻率

其中，橫軸表示信號的稀疏度數(shù)值，縱軸表示信號重構(gòu)成功的頻率，使用“*”標(biāo)記的曲線是確定性測量矩陣的信號重構(gòu)成功頻率的擬合結(jié)果，而“+”標(biāo)記的曲線是Gaussian隨機(jī)矩陣的信號重構(gòu)成功頻率的擬合結(jié)果.由圖1所展示的統(tǒng)計(jì)數(shù)據(jù)可知，在信號稀疏度k∈[13,37]時，基于偽隨機(jī)序列的確定性測量矩陣的信號重構(gòu)成功頻率顯著高于Gaussian隨機(jī)矩陣，而在信號稀疏度k≥40時，確定性測量矩陣和Gaussian隨機(jī)矩陣的信號重構(gòu)成功頻率趨近于0，即難以重構(gòu)原始信號，當(dāng)k<13時，確定性測量矩陣和Gaussian隨機(jī)矩陣均以接近于100%的概率重構(gòu)原始信號.總之，在n為奇數(shù)的情況下，基于偽隨機(jī)序列的確定性測量矩陣具有更加優(yōu)秀的信號重構(gòu)性能.

3.2 偶數(shù)測量矩陣仿真

與奇數(shù)情況類似，當(dāng)n=8時，文中將信號稀疏度設(shè)置在區(qū)間[30,72]內(nèi)，以間隔為3進(jìn)行信號重構(gòu)實(shí)驗(yàn).利用與奇數(shù)情況同樣的實(shí)驗(yàn)方法，得到了如圖2所示的統(tǒng)計(jì)數(shù)據(jù).

圖2 大小為255×65 536的測量矩陣的信號重構(gòu)成功頻率

由圖2可知，當(dāng)信號稀疏度k∈[36,66]時，確定性測量矩陣的信號重構(gòu)成功頻率顯著高于Gaussian隨機(jī)矩陣，而當(dāng)信號稀疏度k<36，確定性測量矩陣與Gaussian隨機(jī)矩陣均以100%的概率重構(gòu)原始的采樣信號，當(dāng)k>66時，確定性測量矩陣與Gaussian隨機(jī)矩陣的信號重構(gòu)成功頻率接近于0，即難以成功重構(gòu)原始信號.

綜上所述，在實(shí)驗(yàn)仿真過程中，與Gaussian隨機(jī)矩陣相比，基于偽隨機(jī)序列的確定性測量矩陣具有更加優(yōu)秀的信號重構(gòu)性能.

4 結(jié)論

基于偽隨機(jī)序列，本文分別提出了奇數(shù)和偶數(shù)情況下確定的雙極性測量矩陣.通過理論推導(dǎo)和實(shí)驗(yàn)仿真，在同樣條件下，與Gaussian隨機(jī)矩陣相比，基于偽隨機(jī)序列的確定性測量矩陣具有較低的相關(guān)性和更加優(yōu)秀的信號重構(gòu)性能.此外，由于具有更加簡單方便的電路實(shí)現(xiàn)方式，所以確定性測量矩陣優(yōu)于Gaussian隨機(jī)矩陣.然而，文中并未考慮基于偽隨機(jī)序列的確定性測量矩陣的實(shí)際應(yīng)用場景，這也將是我們未來將要考慮的重要問題.