自適應(yīng)稀疏度的1 bit壓縮重構(gòu)算法

黃澳 柏正堯，2 周 雪

（1.云南大學(xué)信息學(xué)院，云南昆明 650500；2.云南大學(xué)-云南天文臺信息技術(shù)聯(lián)合實驗室，云南昆明 650500）

1 引言

在過去的幾十年里，數(shù)字處理技術(shù)的發(fā)展刺激了對更大帶寬信號和更高分辨率圖像和視頻的數(shù)字化需求的快速增長。然而，傳統(tǒng)ADC 設(shè)備無法滿足這種帶寬數(shù)字化的需求。為了解決這個問題，一種不同的數(shù)據(jù)采集框架，即壓縮感知（Compressed Sensing，CS）出現(xiàn)了，基于CS 提出的顯著性圖像可以廣泛應(yīng)用于許多計算機視覺領(lǐng)域的應(yīng)用，CS利用信號的稀疏特征，能用數(shù)目顯著低于奈奎斯特采樣定理要求的樣本準確地重構(gòu)出稀疏信號。

目前，壓縮感知理論在諸多領(lǐng)域都取得了很好的研究成果，但是壓縮感知要想從理論走向?qū)嶋H還需要考慮存儲、傳輸和處理等過程。為了降低硬件的復(fù)雜性、成本、數(shù)據(jù)傳輸帶寬和能量，需要用少量的比特來量化測量。因此，一些學(xué)者提出了1位CS，利用每個被測符號進行1 bit量化，恢復(fù)稀疏信號，提高信號采樣效率。2007 年，Boufouno 和Baraniuk 等人［1］提出了一種基于不定點迭代（Fixed-Point Continuation，F(xiàn)PC）的算法--重正規(guī)化不動點迭代算法（Renormalized Fixed Point Iteration，RFPI），該算法利用單邊的l2范數(shù)來強制一致性。該算法是有效的，但出現(xiàn)符號跳變時表現(xiàn)不佳。除了基于FPC的方法外，還提出了其他一些1位CS算法，包括二進制迭代硬閾值（Binary Iterative Hard Thresholding，BIHT）［2］、匹配符號追蹤（Matching Sign Puisit，MSP）［3］、基于正交匹配追蹤（Orthogonal Matching Pursuit，OMP）［4］的量化子空間追蹤（Quantization Subspace Pursuit，QSP）與量化壓縮采樣（Quantization Compressive Sampling Matching Pursuit，QCaSamp）［5］、基于l1最小化線性回歸（Linear Programming，LP）［6］、歷史（HISTORY）算法［7］、被動（passive）算法［8］和類似于信賴域的限制步長收縮算法RSS［9］。這些算法或多或少都有缺陷。QSP、QCasamp、QMP、BIHT、MSP 和HISTORY 這些需要稀疏性水平作為先驗信息，而RFPI、passive 和RSS 則不需要。另外，BIHT 在重建誤差和一致性方面優(yōu)于MSP和RSS。

對1 bit 壓縮感知的另一個挑戰(zhàn)是噪聲環(huán)境下的魯棒性。在有噪聲的情況下，二進制測量值是隨機擾動的，符號跳變嚴重降低了恢復(fù)性能。文獻［10］提出的自適應(yīng)異常值追蹤（Adaptive Outlier Pursuit，AOP）算法，以及基于RFPI 與自適應(yīng)異常值追蹤的NARFPI［11］算法在噪聲環(huán)境中具有魯棒性。盡管這些信號重構(gòu)算法具有良好的性能，但無一例外都需要信號稀疏性這一先驗信息。因此，一些研究者致力于通過克服稀疏依賴性來提高信號恢復(fù)的精度，文獻［12］提出一種基于AOP 思想的改進不動點的FPC-AOP-算法，它雖然不需要信號稀疏度的先驗知識，但性能不理想。另外，用于處理符號跳變錯誤的魯棒的1 bit 貝葉斯壓縮感知（Bayesian Compressed Sensing，BCS）［13］，信號重構(gòu)性能良好且不需要信號的稀疏度先驗信息，但是卻需要稀疏信號與噪聲的高斯逆伽馬先驗信息。文獻［14］提出分塊稀疏信號重構(gòu)算法，性能優(yōu)于BIHT 算法，但由于需要計算Toeplitz 矩陣，計算效率不高，適用于維度比較低的稀疏信號重構(gòu)。文獻［15］考慮超定與欠定條件下的最小二乘法，引入一種原始對偶活動集算法，提出原對偶連續(xù)主動集算法（A primal dual active set algorithm with continuation，Pdasc）算法來解決非平滑問題，對噪聲和符號跳變具有一定魯棒性，然而只對稀疏度較低有效，但對于稀疏度高的問題重構(gòu)性能不佳。文獻［16］提出非凸稀疏性的誘導(dǎo)懲罰型算法，極大最小的凸懲罰項（Minimax Concave Penalty，MCP），求解對偶問題，來求得解析解。能夠獲得較好的結(jié)果并提高恢復(fù)性能。但對噪聲魯棒性不高，而且對于低維信號性能不佳?？傊@些算法要么需要稀疏性水平的先驗信息，要么信號重構(gòu)性能有限。

針對上述方法的局限性，本文提供出一種簡單而有效的算法，在稀疏性未知的情況下，借鑒稀疏度自適應(yīng)匹配追蹤（Sparsity Adaptive Matching Pursuit，SAMP）［17］自適應(yīng)稀疏度思想，結(jié)合自適應(yīng)異常值追蹤與自適應(yīng)稀疏度的思想實現(xiàn)最優(yōu)的信號重構(gòu)性能。自適應(yīng)異常值追蹤能夠檢測出大部分的符號跳變，并且在符號跳變被糾正后，測量結(jié)果更加準確，因此能夠提高這算法的性能。本文方法利用彈球損失函數(shù)，提高對符號跳轉(zhuǎn)的檢測，此外，還設(shè)置了正則化參數(shù)，以加快運算速度。與現(xiàn)有算法相比，該算法的性能有顯著提高。數(shù)值結(jié)果表明了該算法的有效性和優(yōu)越性。

2 壓縮感知理論

2.1 一位壓縮感知理論

壓縮感知是稀疏可壓縮信號采樣和重構(gòu)的一種方法。不失一般性，假設(shè)信號x是N 維向量，稀疏度為K，通過采樣，得到信號y=Φx，要從y中重構(gòu)信號x：

一位壓縮感知問題變?yōu)椋?/p>

信號的幅度通過一位量化丟失，將稀疏信號限制在超球面上，

二進制迭代硬閾值算法（BIHT）是在迭代硬閾值算法（IHT）的基礎(chǔ)上提出的。在經(jīng)典壓縮感知中，引入IHT對稀疏信號進行迭代重構(gòu)。

IHT 方法用于解決壓縮感知中的類似以下的問題：

IHT迭代公式有：

其中ηK(x)，通過保持K個最大的項的大小為x，suppK(x)其余設(shè)置為0。

類似地，在1 位壓縮感知中，BIHT 修改IHT 中的梯度步驟，迭代計算如下：

BIHT算法可以看做是解決這樣一個問題：

[·]-是負值函數(shù)，大于零的元素取零，負數(shù)不變（單邊l1范數(shù)）。

BIHT 算法在無噪聲的情況下能得到更好的可行解。但是如果有許多測量信號值發(fā)生跳變，BIHT的效果變得很不理想。

假設(shè)噪聲級別（發(fā)生跳變的信號所占比例）給定，我們可以選擇一個合適的整數(shù)L，整個測量值中最多有L個信號被錯誤地采集（發(fā)生跳變）。比如測量值y∈{-1，+1}M，Λ∈RM是一個二值矢量表示數(shù)據(jù)的對錯：

我們可以把我們的問題表述為：

自適應(yīng)離群點追蹤的求解，采用交替極小化方法［10］求解：

（1）固定Λ，求解x：

（2）固定x，求解Λ：

這個問題可以從[y·(Φx)]-的M個元素中選擇M-L個元素，這些元素滿足和最小。對于問題一中估計出來的x，我們在一步中更新Λ：

T是[y·(Φx)]-中的第L大的元素值。

BIHT-AOP算法的是為了找到ΦT(y-sign(Φx))的最小值。采用梯度下降法求出最小值，通過硬閾值函數(shù)映射到單位球面上。交替極小化法，求解原稀疏信號。

本文首先使用高斯稀疏信號作為原始信號進行仿真實驗。信號長度N=1000，M=500，信號噪聲比例50 dB，跳變次數(shù)L從10到100，間隔為10，感知矩陣Φ為隨機高斯矩陣。使用BIHT-AOP重構(gòu)。在不同稀疏度下，L從10 到100 時，進行100 次實驗。實驗結(jié)果如圖1 所示，在信號跳變固定下，稀疏度K未知下，不同稀疏度對重構(gòu)信號的精度影響較大。相同稀疏度下，信號跳變越多，重構(gòu)信號信噪比也就越低。通過上述實驗結(jié)果分析，稀疏度K與噪聲是影響重構(gòu)效果的兩個重要因素，為了提高重構(gòu)信號信噪比，有必要去解決對稀疏信號的稀疏度K的依賴以及提升對信號噪聲魯棒性。

2.2 自適應(yīng)稀疏度的一位壓縮感知算法

我們將固定步長自適應(yīng)方法與自適應(yīng)異常值追蹤引入PIHT 算法中，提出了一種自適應(yīng)稀疏度的AOP-ASPIHT算法，用于解決未知信號稀疏度與符號跳變導(dǎo)致的重構(gòu)效果不理想的問題。其中，固定步長法主要是通過計算得到信號稀疏度的估計數(shù)，然后將估計數(shù)輸入到算法中，進行下一步的信號部分恢復(fù)。

首先定義彈球損失：

文獻［18］給出了以下關(guān)于一位壓縮感知的凸模型：

在無噪聲情況下，PIHT 算法相對BIHT 有所提高。但如果有信號跳變，兩種算法效果都變得不理想。為此加入自適應(yīng)異常值追蹤。變?yōu)橄率鰡栴}：

首先設(shè)定初始步長m＜K作為迭代的初始硬閾值參數(shù)，然后判斷相鄰兩次迭代信號的能量差和殘差大小，確保迭代向收斂方向發(fā)展。

當相鄰兩次迭代信號的能量差小于ε時，此時的硬閾值大小（估計稀疏度S）最接近信號稀疏度，再利用S恢復(fù)原信號。步驟（1）到步驟（3），實現(xiàn)了稀疏度的粗估計和迭代變量的初始化。詳細如表1所示算法1。

表1 本文提出算法偽代碼Tab.1 The pseudo-code of the proposed algorithm in this paper

（1）確定固定步長m，使其滿足m＜K。

（2）采用步長m值的大小作為硬閾值的初始值在球面映射重建。通過計算相鄰兩次迭代過程中信號估計值的能量差和殘差，判斷殘差是否隨迭代次數(shù)的增加而減小，計算出兩個信號的能量差小于ε。

（3）記錄此時硬閾值的大小，并將其用作估計的信號稀疏度以用于信號恢復(fù)。

3 實驗仿真與結(jié)果分析

3.1 對AOP-ASPIHT仿真

我們在i5-7500，GTX750ti 電腦上用Matlab R2020a軟件進行仿真實驗，比較了有（無）噪聲影響下算法的信號重構(gòu)性能。實驗中的信號恢復(fù)性能指標主要基于主流的評價指標，信噪比（Signal Noise Ratio，SNR）和均方誤差（Mean Square Error，MSE），絕對均方誤差（Absolute Mean Square Error，AMSE）與漢明誤差（Hamming Error），其中信噪比定義如下：

均方誤差（MSE）定義如下：

絕對均方誤差（AMSE）定義如下：

漢明誤差（HE）定義如下：

3.2 無噪聲影響下算法性能比較

感知矩陣Φ全部使用隨機高斯矩陣。其中，模擬信號的長度固定在N=256，觀測次數(shù)M=100，稀疏度K=10，AOP-ASPIHT 參數(shù)步長m=5。比較在符號跳變率為0%（無符號跳變），無噪聲，稀疏度為10時，BIHT 重構(gòu)算法，歸一化二進制迭代硬閾值（Normalized Binary Iterative Hard Thresholding，NBIHT）［19］，PIHT［3］，以及本文提出的AOP-ASPIHT 的均方誤差（MSE），信噪比（SNR）以及運行時間。進行了100次蒙特卡洛實驗。

文獻［19］證明了最佳誤差衰減率取參數(shù)μ=得到歸一化二進制迭代硬閾值NBIHT 算法，將BIHT 中損失函數(shù)換為彈球損失函數(shù)，得到PIHT。仿真實驗結(jié)果如表2 所示，在無噪聲，無符號跳變下，NBIHT 算法性能相對BIHT 算法并沒有提高，但是運行時間少于BIHT算法。PIHT算法信號重構(gòu)性能是優(yōu)于BIHT 算法，MSE 減低2.1%，信噪比提高5.13%，運行時間減少約BIHT 的1/6。PIHT（α=，將BIHT 算法中μ值設(shè)置為μ=性能相對PIHT（α=0.05）有所提升，本文提出的AOP-ASPIHT算法重構(gòu)性能明顯優(yōu)于PIHT，BIHT。相對BIHT，MSE 降低9.72%，信噪比提高17.09%，運行時間減少約BIHT 的1/3。在無噪聲情況下，PIHT 相對BIHT 算法重構(gòu)性能有所提升，NBIHT 算法相對BIHT 運行時間有所降低。為此考慮在下一步有噪聲實驗中加入歸一化參數(shù)。

表2 四種算法性能比較Tab.2 Performance comparison of four algorithms

3.3 有噪聲影響下算法性能比較

采用AMSE，SNR，HE 與運行時間等指標對PIHT［3］，BIHT-AOP［10］，PIHT-AOP［3］及本文提出的AOP-ASPIHT 算法重構(gòu)性能進行比較。模擬信號采用經(jīng)典的高斯稀疏信號。稀疏信號固定長度N=1000，觀測次數(shù)M從200 到700，間隔為100。稀疏度設(shè)置K為10，符號跳變比例5%～10%（稀疏信號中有M× 10%個符號跳變）。PIHT，BIHT-AOP，PIHTAOP以及本文提出的AOP-ASPIHT步長參數(shù)均設(shè)置為

為驗證AOP-ASPIHT 算法性能重構(gòu)性能，利用BIHT 算法，BIHT-AOP 算法，PIHT-AOP 以及本文提出的AOP-ASPIHT對信號進行重構(gòu)，比較其絕對均方誤差，信噪比，漢明誤差以及運行時間。由圖2（a），（b）以及圖3 四種算法漢明誤差，運行時間的對比，可以看出本文提出的算法信號重構(gòu)性能要優(yōu)于PIHT，BIHT-AOP，PIHT-AOP，在測量值M=300 時，相對PIHT-AOP 算法本文提出算法絕對均方誤差降低約0.15，信噪比提高約5 dB，漢明誤差降低約0.04。這說明本文提出方法可以有效地降低符號跳變對重構(gòu)信號的性能的影響。M值超過600之后本文提出方法重構(gòu)性能SNR 隨著測量值增加，增長變緩慢。由圖3（b）看出，BIHT-AOP 算法由于在算法過程中增加了對符號跳變位置的檢測，消耗了時間，其運行時間增加。在M=400 時，運行時間超過本文提出的AOP-ASPIHT。PIHT 算法可以降低符號跳變的影響，加入自適應(yīng)異常值追蹤方法后，可以進一步降低符號跳變的影響使得算法收斂速度快。本文提出的AOP-ASPIHT算法利用了相鄰殘差能量信息，雖然增加了對稀疏度的估計，但是可以使得迭代次數(shù)降低，算法收斂速度相對BIHT-AOP加快。

為驗證符號跳變比例對信號重構(gòu)性能的影響，本文考慮M=500，N=1000，K=10。符號跳變比例為5%到10%，每次增長1%。實驗結(jié)果如圖4 跳變對信噪比的影響所示，跳變比例在5%四種算法SNR差別不大。隨著跳變比例增加，四種算法SNR 均降低，AOP-ASPIHT 信噪比下降最慢，其次是PIHTAOP，再其次是BIHT-AOP，說明PIHT 算法本身就能減小符號跳變的影響，主要是因為PIHT 通過設(shè)計邊緣距離來抑制符號跳變對信號稀疏重構(gòu)的影響。本文所提出的AOP-ASPIHT 利用回溯思想，來估計信號稀疏度的有助于檢測符號跳變的位置，其性能提高。從圖4可以看出，符號跳變比例10%時，AOP-ASPIHT 信噪比相對提高3 dB。說明本文提出的方法可以更好的抗符號跳變引起的噪聲。

3.4 與其他先進算法性能比較

采用MSE 與運行時間等指標對其他先進算法如BIHT［1］，BIHT-AOP［10］，LP［26］，Passive［8］，Pdasc［15］等及本文提出的AOP-ASPIHT算法重構(gòu)性能進行比較。其中BIHT，BIHT-AOP，LP 均需要稀疏度先驗信息，Pdasc，Passive 以及本文提出的方法均不需要稀疏度水平。模擬信號采用經(jīng)典的高斯稀疏信號。稀疏信號固定長度N=1000，觀測次數(shù)M從300 到600，間隔為50。稀疏度設(shè)置K為10，符號跳變比例分別為1%～10%與2%到14%（稀疏信號中有M×符號跳變比例個符號跳變）。其中BIHT，BIHTAOP，以及本文提出的AOP-ASPIHT 步長參數(shù)均設(shè)置為

為驗證AOP-ASPIHT 算法性能重構(gòu)性能，利用BIHT，BIHT-AOP，LP，Passive，MCP，Pdasc 以及本文提出的AOP-ASPIHT 對信號進行重構(gòu)，比較其均方誤差與信噪比。稀疏信號固定長度N=1000，觀測次數(shù)M從300 到600，間隔為50。稀疏度設(shè)置K為10，符號跳變比例1%，噪聲比例為0.1。由圖5（c），（d）看出，本文提出的算法信號重構(gòu)性能要優(yōu)于BIHT，BIHT-AOP，LP，Passive，MCP，Pdasc，在測量值M=450時，相對BIHT-AOP算法本文提出算法絕對均方誤差降低約0.02，信噪比提高約5 dB。這說明本文提出算法可以有效地降低符號跳變對重構(gòu)信號的性能的影響且對低M值的稀疏信號有較好的恢復(fù)特性。M值超過600 之后本文提出算法重構(gòu)性能SNR 達到51 dB，其余各種算法隨著M的增大，恢復(fù)效果逐漸增強，可以最高達到45 dB。原因是PIHT算法本身就能減小符號跳轉(zhuǎn)的影響，加入自適應(yīng)異常值追蹤方法后，可以進一步降低符號跳變，此外利用回溯思想，來估計信號稀疏度的有助于檢測符號跳變的位置，其性能提高。且本文算法不易受M值的影響，其余如LP，Passive，MCP，Pdasc 各種算法受M值影響較大，小M值甚至不能很好的恢復(fù)稀疏信號。說明本文提出的方法對噪聲具有較好的魯棒性。

為驗證符號跳變比例對信號重構(gòu)性能的影響，本文考慮首先考慮小M值，M=300，N=1000，K=10符號跳變比例為1%到10%，每次增長1%。實驗結(jié)果如圖5（a）所示，跳變比例在1%，性能相對最好的PDASC 算法重構(gòu)成功率約為0.75，此時本文所提算法重構(gòu)成功率達到1。隨著跳變比例增加，七種算法重構(gòu)成功率均降低，AOP-ASPIHT 算法重構(gòu)成功率下降最慢，其次是BIHT-AOP。主要因為本文所提出的AOP-ASPIHT 利用回溯思想，來估計信號稀疏度的有助于檢測符號跳變的位置，此外還通過設(shè)計邊緣距離來抑制符號跳變對信號稀疏重構(gòu)的影響，其性能相對BIHT-AOP 提高。其余算法都能一定程度抑制符號跳變引起的噪聲，但性能隨著跳變比例的增大，信號重構(gòu)成功率逐漸降低，在4%時，幾乎其他算法信號重構(gòu)成功率接近0。說明其他算法能一定抗符號跳變，但隨著符號跳變比例增大，性能逐步下降。本文所提算法能很好解決符號跳變引起的信號恢復(fù)性能不佳的問題。其次本文考慮M值對其他算法如LP，Passive，MCP，Pdasc 恢復(fù)性能影響較大，設(shè)計如下實驗。M=600，N=1000，K=10 符號跳變比例為2%到14%，每次增長2%。實驗結(jié)果如圖5（b）所示，LP，Passive，MCP，Pdasc，BIHT重構(gòu)成功率都相對M=300 時的重構(gòu)成功率有所提高，說明隨著M值增加，各類算法都具有一定的抗符號跳變能力，但隨著符號跳變比例增大，重構(gòu)性能都下降。在12%時，幾乎其他算法信號重構(gòu)成功率接近0，而本文算法信號重構(gòu)成功率依然接近0.6。說明本文提出的算法對符號跳變引起的噪聲具有很好的魯棒性。

4 結(jié)論

我們提出了具有自適應(yīng)稀疏性的1 bit壓縮感知算法。通過計算殘差能量大小，有效地學(xué)習(xí)了信號和噪聲，采用固定步長學(xué)習(xí)硬閾值參數(shù)，近似計算稀疏度，引入AOP 進一步降低符號跳變的影響，獲得了滿意的結(jié)果。通過均方誤差（MSE），信噪比，絕對均方誤差（AMSE）和重構(gòu)成功率分析，說明本文提出的1 bit 壓縮感知重建算法是有效的，并具有對噪聲的魯棒性。本文重構(gòu)算法很好地解決了重構(gòu)算法稀疏度依賴性問題，顯著提升了重構(gòu)效果。

在未來的工作中，我們計劃將算法應(yīng)用于天文射電信號功率譜估計研究中。