改進(jìn)的一比特量化壓縮感知重建算法*

黨 骙，馬林華，田 雨，孫玉雪，茹 樂

(1.空軍工程大學(xué) 航空航天工程學(xué)院，西安710038;2. 西安電子科技大學(xué) 綜合業(yè)務(wù)網(wǎng)理論及關(guān)鍵技術(shù)國家重點(diǎn)實(shí)驗(yàn)室，西安710071;3.空軍工程大學(xué) 信息與導(dǎo)航學(xué)院，西安710077)

1 引 言

壓縮感知理論指出，通過適當(dāng)?shù)姆椒ǎ∈栊盘柣蚩蓧嚎s信號可以從其線性欠采樣測量中精確重建出來［1－2］。目前大多數(shù)的研究所考慮的測量值都是實(shí)值的，具有無限比特精度。然而，在實(shí)際處理中，需要將采集到的測量值進(jìn)行量化，以確保能夠?qū)?shù)據(jù)進(jìn)行存儲和傳輸，即將實(shí)值測量值映射為有限域上的離散值［3］。例如，在均勻量化中，將測量值量化至2B個離散值，B 表示量化比特數(shù)。量化是不可逆的，在量化過程中會引入量化誤差，通常將量化誤差看作加性噪聲來處理。近年來，一些學(xué)者研究了測量值的量化問題，并提出了相關(guān)重建方法［4－5］。

Boufounos 和Baraniuk 在文獻(xiàn)［6］中指出，將測量值用一個比特表示，即只保留測量值的符號，仍然可以精確穩(wěn)定地重建原始信號。采用這種量化方式可以大大降低信號在傳輸和存儲過程中的比特數(shù)，在多數(shù)情況下，目標(biāo)是減少總的比特數(shù)和非測量數(shù)。并且在許多情況下，量化消耗遠(yuǎn)大于采樣消耗，而1－bit 壓縮感知在量化過程中只需要一個比較器就可以實(shí)現(xiàn)高速穩(wěn)定的量化。

目前，基于1－bit 壓縮感知的重建算法主要有符號匹配追蹤算法(Matching Sign Pursuit，MSP)［7］、約束步長收縮算法(Restricted－ step Shrinkage，RSS)［8］、二進(jìn)制迭代硬閥值算法(BIHT)［9］等，其中BIHT 算法比其他算法在重建精度和重建一致性上都要高。

本文正是在BIHT 算法的基礎(chǔ)上，在每一步迭代過程中引入回溯［10］篩選的步驟，提出了基于回溯的二進(jìn)制迭代硬閥值算法(BBIHT)，該算法在每次迭代過程中，將前后兩次迭代的支撐集合并，再在合并的支撐集下一致性重建?；厮莶襟E的加入優(yōu)化了迭代過程中支撐的選擇，避免了同一原子在前后兩次迭代中被反復(fù)篩選和刪除，降低了算法的重建復(fù)雜度。實(shí)驗(yàn)仿真表明，在較低采樣比特數(shù)下，BBIHT算法比BIHT 算法重建精度要高，重建速度要快。

2 1－bit 壓縮感知理論

1－bit 壓縮感知是考慮對測量值量化的一種極限情況，表示為

其中，sign(·)表示符號函數(shù)，當(dāng)測量值為正時取值為+1 否則為－1;M 表示測量值的數(shù)目，而在1－bit 量化中，測量數(shù)即比特數(shù)。為了得到更高的重建精度，可以增加M 值的大小，甚至可以大于信號長度N。

一致性重建定義［11］如下:

其中，Y=diag(y)，即量化后的測量值構(gòu)成的對角矩陣。

由于1－bit 量化使得信號幅度信息丟失，因此對信號增加一個能量約束，使重構(gòu)信號在單位超球面上:

這一約束使得求解空間縮小，提高了重建精度。

3 算法設(shè)計

3.1 二進(jìn)制迭代硬閥值算法

為了從1－bit 測量中重建出原始信號，文獻(xiàn)［9］給出BIHT 算法所求解問題為

其中，

BIHT 算法步驟如下:

步驟1:初始化，最大迭代次數(shù)nmax，迭代次數(shù)n=0，x0=0，稀疏度K;

步驟3:計算xn+1=ηKan+1()，并令n=n+1;

步驟4:當(dāng)n = nmax或y－sign(x)= 0 時輸出xn+1/‖xn+1‖，否則轉(zhuǎn)步驟2。

其中，μ為標(biāo)量，用來控制梯度下降步長的大小，函數(shù)ηK( v)用來保留v 中最大的K 個量并將其余量置零。

3.2 基于回溯的二進(jìn)制迭代硬閥值算法

本文受到文獻(xiàn)［10］中對支撐進(jìn)行回溯篩選的啟發(fā)，將回溯的方法引入BIHT 算法中，在每次迭代過程中，將前后兩次迭代的支撐進(jìn)行合并，并在該支撐下一致性重建，即在該支撐下最小化

BBIHT 具體算法步驟如下:

步驟1:初始化，最大迭代次數(shù)nmax，迭代次數(shù)n=0，x0=0，稀疏度K;

步驟3:計算cn+1=ηK(an+1)，合并前后兩次迭代支撐Γn=supp(cn+1)∪supp(xn);

總而言之，農(nóng)村氣象服務(wù)建設(shè)作為一項(xiàng)長期性、系統(tǒng)性、復(fù)雜性工程，必須投入更多人力、物力、財力，全面提升農(nóng)村氣象的整體服務(wù)水平。加大氣象服務(wù)工程建設(shè)力度，為有效預(yù)防和處理農(nóng)業(yè)災(zāi)害、增加農(nóng)民收入和農(nóng)作物產(chǎn)量發(fā)揮出不可取代的作用。此外，農(nóng)村氣象服務(wù)是新農(nóng)村重點(diǎn)建設(shè)內(nèi)容，對于社會進(jìn)步和國家繁榮發(fā)展等目標(biāo)實(shí)現(xiàn)提供了有力條件。

步驟4:在支撐集下一致性重建

步驟5:當(dāng)n=nmax或‖neg(YA)‖2=0 時，輸出xn+1=bn|K/‖bn|K‖2，否則轉(zhuǎn)步驟2。

通過對比研究BIHT 算法和BBIHT 算法發(fā)現(xiàn)，在BIHT 算法迭代過程中，不斷將信號殘差投影到測量矩陣A 列構(gòu)成的原子庫中最匹配的K 個原子，確定K 個可信賴的候選，當(dāng)認(rèn)為所選列是可信賴的，則將其加入下一次迭代序列。由于這種方式缺乏A 各列之間的正交性而不是最優(yōu)的，向量a 的某個支撐可能由于不在信賴候選集內(nèi)而被丟棄，但是在下一次的迭代中又因?yàn)榧尤霘埐钔队?，又被選入到可信賴的支撐集內(nèi)，因此可能產(chǎn)生a 的某個支撐被反復(fù)丟棄和保留，從而導(dǎo)致整個算法需要迭代較多次數(shù)才能達(dá)到較高重建精度。

而BBIHT 算法通過加入回溯步驟，使同一原子被反復(fù)選擇和丟棄的概率大大降低，通過在合并的支撐上一致性重建，提高了信號的重建精度和重建速度。本文算法所用思想與文獻(xiàn)［10］中基本相同，然而算法實(shí)現(xiàn)時文獻(xiàn)［10］采用最小二乘的方式，而本文算法是根據(jù)一致性原理進(jìn)行重建，且兩種算法針對問題不同，本文算法是考慮量化情況下的重建算法，因此也更加具有實(shí)際中的存儲傳輸意義。

4 實(shí)驗(yàn)仿真及分析

在文獻(xiàn)［9］中BIHT 算法已經(jīng)與其他算法進(jìn)行了對比，因此本文只用BBIHT 算法與BIHT 算法進(jìn)行對比，并且設(shè)定與該文獻(xiàn)相同的實(shí)驗(yàn)條件。原始待采樣信號x 長度為N，稀疏度為K 且非零值在單位球上隨機(jī)取值，即滿足‖x‖2=1，測量矩陣A 采用大小為M×N 的高斯隨機(jī)測量矩陣。定義重構(gòu)誤差為，角度誤差(Angular Error)為arccos〈x，〉/π，且均為1 000次實(shí)驗(yàn)的平均值。

設(shè)定信號長度N=1 000，稀疏度K=10，采樣率M/N 在區(qū)間［0，2］上取值(當(dāng)M/N＞1 時所獲得測量值將大于原始信號的長度，這在傳統(tǒng)的壓縮感知中是不存在的，然而在1－bit 壓縮感知中關(guān)注的是總的比特數(shù)而非測量值數(shù)，因此M/N＞1 的情況在1－bit壓縮感知中是常見的)所得BBIHT 與BIHT 重構(gòu)誤差比對如圖1所示，重建時間比對如圖2所示，角度誤差比對如圖3所示。

圖1 BBIHT 與BIHT 重建誤差比對Fig.1 Reconstruction error between BBIHT and BIHT

由圖1可以看出，采樣率在0.7 以下時，BBIHT的重建精度比BIHT 的要高約2～3 dB，在大于0.7時兩種算法的重建精度基本趨于相同，采樣率大于1.2 時兩者的重建精度基本一致。

圖2 BBIHT 與BIHT 重建時間比對Fig.2 Reconstruction time between BBIHT and BIHT

從圖2時間曲線可以看出，在相同條件下BBIHT 算法的重建速度要高于BIHT 算法;兩者時間開銷大致隨著采樣率的增加呈線性升高趨勢，且BIHT 算法的重建時間曲線斜率略大于BBIHT 算法時間曲線，因而隨著采樣率增加，BBIHT 算法的時間開銷增長速度略慢于BBIHT 算法。

圖3 BBIHT 與BIHT 重建角度誤差比對Fig.3 Reconstruction angular error between BBIHT and BIHT

由圖3可以看出，在采樣率小于0.6 時，采用BBIHT 算法重建信號所得角度誤差稍小于BIHT 算法，當(dāng)采樣率大于0.6 時，兩者的重建角度誤差基本相同，說明了本文所提算法的重建一致性要高于BIHT 算法。

5 結(jié) 論

本文對BIHT 算法迭代過程中可能產(chǎn)生原子被反復(fù)篩選和丟棄的情況進(jìn)行分析，并通過引入原子的回溯篩選思想，提出了基于回溯的BIHT 算法。通過這種方法，大大降低了同一原子在前后兩次迭代過程中被反復(fù)篩選和刪除的概率，降低了算法的重建復(fù)雜度。通過仿真實(shí)驗(yàn)可以看出，本文所提算法在采樣率較低時(低于0.7)的重建精度比BIHT算法高出約2～3 dB，達(dá)到重建精度所需時間略低于BIHT 算法，重建一致性也高于BIHT 算法，說明本文算法比BIHT 算法更具有實(shí)際應(yīng)用意義。本文實(shí)驗(yàn)結(jié)果均是通過大量樣本得到的平均值，實(shí)驗(yàn)中并無例外情況。下一步還應(yīng)更加深入地進(jìn)行數(shù)學(xué)分析，使算法在理論上更加完善。

［1］ 邵文澤，韋志輝. 壓縮感知基本理論:回顧與展望［J］.中國圖像圖形學(xué)報，2012，17(1):1－12.SHAO Wen－ze，WEI Zhi－h(huán)ui. Advances and perspectives on compressed sensing theory［J］. Journal of Image and Graphics，2012，17(1):1－12.(in Chinese)

［2］ 喬田田，張宇，李維國.一種基于壓縮感知的信號重建新算法［J］.電訊技術(shù)，2013，53(10):1289－1292.QIAO Tian－tian，ZHANG Yu，LI Wei－guo. A New Signal Reconstruction Algorithm Based on Compressed Sensing［J］. Telecommunication Engineering，2013，53(10):1289－1292.(in Chinese)

［3］ Boufounos P T，Jacques L. Quantization and Compressive Sensing［EB/OL］. ［2014－05－07］. http://arxiv.org/abs/1405.1194.

［4］ Zymnis A，Boyd S，Candes E.Compressed sensing with quantized measurements ［J］. IEEE Signal Processing Letters，2010，17(2):149－152.

［5］ Laska J N，Boufounos P T，Davenport M A，et al. Democracy in action:Quantization，saturation，and compressive sensing［J］. Applied and Computational Harmonic Analysis，2011，31(3):429－443.

［6］ Boufounos P T，Baraniuk R G. 1－bit compressive sensing［C］//Proceedings of 2008 42nd Annual Conference on Information Science and Systems. Princeton，NJ:IEEE，2008:16－21.

［7］ Boufounos P T. Greedy sparse signal reconstruction from sign measurements［C］// Proceedings of the 43rd Asilomar Conference on Signals，Systems and Computers.Piscataway，NJ，USA:IEEE，2009:1305－1309.

［8］ Laska J N，Wen Z，Yin W，et al. Trust，but verify:Fast and accurate signal recovery from 1－bit compressive measurement［J］.IEEE Transactions on Signal Processing，2011，59(11):5289－5301.

［9］ Jacques 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(4):2082－2102.

［10］ 楊海蓉，方紅，張成，等. 基于回溯的迭代硬閥值算法［J］. 自動化學(xué)報，2011，37(3):276－282.YANG Hai－rong，F(xiàn)ANG Hong，ZHANG Cheng，et al. Iterative Hard Thresholding Algorithm Based on Backtracking［J］. ACTA Automatica Sinica，2011，37(3)，276－282.(in Chinese)

［11］ 肖濤，馬社祥. 一比特壓縮傳感的貪婪重構(gòu)算法［J］.科學(xué)技術(shù)與工程，2012，12(34):9182－9185.XIAO Tao，MA She－xiang. Greedy Reconstruction Algorithm of One－bit Compressed Sensing ［J］. Science Technology and Engineering，2012，12(34):9182－9185.(in Chinese)