基于混合梯度的硬閾值追蹤算法

楊立波，蔣鐵鋼，徐志強

（廣東科技學院機電工程系，廣東東莞523083）

（*通信作者電子郵箱jiangtiegang5201@163.com）

0 引言

傳統的信號處理方式基于Shannon-Nyquist 采樣理論，根據這一理論，當采樣率大于信號最大頻率的兩倍時可以重建原始信號。大數據時代海量的信息量極大地增加了傳統信號處理方式的功耗和存儲、傳輸成本，因此，研究新型高效的信號處理技術非常重要。壓縮感知（Compressed Sensing，CS）理論最初由Candès 等［1］和Donoho［2］提出，壓縮感知將信號的采集和處理過程聯合在一起，探索了信號的稀疏特性。在傳統的信號處理中，采樣率取決于信號的最高頻率，而壓縮感知中采樣率取決于信號的稀疏程度。現實生活中大多數信號可以被認為在某些變換域內是稀疏的或可壓縮的，例如離散余弦基和小波基可用于大多數自然圖像的壓縮［3］。目前，壓縮感知技術已在圖像處理、通信、人工智能等領域被廣泛地研究和應用［4-5］。

步驟3 計算候選Tn+1=supp(Hs(an+1))∪supp(Hs(bn+1))。

2.3 HGHTP算法性能分析

從2.2 節算法流程可知，HCHTP 算法在每次迭代中同時更新了當前迭代點處的梯度與共軛梯度。由于s?N，因此矩陣是正定的，在求解方程=時，梯度下降法具有與相關的收斂速度，共軛梯度法具有與相關的收斂速度，其中κ是的條件數。由此可知，在測量矩陣子矩陣AΓn的列原子相關性相同時，使用共軛梯度方法比梯度下降法具有更快的收斂速度［14］。考慮到共軛梯度法的加速優勢，HGHTP 算法引入共軛梯度法作為支撐集的挑選依據之一，對僅使用梯度下降法來挑選支撐集的算法做了補充，加速算法的收斂。由于共軛梯度法在收斂速度上的優勢，因此在迭代點xn處的共軛梯度尋優方向dn中可能包含有益于加速挑選正確支撐集的信息。HGHTP 算法同時將梯度方向和共軛梯度方向作為支撐集選擇的參照，充分利用了共軛梯度的優勢，因此在算法迭代過程中正確的支撐能被快速定位。其次，HGTHP 算法中引入共軛梯度主要用于支撐集的挑選，由于通過梯度和共軛梯度更新的稀疏系數中其非零元素的位置及包含的信息能量不同，同時考慮到使用共軛梯度更新的稀疏系數中可能包含能量更大的原子，因此HGHTP 算法將兩種不同更新方式的支撐集進行合并，并選取能量最大的原子所對應的位置作為候選支撐集，同時保留了元素尺度大小。這意味著在每次迭代中更新的稀疏系數和候選支撐集中都可能包含梯度域和共軛梯度域的信息。

BCGIHT 算法中的共軛梯度是作為尋優方向，加速殘差的減小，使該算法能加速收斂，但是在迭代過程中每次只用單一的梯度或共軛梯度方向作為尋優方向，沒有綜合考慮梯度與共軛梯度的作用。由于BCGIHT 算法需要保證在前后迭代中支撐集變化不大時才能體現出共軛梯度的優勢，因此BCGIHT 算法通常只在迭代到接近精確解時才能體現出加速優勢。在迭代過程中，不管前后迭代的支撐集是否一樣，HGHTP 算法都綜合考慮梯度與共軛梯度對支撐集選擇的影響，并選取兩個更新的稀疏系數中最大s個原子作為候選支撐集。即使前后迭代中支撐集對應的測量矩陣子矩陣不一樣，共軛梯度域內稀疏系數中的某些原子的絕對值也可能比梯度域內原子的絕對值大，這是BCGIHT 算法沒有考慮到的一點。HGHTP 算法則將梯度和共軛梯度對支撐集選擇的影響有機地結合在一起，在每一次迭代中綜合考慮了梯度與共軛梯度的影響，吸取了共軛梯度方向中有益于加速算法收斂的信息。

幾種迭代硬閾值類算法中，CGIH 算法的計算量主要在更新梯度或共軛梯度方向步驟中，其算法復雜度可以估計為O(MN)。GraSP 算法在每次迭代中挑選了2s個原子，且進行了回溯操作，其復雜度可以估計為O(MN+M(3s)2)。BIHT算法、BCGIHT 算法和HGHTP 算法的計算量集中在計算梯度（共軛梯度）和更新稀疏系數中，它們的算法復雜度相當，可以估計為O(MN+M(2s)2)。盡管HGHTP 算法的計算復雜度與BIHT 和BCGIHT 算法相當，但是其能快速定位系數的正確支撐，迭代次數更少（見圖2），所以在相同重構精度下，它所需的重構時間更少（見表1）。

3 實驗結果及討論

本章通過對一維隨機高斯信號和標準測試圖像的重構實驗驗證所提出算法的重構性能，對比算法包括BIHT 算法、BCGIHT 算法、GraSP 算法和CGIHT 算法。實驗環境配置為Intel（i5-7500，8 GB內存），仿真軟件為Matlab 2018b。

3.1 一維信號重構實驗

圖1 為采樣數M= 128 時各算法在不同稀疏度情況下的重構成功率。從圖1可知，當稀疏度大于35時，各算法的重構成功率逐漸降低，這是因為稀疏度增加導致了支撐集相關性的增加，從而使重構算法難以找到正確的支撐集。BCGIHT算法和HGHTP 算法的重構表現較好，在稀疏度s= 45 時保持著較高的重構成功率。整體來說，HGHTP 算法的重構成功率要優于其他對比算法。

圖1 不同稀疏度下不同算法重構成功率對比Fig. 1 Reconstruction success rate comparison of different algorithms with different sparsities

圖2 記錄了在采樣率不變時，各算法的平均迭代次數。從圖2可知，在稀疏度小于50時，CGIHT算法的迭代次數明顯高于其他對比算法，這是因為CGIHT 算法在迭代過程中更新系數時沒有精確估計，導致其需要較多迭代次數才能達到較高的精度。HGHTP 算法的迭代次數比GraSP 算法和BCGIHT算法稍少，這意味著HGHTP算法中采用梯度和共軛梯度混合支撐集選擇的策略起到了加速的作用。

圖3 記錄了稀疏度s= 10 時在不同采樣數情況下各算法的重構成功率。從圖3 可知，HGHTP 算法和GraSP 算法在采樣數大于58 時，基本能達到100%的成功率，而BCGIHT 算法和GraSP算法則需要采樣數大于72時才能達到這一水平。這說明在稀疏度不變時，HGHTP 算法和BCGIHT 算法相對于其他算法需要更少的采樣數。

圖2 不同稀疏度下迭代次數對比Fig. 2 Iteration number comparison with different sparsities

圖3 不同采樣數下不同算法重構成功率比較Fig. 3 Reconstruction success rate comparison of different algorithms with different sampling numbers

3.2 二維圖像重構實驗

本實驗采用大小為256×256 像素的標準測試圖片“Lena”來驗證本文提出算法的圖像重構性能。實驗過程中對原圖像進行小波變換，取稀疏度為s=M4= 32。觀測矩陣選用大小為M×N的隨機高斯矩陣，定義采樣率為r=M N。本實驗中所有的算法均獨立測試200 次，以平均值作為實驗結果。圖像的重構質量用峰值信噪比（Peak Signal-to-Noise Ratio，PSNR）來評估，其計算公式為:

圖4給出了在r= 0.5時不同算法重構Lena原圖得到的直觀效果圖對比，其中（a）為原圖，（b）～（f）分別為由BIHT 算法、BCGIHT 算法、GraSP 算法、CGIHT 算法和HGHTP 算法重構得到的圖像。從圖4 可以直觀地看出GraSP 算法和本文提出的HGHTP算法重構效果比其他算法稍好。

表1 記錄了在不同采樣率下不同算法的重構PSNR 和重構時間。從表可以看出CGIHT 算法的重構PSNR 值最低，表明其重構質量較差，這是因為相對于其他對比算法，CGIHT算法在迭代過程中沒有進行“去偏”操作（即用最小二乘法更新系數）。在采樣率較低時（r= 0.3），HGHTP 算法的重構PSNR值比其他對比算法高至少2 dB。當r≥0.5 時，雖然GraSP 算法的重構PSNR 值與HGHTP 算法相當，但其重構時間遠高于HGHTP 算法，這與其較高的算法復雜度有關，符合第2 章的分析。BCGIHT 算法采用梯度與共軛梯度交替的方式作為尋優方向，這對觀測矩陣的非相關性要求很嚴格，即只有在觀測矩陣變化不大的時候BCGIHT 算法才能起到加速的作用。雖然HGHTP 算法和BCGIHT 算法的算法復雜度相當，但其重構質量要優于BCGIHT算法，重構時間相較于BCGIHT算法也分別減少了47%（r= 0.3）、40%（r= 0.5）和32%（r= 0.7）。

圖4 不同算法的重構結果Fig. 4 Reconstruction results of different algorithms

表1 不同采樣率下不同算法性能對比Tab. 1 Performance comparison of different algorithms under different sampling rate

現實中的圖像通常會存在不同程度的噪聲污染，為了驗證本文所提出算法的抗噪性能，在采樣率r= 0.5的情況下，對原始圖片加上不同方差的高斯噪聲，對比不同算法的重構效果，實驗結果記錄在表2 中。從表2 可以看出，隨著噪聲的加強，各算法的重構PSNR 值均逐漸降低。對比表1 和表2 可知隨著噪聲強度的加大，CGIHT 算法的重構PSNR 值降低幅度較小，說明其抗噪性能較好。GraSP 算法的抗噪性能較差，尤其在噪聲強度較大時表現明顯，HGHTP 算法和BIHT 算法、BCGIHT算法的抗噪能力相當，介于CGIHT算法和GraSP算法之間。

表2 高斯噪聲環境下不同算法重建PSNR（r = 0.5）單位：dBTab. 2 Reconstruction PSNR of different algorithms in Gaussian noise environment（r = 0.5） unit:dB

4 結語

本文在壓縮感知重構算法的研究基礎上，針對迭代硬閾值類算法迭代次數多、重構時間長的問題，提出HGHTP算法，并對算法性能作了分析:將梯度域和共軛梯度域下支撐集混合，優化支撐集選擇策略，確保快速定位正確支撐的位置；采用最小二乘法對候選支撐集作二次篩選，保證算法重構精度。一維信號和圖像重構實驗表明HGHTP 算法在保證重構精度的前提下相比同類迭代硬閾值類算法需要更少迭代次數，重構時間更短，且在不同強度噪聲環境下具有較好的抗噪性能。