張京超 付 寧楊 柳

(哈爾濱工業(yè)大學(xué)自動(dòng)化測(cè)試與控制系 哈爾濱 150080)

1-Bit壓縮感知盲重構(gòu)算法

張京超 付 寧*楊 柳

(哈爾濱工業(yè)大學(xué)自動(dòng)化測(cè)試與控制系 哈爾濱 150080)

1-Bit壓縮感知(CS)是壓縮感知理論的一個(gè)重要分支。該領(lǐng)域中二進(jìn)制迭代硬閾值(BIHT)算法重構(gòu)精度高且一致性好，是一種有效的重構(gòu)算法。該文針對(duì)BIHT算法重構(gòu)過(guò)程需要信號(hào)稀疏度為先驗(yàn)信息的問(wèn)題，提出一種稀疏度自適應(yīng)二進(jìn)制迭代硬閾值算法，簡(jiǎn)稱為SABIHT算法。該算法修正了BIHT算法，首先通過(guò)自適應(yīng)過(guò)程自動(dòng)調(diào)節(jié)硬閾值參數(shù)，然后利用測(cè)試條件估計(jì)信號(hào)的稀疏度，最終實(shí)現(xiàn)不需要確切信號(hào)稀疏度的1-Bit壓縮感知盲重構(gòu)。理論分析和仿真結(jié)果表明，該算法較好地實(shí)現(xiàn)了未知信號(hào)稀疏度的精確重建，并且與BIHT算法相比重構(gòu)精度及算法復(fù)雜度均相當(dāng)。

壓縮感知；1-Bit壓縮感知；盲重構(gòu)；二進(jìn)制迭代硬閾值

1 引言

壓縮感知理論[1-3]是近年發(fā)展起來(lái)的新的信號(hào)獲取和信號(hào)處理理論。該理論表明，對(duì)于稀疏或可壓縮信號(hào)，通過(guò)遠(yuǎn)低于奈奎斯特采樣速率采樣，可精確地實(shí)現(xiàn)原始信號(hào)恢復(fù)。在數(shù)字信號(hào)處理和數(shù)字通信系統(tǒng)中，信號(hào)量化是必不可少的一部分。隨著信息技術(shù)不斷發(fā)展，信號(hào)頻帶寬度不斷增大，為了滿足人們的信息需求，需要提高采樣速率和量化精度，這將對(duì)采樣系統(tǒng)中模擬數(shù)字轉(zhuǎn)換器件(Analog to Dgital Converter, ADC)、存儲(chǔ)器件的選擇及數(shù)據(jù)傳輸提出了比較嚴(yán)峻的挑戰(zhàn)。壓縮感知理論雖然實(shí)現(xiàn)了低速采樣，在一定程度上緩解了ADC壓力，但是為了提高重構(gòu)精度，仍需要增加信號(hào)的觀測(cè)數(shù)量和提高觀測(cè)值的量化精度[4,5]。無(wú)論是提高采樣速率還是量化精度，都會(huì)造成數(shù)據(jù)量增大，量化仍然是壓縮感知中數(shù)據(jù)壓縮的重要一步。近年來(lái)，量化壓縮感知[4-7]受到廣泛關(guān)注，人們從降低采樣速率的角度轉(zhuǎn)換為降低量化精度的角度，試圖通過(guò)低精度量化緩解硬件壓力。2008年，文獻(xiàn)[8]提出對(duì)測(cè)量值進(jìn)行極限量化，即1-Bit量化，也能實(shí)現(xiàn)稀疏信號(hào)重構(gòu)。1-Bit壓縮感知是將壓縮觀測(cè)值進(jìn)行極限量化處理，通過(guò)保留觀測(cè)值的符號(hào)信息，緩解硬件壓力，提高存儲(chǔ)效率，并克服測(cè)量中的動(dòng)態(tài)范圍問(wèn)題。1-Bit壓縮感知的重構(gòu)算法可分為兩大類：凸算法與非凸貪心算法。文獻(xiàn)[8]在固定點(diǎn)連續(xù)(Fixed Point Continuation, FPC)算法的基礎(chǔ)上，增加梯度投影和球面約束思想，提出BFPC(Binary FPC)算法，該算法為凸正則化算法。匹配符號(hào)追蹤算法(Matching Sign Puisuit, MSP)[9]是在CoSaMP算法的基礎(chǔ)上提出的一種貪心算法。文獻(xiàn)[10]介紹了類似于非凸優(yōu)化中的信賴域算法––限制步長(zhǎng)收斂算法(Restricted Step Shrinkage, RSS)，該算法具有較好的收斂性，計(jì)算速度快，重構(gòu)信噪比較高。文獻(xiàn)[11]提出二進(jìn)制迭代硬閾值算法(Binary Iterative Hard Thresholding, BIHT)，文獻(xiàn)[5]提出的1-Bit線性規(guī)劃算法(One-Bit linear programming)，文獻(xiàn)[12]提出一種快速精確的兩級(jí) (Fast and Accurate Two-Stage, FATS)信號(hào)重構(gòu)算法，在上述算法中最突出的算法是BIHT算法，該算法較其它重構(gòu)算法的重夠效果更好，表現(xiàn)為較高的重構(gòu)信噪比和一致性，且計(jì)算過(guò)程簡(jiǎn)單，復(fù)雜度低[13]。BIHT算法雖然具有較完美的重構(gòu)效果，但是該算法要求信號(hào)的稀疏度作為重構(gòu)的先驗(yàn)條件。在實(shí)際應(yīng)用中，獲取信號(hào)稀疏度是相當(dāng)困難的。針對(duì)BIHT算法要求信號(hào)的稀疏度已知的問(wèn)題，該文在其基礎(chǔ)上進(jìn)行改進(jìn)，提出稀疏度自適應(yīng)二進(jìn)制迭代硬閾值(Sparsity Adaptive Binary Iterative Hard Thresholding, SABIHT)算法。該算法通過(guò)增加稀疏度自適應(yīng)過(guò)程，很好地克服了BIHT算法對(duì)信號(hào)稀疏度依賴性的問(wèn)題，實(shí)現(xiàn)了1-Bit壓縮感知盲重構(gòu)，在不影響重構(gòu)精度的前提下，有效克服實(shí)際中信號(hào)稀疏度未知的問(wèn)題。

本文在第2節(jié)介紹了壓縮感知模型與1-Bit壓縮感知模型；第3節(jié)首先分析BIHT算法，然后描述1-Bit壓縮感知盲重構(gòu)算法的具體實(shí)施方法；第4節(jié)給出不同情況下SABIHT算法與BIHT算法的性能比較試驗(yàn)，通過(guò)分析仿真結(jié)果說(shuō)明改進(jìn)算法的有效性；第5節(jié)對(duì)該方法進(jìn)行總結(jié)。

2 壓縮感知背景

2.1 壓縮感知模型

信號(hào)的稀疏性是壓縮感知理論應(yīng)用的前提。假設(shè)實(shí)值離散時(shí)間信號(hào)x∈是N×1維列向量?？臻g的任何信號(hào)都可以用N×N維的規(guī)范正交基向量{ψi}的線性組合表示。則x在一組正交基下進(jìn)行展開(kāi)，即

其中系數(shù)向量為α=[α,α,???,α]T。如果信號(hào)x在

12N正交基Ψ下的系數(shù)向量α中最多含有K個(gè)非零元素，則稱向量α為信號(hào)的x稀疏表示，即a=Ψ-1x=ΨTx ，信號(hào)x則稱為稀疏信號(hào)。

其中Φ為M×N(M＜＜N)維觀測(cè)矩陣。利用M維觀測(cè)值y恢復(fù)信號(hào)x的過(guò)程稱為信號(hào)重構(gòu)，重構(gòu)模型可寫(xiě)為

求解式(4)的本質(zhì)是0l范數(shù)最小化求解問(wèn)題，是NP難問(wèn)題，無(wú)法直接求解。當(dāng)前這類問(wèn)題的間接求解方法較多，其中貪婪迭代算法因算法結(jié)構(gòu)簡(jiǎn)單、運(yùn)算量小而頗受關(guān)注，主要有匹配追蹤(Matching Pursuit, MP)[14]、正交匹配追蹤(Orthogonal Matching Pursuit, OMP)[15]及子空間追蹤(Subspace Pursuit, SP)[16]等。

2.2 1-Bit壓縮感知模型

在現(xiàn)實(shí)環(huán)境中，觀測(cè)值y必須經(jīng)過(guò)量化處理后，才能進(jìn)行數(shù)字處理，進(jìn)而恢復(fù)信號(hào)。量化模型[17]可寫(xiě)為

其中BQ表示B-Bit量化，即將觀測(cè)值量化為B位二進(jìn)制數(shù)。當(dāng)B取值為1時(shí)，表示1-Bit量化。1-Bit量化是對(duì)觀測(cè)值進(jìn)行量化處理的一種極限情況，即僅保留觀測(cè)值的符號(hào)信息[8]。測(cè)量值的1-Bit量化具有的優(yōu)勢(shì)為[10]：1-Bit量化通過(guò)比較器實(shí)現(xiàn)，比較器代替ADC可以極大地提高運(yùn)行速率，簡(jiǎn)化硬件結(jié)構(gòu)；避免受動(dòng)態(tài)量程的影響，當(dāng)模擬輸入端受適當(dāng)?shù)挠绊憰r(shí)，測(cè)量值的符號(hào)依舊有效；在輸入信噪比水平較低時(shí)，總比特位數(shù)固定時(shí)1-Bit CS優(yōu)于多Bit CS。

通常情況下，量化過(guò)程電壓比較器的比較電壓取為零[8]，則1-Bit壓縮感知量化模型可寫(xiě)為

其中，sign(?)為符號(hào)函數(shù)。觀測(cè)值向量y可構(gòu)成M×M的對(duì)角矩陣Y=diag(y)。根據(jù)符號(hào)一致性原理，可得YΦx≥0。1-Bit壓縮感知僅保留觀測(cè)值的符號(hào)，信號(hào)的幅度信息丟失，重構(gòu)模型用l1范數(shù)作為衡量信號(hào)稀疏性標(biāo)準(zhǔn)。為了確保得到非零解，并克服幅度不確定性問(wèn)題，在單位l2球面上重構(gòu)信號(hào)。1-Bit壓縮感知重構(gòu)模型為

1-Bit壓縮感知理論自提出以來(lái)，受到了學(xué)者們的廣泛關(guān)注并提出許多有效算法。BIHT算法的重構(gòu)效果優(yōu)于MSP和RSS算法，主要表現(xiàn)為重構(gòu)過(guò)程簡(jiǎn)單，較高的重構(gòu)信噪比和一致性，詳見(jiàn)文獻(xiàn)[11]。但是BIHT算法要求信號(hào)的稀疏度K作為先驗(yàn)信息，然而在實(shí)際應(yīng)用中信號(hào)的稀疏度K通常是未知的，這在相當(dāng)程度上限制了上述算法的應(yīng)用。

3 1-Bit壓縮感知盲重構(gòu)

3.1 傳統(tǒng)的BIHT算法

BIHT算法最初是在迭代硬閾值(Iterative Hard Thresholding，IHT)算法[18]的基礎(chǔ)上改進(jìn)的。IHT算法是處理壓縮感知問(wèn)題的一種常用算法，該算法是求解滿足約束條件優(yōu)化問(wèn)題，文獻(xiàn)[18～20]推導(dǎo)出了IHT算法理論，IHT算法十分簡(jiǎn)潔，采用迭代式(8)：

其中xt為第t次迭代值，ηK(β)是一個(gè)非線性算子，它將矢量β中幅度最大的前K個(gè)元素以外的所有元素設(shè)置為零。

IHT算法的迭代式(8)可分解為兩步，第1步在第t次迭代中令矢量，通過(guò)梯度下降法減小目標(biāo)的平方差；第2步將1t+β映射到0l范數(shù)球面上，得到稀疏解。

BIHT算法結(jié)合1-Bit壓縮感知特點(diǎn)，用最小一致目標(biāo)代替IHT算法的第1步，即在第l次迭代中令，并令殘差r=yt-sign(Φxt)；第2步將βt+1映射到l2范數(shù)單位超球面上，并保留前K個(gè)最大值元素，其余元素置為零。BIHT算法的具體重構(gòu)原理框圖如圖1所示。

如圖1所示，重構(gòu)時(shí)首先利用觀測(cè)值進(jìn)行初始估計(jì)，然后進(jìn)行硬閾值投影，即將估計(jì)值以參數(shù)K為硬閾值，投影到單位超球面上，并保留前K個(gè)最大值元素，其余元素置為零，然后更新信號(hào)，更新殘差后繼續(xù)迭代。

圖1 BIHT算法重構(gòu)原理圖

3.2 BIHT算法稀疏度依賴性問(wèn)題分析

由于BIHT算法采用信號(hào)稀疏度K作為迭代過(guò)程中的硬閾值條件，信號(hào)稀疏度K成為該算法有效應(yīng)用的一個(gè)必要前提。為了說(shuō)明信號(hào)稀疏度K值不準(zhǔn)確對(duì)BIHT重構(gòu)算法的影響，進(jìn)行如下仿真實(shí)驗(yàn)。仿真信號(hào)為高斯隨機(jī)稀疏信號(hào)，長(zhǎng)度N=256，信號(hào)稀疏度K=20，觀測(cè)值個(gè)數(shù)M=300, 400, 500, 600，700，感知矩陣Φ服從高斯分布[21]。實(shí)驗(yàn)中利用BIHT算法進(jìn)行重構(gòu)，重構(gòu)算法采用估計(jì)稀疏度，依次取值為10, 15, 20, 25, 30，實(shí)驗(yàn)運(yùn)行100次。仿真結(jié)果如圖2所示。

通過(guò)觀察圖2結(jié)果，說(shuō)明稀疏度K值不準(zhǔn)確對(duì)BIHT算法重構(gòu)效果的影響明顯。稀疏度估計(jì)值取為20時(shí)，BIHT算法重構(gòu)信噪比最高，稀疏度估計(jì)值大于或小于真實(shí)值K=20，都會(huì)不同程度的影響B(tài)IHT算法的重構(gòu)效果，其中K=10時(shí)，重構(gòu)效果最差。由此可以得出結(jié)論，信號(hào)稀疏度K不準(zhǔn)確，將造成BIHT算法的重構(gòu)效果明顯變差，即BIHT重構(gòu)算法存在信號(hào)稀疏度依賴性問(wèn)題。

3.3 稀疏度自適應(yīng)二進(jìn)制迭代硬閾值(SABIHT)算法

由于BIHT重構(gòu)算法將信號(hào)稀疏度K作為重構(gòu)的硬閾值條件，從而保證重建的精確性。為了克服BIHT算法的稀疏度依賴性問(wèn)題，該文在BIHT算法的基礎(chǔ)上增加稀疏度自適應(yīng)的過(guò)程，提出SABIHT重構(gòu)算法。圖3給出了該算法的原理框圖。

圖3 SABIHT算法重構(gòu)原理圖

如圖3所示，SABIHT的重構(gòu)思想是：在BIHT算法的基礎(chǔ)上引入稀疏度自適應(yīng)[21]方法，自適應(yīng)地估計(jì)閾值參數(shù)，利用估計(jì)硬閾值更新信號(hào)。具體實(shí)施方法為：選擇固定的步長(zhǎng)s作為初始硬閾值參數(shù)，通過(guò)測(cè)試條件判斷估計(jì)硬閾值是否滿足要求，并控制硬閾值參數(shù)以s為步長(zhǎng)逐漸逼近信號(hào)稀疏度K，最終利用估計(jì)的硬閾值參數(shù)按照BIHT原理恢復(fù)信號(hào)。該算法的測(cè)試條件包括相鄰兩階段重建信號(hào)的能量差和殘差能量的大小。SABIHT重構(gòu)算法通過(guò)上述過(guò)程實(shí)現(xiàn)自適應(yīng)的估計(jì)信號(hào)稀疏度，克服了BIHT算法直接將稀疏度K作為硬閾值，過(guò)度依賴稀疏度的問(wèn)題。算法的具體實(shí)施步驟如表1所示。

SABIHT算法，首先設(shè)定初始步長(zhǎng)s＜K作為迭代的初始硬閾值參數(shù)，然后判斷相鄰兩次迭代信號(hào)的能量差和殘差大小，確保迭代向收斂方向發(fā)展。當(dāng)相鄰兩次迭代信號(hào)的能量差小于參數(shù)ε時(shí)，此時(shí)的硬閾值大小(估計(jì)稀疏度L)最接近信號(hào)稀疏度，再利用L恢復(fù)原信號(hào)。步驟(1)到步驟(3)，實(shí)現(xiàn)了稀疏度的粗估計(jì)和迭代變量的初始化。步驟(4)到步驟(8)，為SABIHT重構(gòu)算法在BIHT框架下的稀疏自適應(yīng)迭代部分。

SABIHT算法是在BIHT框架下融合稀疏自適應(yīng)策略而得到，該策略將對(duì)算法的收斂速度產(chǎn)生影響但并不影響算法的收斂性。而B(niǎo)IHT是迭代硬閾值(IHT)的改編算法，研究人員從數(shù)值仿真實(shí)驗(yàn)角度證明了其收斂性[11]，而IHT算法則有完善的理論分析證明其至少收斂到一個(gè)局部點(diǎn)[22]。基于上述成果，本文得出SABIHT算法至少能收斂到一個(gè)局部點(diǎn)。算法收斂時(shí)的稀疏度為與真實(shí)的稀疏度K近似相等，從而在未知稀疏度的前提下，實(shí)現(xiàn)了重構(gòu)。SABIHT重構(gòu)算法每次迭代的運(yùn)算量主要集中在表1中的步驟(2)和步驟(3)中，復(fù)雜度為()OMN，這與BIHT算法是一致的。SABIHT重構(gòu)算法的計(jì)算復(fù)雜度與迭代次數(shù)有密切關(guān)系。當(dāng)步長(zhǎng)固定時(shí)，步長(zhǎng)的選擇直接影響到迭代次數(shù)，步長(zhǎng)s越小，重建迭代次數(shù)越多，因此在重建過(guò)程中應(yīng)選取適當(dāng)?shù)牟介L(zhǎng)，具體分析見(jiàn)4.3節(jié)。

4 實(shí)驗(yàn)結(jié)果及分析

為了保證該文重建算法性能的有效性和客觀性，該文通過(guò)MATLAB處理平臺(tái)對(duì)提出的SABIHT算法和BIHT算法進(jìn)行了實(shí)驗(yàn)仿真。實(shí)驗(yàn)中BIHT算法采用的是Jacques L個(gè)人網(wǎng)站的程序包(http://perso.uclouvain.be/laurent.jacques)。第4.1節(jié)和4.2節(jié)通過(guò)比較無(wú)噪聲情況兩種重構(gòu)算法的重構(gòu)信噪比和噪聲情況下的重構(gòu)信噪比，驗(yàn)證了本文算法的有效性。第4.3節(jié)給出了步長(zhǎng)選取對(duì)本文算法的影響分析實(shí)驗(yàn)。

表1 SABIHT算法流程

4.1 無(wú)噪聲情況下SABIHT算法與BIHT算法重建性能比較

4.1.1 高斯信號(hào)的重構(gòu)信噪比比較 在該實(shí)驗(yàn)中首先采用高斯稀疏信號(hào)[21]，測(cè)量矩陣為高斯矩陣。假設(shè)信號(hào)長(zhǎng)度N=256，測(cè)量值個(gè)數(shù)M從50增加到600，以50為步進(jìn)變化，初始步長(zhǎng)s=10，最大迭代次數(shù)nIter=1000，對(duì)于不同的觀測(cè)值M分別做100次實(shí)驗(yàn)，分別比較改進(jìn)算法與BIHT算法在信號(hào)稀疏度K=20, 40, 60平均重構(gòu)信噪比(重構(gòu)信噪比之和除以實(shí)驗(yàn)次數(shù))。仿真中BIHT算法給定信號(hào)稀疏度，SABIHT重構(gòu)算法未給定信號(hào)稀疏度，比較結(jié)果如圖4所示。

輸入信號(hào)x與重構(gòu)信號(hào)x?之間的信噪比[1]計(jì)算公式為

由圖4可以看出在相同實(shí)驗(yàn)條件下，對(duì)稀疏度不同的高斯稀疏信號(hào)進(jìn)行重構(gòu)，SABIHT算法在信號(hào)稀疏度未知的情況下與BIHT算法已知信號(hào)稀疏度的情況下的重構(gòu)效果基本一致，均隨著觀測(cè)值個(gè)數(shù)增加，分別由-2 dB增加到22 dB, 15 dB和12 dB。SABIHT算法放寬了實(shí)驗(yàn)已知條件，仍可以達(dá)到較好的重構(gòu)效果，克服了實(shí)際應(yīng)用中信號(hào)稀疏度難以獲得的問(wèn)題。

4.1.2 伯努利信號(hào)重構(gòu)信噪比比較 為了說(shuō)明提出算法的有效性和正確性，該實(shí)驗(yàn)中采用伯努利稀疏信號(hào)[21]作為原始信號(hào)，測(cè)量矩陣為高斯矩陣。假設(shè)信號(hào)長(zhǎng)度N=256，測(cè)量值個(gè)數(shù)M從50增加到600，對(duì)于不同的觀測(cè)值M分別做100次實(shí)驗(yàn)，分別比較SABIHT算法與BIHT算法在信號(hào)稀疏度K=20, 40, 60平均重構(gòu)信噪比(重構(gòu)信噪比之和除以實(shí)驗(yàn)次數(shù))。重構(gòu)結(jié)果如圖5所示。

圖4和圖5的實(shí)驗(yàn)結(jié)果說(shuō)明1-Bit壓縮感知盲重構(gòu)算法在信號(hào)稀疏度未知的情況下，對(duì)于高斯稀疏信號(hào)和伯努利稀疏信號(hào)，均可實(shí)現(xiàn)較高的重構(gòu)信噪比——與BIHT算法重構(gòu)信噪比基本一致。

4.2 噪聲情況下SABIHT與BIHT算法重建性能比較

1-Bit壓縮感知在量化過(guò)程中對(duì)觀測(cè)值進(jìn)行非線性量化，得到的測(cè)量值向量為符號(hào)向量。在實(shí)際測(cè)量中，由于噪聲的影響，會(huì)使測(cè)量值符號(hào)發(fā)生變化。當(dāng)測(cè)量值符號(hào)變化后，準(zhǔn)確恢復(fù)原信號(hào)變得更加困難。該部分著重分析，當(dāng)信號(hào)受噪聲影響時(shí)，提出SABIHT算法的重構(gòu)效果。

4.2.1 含噪聲時(shí)高斯信號(hào)的重構(gòu)信噪比比較 該實(shí)驗(yàn)中采用高斯稀疏信號(hào)作為原始信號(hào)，測(cè)量矩陣為高斯矩陣。假設(shè)信號(hào)長(zhǎng)度N=256，測(cè)量值個(gè)數(shù)M=300, 350, 400，受噪聲影響的符號(hào)位個(gè)數(shù)p=1(觀測(cè)值中存在某一觀測(cè)值符號(hào)因噪聲發(fā)生符號(hào)翻轉(zhuǎn))[22,23]，信號(hào)稀疏度K=10, 20, 30, 40, 50, 60，步長(zhǎng)s=10，對(duì)于不同的信號(hào)稀疏度K分別做100次實(shí)驗(yàn)，分別比較本文算法與BIHT算法在噪聲情況下的重構(gòu)信噪比。

圖6表明，在噪聲情況下SABIHT算法和BIHT算法對(duì)高斯信號(hào)的重構(gòu)信噪比，均隨著觀測(cè)值個(gè)數(shù)增加而提高。信號(hào)稀疏度越大，兩種算法的重構(gòu)精度都降低，但是提出算法的重構(gòu)效果略高于BIHT算法。

4.2.2 含噪聲時(shí)對(duì)伯努利信號(hào)重構(gòu)信噪比比較 該實(shí)驗(yàn)中實(shí)驗(yàn)信號(hào)采用稀疏伯努利信號(hào)，實(shí)驗(yàn)條件與4.2.1節(jié)的條件相同，實(shí)驗(yàn)結(jié)果如圖7所示。

4.2.1 節(jié)和4.2.2節(jié)中SABIHT算法與BIHT算法針對(duì)不同信號(hào)的重構(gòu)信噪比結(jié)果圖說(shuō)明，在噪聲情況下不同信號(hào)稀疏水平時(shí)，本文提出算法與BIHT算法的重構(gòu)信噪比基本一致，均隨著觀測(cè)值個(gè)數(shù)增加。1-Bit壓縮感知盲重構(gòu)算法在噪聲情況下，仍可以實(shí)現(xiàn)未知信號(hào)稀疏度條件下的精確重構(gòu)。

4.3 步長(zhǎng)s對(duì)SABIHT算法影響分析實(shí)驗(yàn)

本節(jié)為考察SABIHT算法重構(gòu)過(guò)程中，步長(zhǎng)選取對(duì)重構(gòu)信噪比和算法復(fù)雜度的影響，進(jìn)行如下仿真實(shí)驗(yàn)。實(shí)驗(yàn)采用伯努利稀疏信號(hào)，信號(hào)維數(shù)N=256，觀測(cè)值個(gè)數(shù)M=300，信號(hào)稀疏度K=10, 20, 30, 40, 50, 60，實(shí)驗(yàn)中SABIHT算法的步長(zhǎng)分別取s=1, 5, 10，實(shí)驗(yàn)運(yùn)行100次，分別比較SABIHT算法與BIHT算法的重構(gòu)信噪比和所需迭代次數(shù)。比較結(jié)果如圖8，圖8(a)為重構(gòu)信噪比的比較，圖8(b)為重構(gòu)所需迭代次數(shù)的比較圖。

圖4 無(wú)噪聲時(shí)SABIHT算法與BIHT算法對(duì)高斯信號(hào)重構(gòu)信噪比

圖5 無(wú)噪聲時(shí)SABIHT算法與BIHT算法對(duì)伯努利信號(hào)重構(gòu)信噪比

圖6 含噪聲時(shí)SABIHT算法與BIHT算法對(duì)高斯信號(hào)重構(gòu)信噪比

圖7 含噪聲時(shí)SABIHT算法與BIHT算法對(duì)伯努利信號(hào)重構(gòu)信噪比

圖8 SABIHT算法不同步長(zhǎng)時(shí)的重構(gòu)信噪比和迭代次數(shù)比較

從圖8(a)可以看出，隨著信號(hào)稀疏度遞增，SABIHT算法步長(zhǎng)s=1的重構(gòu)信噪比與步長(zhǎng)s=5的重構(gòu)信噪比相當(dāng)，步長(zhǎng)s=10的重構(gòu)效果更接近BIHT算法。從圖8(b)可以看出，步長(zhǎng)的選取影響SABIHT算法重構(gòu)所需的迭代次數(shù)。當(dāng)s=1時(shí)，迭代次數(shù)明顯高于其它步長(zhǎng)時(shí)的迭代次數(shù)。當(dāng)s=10時(shí)，SABIHT算法的迭代次數(shù)甚至小于信號(hào)稀疏度已知時(shí)BIHT算法的迭代次數(shù)。在SABIHT算法中，K首先被設(shè)定為一個(gè)初值，然后按照一定的迭代步長(zhǎng)不斷累加。迭代過(guò)程中，隨著K取值的增大，硬閾值操作保留的元素個(gè)數(shù)逐漸增大，這和BIHT算法每次迭代硬閾值操作保留的元素個(gè)數(shù)保持不變(即信號(hào)的真實(shí)稀疏度)不同。在一定的條件下，SABIHT算法這種策略有助于減小原子的誤匹配，當(dāng)算法的估計(jì)稀疏度達(dá)到真實(shí)稀疏度時(shí)，僅需少量的迭代次數(shù)即可實(shí)現(xiàn)信號(hào)恢復(fù)。算法總體迭代次數(shù)小于BIHT算法的迭代次數(shù)。而當(dāng)步長(zhǎng)參數(shù)較小時(shí)，比如1s=，當(dāng)算法的估計(jì)稀疏度達(dá)到真實(shí)值時(shí)，算法的迭代次數(shù)已經(jīng)達(dá)到較大的值，甚至大于BIHT算法的迭代次數(shù)，因而SABIHT算法在此條件下的迭代次數(shù)通常大于BIHT算法的迭代次數(shù)。仿真實(shí)驗(yàn)證明步長(zhǎng)越大，所需迭代次數(shù)越少，計(jì)算復(fù)雜度越小，同時(shí)步長(zhǎng)的增大并沒(méi)有使重構(gòu)精度受到影響。究其原因是因?yàn)楫?dāng)步長(zhǎng)增大時(shí)，重構(gòu)過(guò)程中相鄰信號(hào)的能量差與殘差變化更明顯，從而確保逼近過(guò)程更準(zhǔn)確。

因?yàn)樾盘?hào)的稀疏度是未知的，增大步長(zhǎng)會(huì)降低算法的迭代次數(shù)，從而降低算法的復(fù)雜度。但步長(zhǎng)較大，易使迭代過(guò)程中估計(jì)稀疏度大于信號(hào)的真實(shí)稀疏度，從而帶來(lái)較大的估計(jì)誤差，這從圖2所示的實(shí)驗(yàn)結(jié)果可以看出。通常步長(zhǎng)設(shè)置為1，然后通過(guò)迭代不斷逼近信號(hào)的真實(shí)稀疏度。但此時(shí)算法復(fù)雜度較大。步長(zhǎng)參數(shù)對(duì)算法的復(fù)雜度有較大的影響。如何選取合適的步長(zhǎng)參數(shù)，是算法后續(xù)研究的一個(gè)問(wèn)題。

5 結(jié)束語(yǔ)

本文針對(duì)1-Bit壓縮感知重構(gòu)算法中，BIHT這一經(jīng)典算法重構(gòu)過(guò)程中要求信號(hào)的稀疏度已知的問(wèn)題，提出了一種1-Bit壓縮感知盲重構(gòu)算法——稀疏度自適應(yīng)二進(jìn)制迭代硬閾值算法，即SABIHT算法。所提出SABIHT算法在重構(gòu)中可以不需要確切的稀疏度信息，自適應(yīng)地估計(jì)信號(hào)稀疏度，利用估計(jì)稀疏度實(shí)現(xiàn)信號(hào)恢復(fù)。實(shí)驗(yàn)結(jié)果表明，在未知稀疏度的前提下，無(wú)論在無(wú)噪聲情況與有噪聲情況下，該算法的性能與已知確切稀疏度的BIHT算法相當(dāng)，可以較好地實(shí)現(xiàn)盲重構(gòu)，本文算法重構(gòu)效果穩(wěn)定，不易受步長(zhǎng)影響。本文所提出的1-Bit壓縮感知盲重構(gòu)方法為實(shí)際1-Bit壓縮感知理論的應(yīng)用提供了一種有效途徑。

[1] Donoho D L. Compressed sensing[J]. IEEE Transactions on Information Theory, 2006, 52(4): 1289-1306.

[2] 甘偉, 許錄平, 蘇哲. 一種壓縮感知重構(gòu)算法[J]. 電子與信息學(xué)報(bào), 2010, 32(9): 2151-2155.

Gan Wei, Xu Lu-ping and Su Zhe. A recovery-algorithm for compressed sensing[J]. Journal of Electronics & Information Technology, 2010, 32(9): 2151-2155.

[3] 賈瓊瓊, 吳仁彪. 基于壓縮感知的空時(shí)自適應(yīng)動(dòng)目標(biāo)參數(shù)估計(jì)[J]. 電子與信息學(xué)報(bào), 2013, 35(11): 2714-2720.

Jia Qiong-qiong and Wu Ren-biao. Space time adaptive paratmeter estimation of moving taeget based on compressed sensing[J]. Journal of Electronics & Information Technology, 2013, 35(11): 2714-2720.

[4] Wang H T, Ghosh S, and Leon-Salas W D. Compressive sensing recovery from non-ideally quantized measurements[C]. Proceedings of the 2013 IEEE International Symposium on Circuits and Systems(ISCAS), Beijing, China, 2013: 1368-1371.

[5] Plan Y and Vershynin R. One-bit compressed sensing by linear programming[J]. Communication on Pure and Applied Mathematics, 2013, 66(8): 1275-1297.

[6] Zhou Tian-yi and Tao Da-cheng. K-Bit hamming compressedsensing[C]. Proceedings of the IEEE International Symposium on Information Theory Proceedings, Istanbul, Turkey, 2013: 679-683.

[7] Laska J N, Boufounos P T, Davenport M. A, et al.. Democracy in action: Quantization, saturation compressive sensing[J]. Applied and Computational Harmonic Analysis, 2011, 31(3): 429-443.

[8] Boufounos P and Baraniuk R. 1-Bit compressive sensing[J]. Sciences and Systems, 2008: 16-21.

[9] Boufounos P. Greedy sparse signal reconstruction from sign measurements[C]. Prceedings of the Asilomar Conference on Signals Systems and Computers, Asilomar, California, 2009: 1305-1309.

[10] Laska J, Wen Z W, Yin W, et al.. Trust, but verify: fast and accurate signal recovery from 1-bit compressive measurements[J]. IEEE Transactions on Signal Processing, 2011, 59(11): 5289-5301.

[11] Jacquesy L, Laska J N, Boufounos P T, et al.. Robust 1-Bit compressive sensing via binary stable embeddings of sparse vectors[J]. IEEE Transactions on Information Theory, 2013, 59(3): 2082-2102.

[12] Sun B, Chen Q, Xu X, et al.. A fast and accurate two-stage algorithm for 1-bit compressive sensing[J]. IEICE Transactions on Information and Systems, 2013, 96(1): 120-123.

[13] 孫彪. 基于壓縮感知的信號(hào)頻譜測(cè)量方法研究[D]. [博士論文],華中科技大學(xué), 2013.

Sun Biao. Research of signal spectrum measurement based on compressing senging[D]. [Ph.D. dissertation], Huazhong University of Science & Technology, 2013.

[14] Mallat S and Zhang Z. Matching pursuits with time-frequency dictionaries[J]. IEEE Transactions on Signal Processing, 1993, 41(12): 3397-3415.

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

[16] Dai W and Milenkovic O. Subspace pursuit for compressive sensing signal reconstruction[C]. Proceedings of the International Symposium on Turbo Codes and Related Topics, Turbocoding, Lausanne, Switzerland, 2008: 402-407.

[17] Laska J and Baraniuk R G. Regime change: bit-depth versus measurement-rate in compressive sensing[J]. IEEE Transactions on Signal Processing, 2012, 60(3): 3496-3505.

[18] Blumensath T and Davies M. Iterative hard thresholding for compressed sensing[J]. Applied Computational Harmonics Analysis, 2009, 27(3): 265-274.

[19] Jacques L, Degraux K, and Vleeschouwer C. Quantized iterative hard thresholding: bridging 1-bit and high-resolution quantized compressed sensing[C]. Proceedings of the 10th Sampling Theory and Application, Jacobs University, Bremen, Germany, 2013: 105-108.

[20] 段世芳, 馬社祥. 變步長(zhǎng)稀疏自適應(yīng)的迭代硬閾值圖像重構(gòu)[J]. 計(jì)算機(jī)工程與科學(xué), 2013, 35(8): 120-124.

Duan Shi-fang and Ma She-xiang. Variable step size sparsity adaptive iterative hard thresholding image reconstruction[J]. Computer Engineer & Science, 2013, 35(8): 120-124.

[21] Do T T, Lu Gan, and Nguyen N. Sparsity adaptive matching pursuit algorithm for practical compressed sensing[C]. Proceedings of the Asilomar Conference on Signals, Systems, and Computers, California, USA, 2008: 581-587.

[22] Blumensath T and Davies M. Iterative thresholding for sparse approximations[J]. Applied Computational Harmonics Analysis, 2008, 14(5): 629-654.

[23] Yan M, Yang Y, and Osher S. Robust 1-bit compressive sensing using adaptive outlier pursuit[J]. IEEE Transactions on Signal Processing, 2012, 60(3): 3868-3875.

張京超： 男，1984年生，博士生，研究方向?yàn)閴嚎s采樣、稀疏信號(hào)處理等.

付 寧： 男，1979年生，博士，副教授，碩士生導(dǎo)師，研究方向?yàn)閴嚎s采樣、稀疏信號(hào)處理、自動(dòng)測(cè)試技術(shù)、盲信號(hào)處理等.

楊 柳： 女，1989年生，碩士生，研究方向?yàn)閴嚎s采樣、1-Bit壓縮感知等.

A Blind 1-Bit Compressive Sensing Reconstruction Method

Zhang Jing-chao Fu Ning Yang Liu
(Department of Automatic Test and Control, Harbin Institute of Technology, Harbin 150080, China)

1-Bit Compressive Sensing (CS) is an important branch of standard CS. The existing 1-Bit CS algorithm-Binary Iterative Hard Thresholding (BIHT) can perfectly recovery signals with high precision and consistency, which requires exact sparsity level in the recovery phase. Considering this problem, a new Sparsity Adaptive Binary Iterative Hard Thresholding (SABIHT) algorithm without prior information of the sparsity is proposed by modifying the BIHT algorithm. By using the adaptive process of automatically adjusting the hard threshold parameters and test conditions to estimate the sparsity, the proposed algorithm realizes accurate reconstruction and estimates the true supporting set of approximated signal. The analytical theory and simulation results show that the SABIHT algorithm recovers effectively the signals without prior information of signal sparsity and the reconstruction performance is similar to the BIHT algorithm.

Compressive Sensing (CS); 1-Bit compressive sensing; Blind Reconstruction; Binary Iterative Hard Thresholding (BIHT)

TN911.72

A

1009-5896(2015)03-0567-07

10.11999/JEIT140419

2014-03-31收到，2014-10-08改回

國(guó)家自然科學(xué)基金(61102148)和黑龍江省博士后基金(LBH-Z10167)資助課題

*通信作者：付寧 funinghit_paper@163.com