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

楊立波，蔣鐵鋼，徐志強(qiáng)

（廣東科技學(xué)院機(jī)電工程系，廣東東莞523083）

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

0 引言

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

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

2.3 HGHTP算法性能分析

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

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

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

3 實(shí)驗(yàn)結(jié)果及討論

本章通過(guò)對(duì)一維隨機(jī)高斯信號(hào)和標(biāo)準(zhǔn)測(cè)試圖像的重構(gòu)實(shí)驗(yàn)驗(yàn)證所提出算法的重構(gòu)性能，對(duì)比算法包括BIHT 算法、BCGIHT 算法、GraSP 算法和CGIHT 算法。實(shí)驗(yàn)環(huán)境配置為Intel（i5-7500，8 GB內(nèi)存），仿真軟件為Matlab 2018b。

3.1 一維信號(hào)重構(gòu)實(shí)驗(yàn)

圖1 為采樣數(shù)M= 128 時(shí)各算法在不同稀疏度情況下的重構(gòu)成功率。從圖1可知，當(dāng)稀疏度大于35時(shí)，各算法的重構(gòu)成功率逐漸降低，這是因?yàn)橄∈瓒仍黾訉?dǎo)致了支撐集相關(guān)性的增加，從而使重構(gòu)算法難以找到正確的支撐集。BCGIHT算法和HGHTP 算法的重構(gòu)表現(xiàn)較好，在稀疏度s= 45 時(shí)保持著較高的重構(gòu)成功率。整體來(lái)說(shuō)，HGHTP 算法的重構(gòu)成功率要優(yōu)于其他對(duì)比算法。

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

圖2 記錄了在采樣率不變時(shí)，各算法的平均迭代次數(shù)。從圖2可知，在稀疏度小于50時(shí)，CGIHT算法的迭代次數(shù)明顯高于其他對(duì)比算法，這是因?yàn)镃GIHT 算法在迭代過(guò)程中更新系數(shù)時(shí)沒(méi)有精確估計(jì)，導(dǎo)致其需要較多迭代次數(shù)才能達(dá)到較高的精度。HGHTP 算法的迭代次數(shù)比GraSP 算法和BCGIHT算法稍少，這意味著HGHTP算法中采用梯度和共軛梯度混合支撐集選擇的策略起到了加速的作用。

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

圖2 不同稀疏度下迭代次數(shù)對(duì)比Fig. 2 Iteration number comparison with different sparsities

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

3.2 二維圖像重構(gòu)實(shí)驗(yàn)

本實(shí)驗(yàn)采用大小為256×256 像素的標(biāo)準(zhǔn)測(cè)試圖片“Lena”來(lái)驗(yàn)證本文提出算法的圖像重構(gòu)性能。實(shí)驗(yàn)過(guò)程中對(duì)原圖像進(jìn)行小波變換，取稀疏度為s=M4= 32。觀測(cè)矩陣選用大小為M×N的隨機(jī)高斯矩陣，定義采樣率為r=M N。本實(shí)驗(yàn)中所有的算法均獨(dú)立測(cè)試200 次，以平均值作為實(shí)驗(yàn)結(jié)果。圖像的重構(gòu)質(zhì)量用峰值信噪比（Peak Signal-to-Noise Ratio，PSNR）來(lái)評(píng)估，其計(jì)算公式為:

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

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

圖4 不同算法的重構(gòu)結(jié)果Fig. 4 Reconstruction results of different algorithms

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

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

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

4 結(jié)語(yǔ)

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