共軛梯度子空間基追蹤算法及其相關(guān)結(jié)果

郝嘉駿, 張茜雯, 王金平

共軛梯度子空間基追蹤算法及其相關(guān)結(jié)果

郝嘉駿, 張茜雯, 王金平*

（寧波大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院, 浙江 寧波 315211）

壓縮感知可以在低于Nyqiust采樣率條件下實(shí)現(xiàn)稀疏信號(hào)的精確恢復(fù). 重構(gòu)算法是壓縮感知的主要研究內(nèi)容之一. 本文基于子空間基追蹤算法的回溯思想與共軛梯度法, 提出了共軛梯度子空間基追蹤算法. 通過仿真實(shí)驗(yàn)驗(yàn)證了算法的有效性, 并討論了該算法利用幾種常見測(cè)量矩陣對(duì)稀疏信號(hào)的重構(gòu)效果. 結(jié)果顯示, 當(dāng)測(cè)量矩陣為部分Fourier矩陣時(shí), 該算法具有最優(yōu)的重構(gòu)效果.

壓縮感知; 測(cè)量矩陣; 共軛梯度; 迭代算法

壓縮感知理論由Donoho和Candes等在2004年首次提出, 目前壓縮感知理論的主要研究方向分為信號(hào)稀疏性、測(cè)量矩陣和恢復(fù)算法3種. 有別于傳統(tǒng)的Nyqiust采樣定理[1], 壓縮感知理論指出, 若一個(gè)信號(hào)是稀疏信號(hào)或者可以在某個(gè)變換域上表現(xiàn)為稀疏信號(hào), 那么可以通過一個(gè)與變換基不相關(guān)的矩陣將此信號(hào)投影到低維空間上, 且此投影過程不會(huì)損失原信號(hào)中的信息, 因此通過該投影可以精確地重構(gòu)出原信號(hào)[2]. 壓縮感知中的采樣過程相對(duì)簡單, 但恢復(fù)非常復(fù)雜, 所以對(duì)于恢復(fù)算法的研究是壓縮感知中相當(dāng)重要的一方面, 而對(duì)于測(cè)量矩陣的討論不可避免地成為了重建算法的主要內(nèi)容之一. 壓縮感知的關(guān)鍵在于可以從線性測(cè)量中獲取信息, 而無需從先前的測(cè)量中學(xué)習(xí).

壓縮感知理論經(jīng)過十幾年的快速發(fā)展, 已產(chǎn)生了許多具有不同復(fù)雜性和性能特征的有效算法, 其中貪婪算法因其結(jié)構(gòu)簡單、易于實(shí)現(xiàn)而得到廣泛關(guān)注. 人們提出了很多改進(jìn)算法, 例如正交匹配追蹤(Orthogonal Matching Pursuit, OMP)算法[3]、原子正則化正交匹配追蹤(Regularized OMP, ROMP)算法[4]、壓縮采樣匹配追蹤(Compressive Sampling MP, CoSaMP)算法[5]、子空間基追蹤(subspace pursuit, SP)算法[6]、分段正交匹配追蹤(Stagewise OMP, StOMP)算法[7]、迭代硬閾值(Iterative Hard Thresholding, IHT)算法[8]以及硬閾值基追蹤(Hard Thresholding Pursuit, HTP)算法[9]. 近幾年來, 人們開始關(guān)注將共軛梯度法與貪婪算法結(jié)合. 2015年Blanchard等[10]提出了共軛梯度硬閾值(Conjugate Gradient Iterative Hard Thresholding, CGIHT)算法. 在此之后又相繼出現(xiàn)了共軛硬閾值基追蹤(Conjugate Gradient Hard Thresholding Pursuit, CGHTP)算法[11]與改進(jìn)的共軛硬閾值基追蹤(Modified Conjugate Gradient Hard Thresholding Pursuit, CCGHTP)算法[12]. 受此啟發(fā), 本文將共軛梯度法與SP算法相結(jié)合, 對(duì)SP算法加以改進(jìn)得到相關(guān)結(jié)果.

1 預(yù)備知識(shí)

1.1 投影與殘差

1.2 SP算法

初始化:

迭代: 在第次迭代中, 作

1.3 測(cè)量矩陣的限制等距性質(zhì)

這等價(jià)于

1.4 常見的測(cè)量矩陣

1.4.1 Gauss隨機(jī)測(cè)量矩陣

1.4.2 Bernoulli隨機(jī)測(cè)量矩陣

1.4.3部分Fourier矩陣

1.4.4部分Hadamard矩陣

1.4.5稀疏隨機(jī)測(cè)量矩陣

1.4.6 Toeplitz矩陣和循環(huán)矩陣

Toeplitz矩陣通過行向量循環(huán)位移生成. 因?yàn)榫仃嚾菀讓?shí)現(xiàn), 所以應(yīng)用前景較好. 一般形式為

循環(huán)矩陣則是Toeplitz矩陣的一種特殊形式, 可表示為

2 共軛梯度子空間基追蹤算法

共軛梯度法最早是由Hestenes和Stiefle提出來的, 在此基礎(chǔ)上, Fletcher[18]首先提出了解非線性最優(yōu)化問題的共軛梯度法. 共軛梯度法是介于最速下降法與牛頓法之間的一種方法, 它僅需要利用一階導(dǎo)數(shù)信息, 既克服了最速下降法收斂慢的缺點(diǎn), 又避免了牛頓法需要存儲(chǔ)和計(jì)算Hesse矩陣并求逆的缺點(diǎn). 共軛梯度法不僅是解決大型線性方程組最有用的方法之一, 也是解大型非線性最優(yōu)化最有效的算法之一. 在各種優(yōu)化算法中, 共軛梯度法是非常重要的一種, 其優(yōu)點(diǎn)是所需存儲(chǔ)量小、具有步收斂性、穩(wěn)定性高, 而且不需要任何外來參數(shù).

CGSP算法:

迭代: 若迭代次數(shù)小于等于2次,

(4)若支撐集未發(fā)生變化,

(6)給出最佳步長

3 仿真實(shí)驗(yàn)

3.1 稀疏信號(hào)單次恢復(fù)實(shí)驗(yàn)

圖1 不同測(cè)量矩陣單次恢復(fù)結(jié)果

通過不同測(cè)量矩陣恢復(fù)該稀疏信號(hào)時(shí), 對(duì)應(yīng)的誤差值見表1.

表1 不同測(cè)量矩陣恢復(fù)誤差

由圖1與表1可以看出, 在實(shí)驗(yàn)所設(shè)條件下, CGSP算法以7種常用矩陣為測(cè)量矩陣時(shí)均可以實(shí)現(xiàn)稀疏信號(hào)的精確恢復(fù), 且測(cè)量矩陣為Fourier矩陣時(shí)重構(gòu)誤差最小, 測(cè)量矩陣為隨機(jī)稀疏測(cè)量矩陣時(shí)誤差最大. 實(shí)驗(yàn)初步證明本文所提算法可以對(duì)滿足要求的稀疏信號(hào)進(jìn)行精確恢復(fù).

3.2 無噪聲稀疏信號(hào)測(cè)量矩陣效果實(shí)驗(yàn)

本實(shí)驗(yàn)為特定情況下測(cè)試算法對(duì)稀疏信號(hào)的恢復(fù)效果, 共分為3部分.

圖2 不同稀疏度的恢復(fù)成功率

表2 4種測(cè)量矩陣實(shí)現(xiàn)穩(wěn)定恢復(fù)的稀疏度區(qū)間

圖3 不同測(cè)量數(shù)的恢復(fù)成功率

表3 4種測(cè)量矩陣穩(wěn)定重構(gòu)最小測(cè)量數(shù)

(b)稀疏度滿足首項(xiàng)為1, 公差為5, 末項(xiàng)為矩陣行數(shù)的等差數(shù)列;

(c)在對(duì)應(yīng)的稀疏度和測(cè)量矩陣行數(shù)對(duì)稀疏信號(hào)進(jìn)行1000次恢復(fù)實(shí)驗(yàn), 取每次實(shí)驗(yàn)所得誤差值的算術(shù)平均值與恢復(fù)時(shí)間的算術(shù)平均值.

實(shí)驗(yàn)結(jié)果見表4.

表4 4種測(cè)量矩陣的恢復(fù)參數(shù)

圖4 4種測(cè)量矩陣的恢復(fù)誤差與時(shí)間

4 結(jié)論

本文通過將SP算法與共軛梯度法相結(jié)合對(duì)SP算法加以改進(jìn)提出了CGSP算法, 并使用幾種常見的測(cè)量矩陣對(duì)此算法的有效性加以驗(yàn)證, 實(shí)驗(yàn)證明此算法確實(shí)可行. 在此基礎(chǔ)上, 本文設(shè)計(jì)實(shí)驗(yàn)討論了算法在無噪聲條件下應(yīng)用各測(cè)量矩陣時(shí)對(duì)稀疏信號(hào)的重構(gòu)效果. 結(jié)果表明, 算法在測(cè)量矩陣為部分Fourier矩陣時(shí)效果最好, 表現(xiàn)在兩方面: 首先, 以稀疏度為變量, 算法在部分Fourier矩陣下所需測(cè)量數(shù)最少; 其次, 以測(cè)量數(shù)為變量, 算法能夠重構(gòu)的稀疏度區(qū)間最廣. 限于篇幅, 本文只選取了較為常見的幾種測(cè)量矩陣測(cè)試并給出了仿真結(jié)果, 其他的測(cè)量矩陣均可以同上述方法討論. 此外, 本文只給出了算法在不同測(cè)量矩陣下的相關(guān)實(shí)驗(yàn)結(jié)果, 并未對(duì)算法進(jìn)行理論分析, 這是下一階段研究的目標(biāo).

[1] Jerri A J. The Shannon sampling theorem—Its various extensions and applications: A tutorial review[J]. Proceedings of the IEEE, 1977, 65(11):1565-1596.

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

[3] Trop J A, Gilbert A C. Signal recovery from random measurements via orthogonal matching pursuit[J]. IEEE Transactions on Information Theory, 2007, 53(12):4655- 4666.

[4] Needell D, Vershynin R. Signal recovery from incomplete and inaccurate measurements via regularized orthogonal matching pursuit[J]. IEEE Journal of Selected Topics in Signal Processing, 2010, 4(2):310-316.

[5] Needell D, Tropp J A. CoSaMP: Iterative signal recovery from incomplete and inaccurate samples[J]. Applied and Computational Harmonic Analysis, 2009, 26(3):301-321.

[6] Dai W, Milenkovic O. Subspace pursuit for compressive sensing signal reconstruction[J]. IEEE Transactions on Information Theory, 2009, 55(5):2230-2249.

[7] Donoho D L, Tsaig Y, Drori I, et al. Sparse solution of underdetermined systems of linear equations by stagewise orthogonal matching pursuit[J]. IEEE Transactions on Information Theory, 2012, 58(2):1094-1121.

[8] Blumensath T, Davies M E. Iterative hard thresholding for compressed sensing[J]. Applied and computational harmonic analysis, 2009, 27(3):265-274.

[9] Foucart S. Hard thresholding pursuit: an algorithm for compressive sensing[J]. SIAM Journal on Numerical Analysis, 2011, 49(6):2543-2563.

[10] Blanchard J D, Tanner J, Wei K. CGIHT: conjugate gradient iterative hard thresholding for compressed sensing and matrix completion[J]. Information and Inference: A Journal of the IMA, 2015, 4(4):289-327.

[11] Zhang Y, Huang Y, Li H, et al. Conjugate gradient hard thresholding pursuit algorithm for sparse signal recovery [J]. Algorithms, 2019, 12(2):36.

[12] Zhu Z, Ma J, Zhang B. A new conjugate gradient hard thresholding pursuit algorithm for sparse signal recovery [J]. Computational and Applied Mathematics, 2020, 39(4): 1-20.

[13] Candès E J, Romberg J K, Tao T. Stable signal recovery from incomplete and inaccurate measurements[J]. Communications on Pure and Applied Mathematics, 2006, 59(8):1207-1223.

[14] Tur R, Eldar Y C, Friedman Z. Innovation rate sampling of pulse streams with application to ultrasound imaging [J]. IEEE Transactions on Signal Processing, 2011, 59(4): 1827-1842.

[15] 李小波. 基于壓縮感知的測(cè)量矩陣研究[D]. 北京: 北京交通大學(xué), 2010.

[16] Gilbert A, Indyk P. Sparse recovery using sparse matrices [J]. Proceedings of the IEEE, 2010, 98(6):937-947.

[17] Bajwa W U, Haupt J D, Raz G M, et al. Toeplitz- structured compressed sensing matrices[C]//2007 IEEE/ SP 14th Workshop on Statistical Signal Processing, IEEE, 2007:294-298.

[18] Fletcher R. Conjugate gradient methods for indefinite systems[M]//Watson G A. Numerical Analysis. Berlin: Springer, 1976:73-89.

Conjugate gradient subspace pursuit algorithm and related results

HAO Jiajun, ZHANG Xiwen, WANG Jinping*

( Schoolof Mathematics and Statistics, Ningbo University, Ningbo 315211, China )

Compressed sensing can accurately recover sparse signals below Nyquist sampling rate. Reconstruction algorithm is one of the main research contents of compressed sensing. Based on the backtracking notion of subspace pursuit algorithm and conjugate gradient method, a conjugate gradient subspace pursuit algorithm is proposed in this paper. The effectiveness of the algorithm is verified through simulations, and the reconstruction effect of the algorithm on sparse signals is discussed using several common measurement matrices. The results show that the algorithm has the best reconstruction effect when the measurement matrix is a partial Fourier matrix.

compressed sensing; measurement matrix; conjugate gradient; iterative algorithm

O177.92

A

1001-5132（2022）01-0098-07

2021?09?05.

寧波大學(xué)學(xué)報(bào)（理工版）網(wǎng)址: http://journallg. nbu. edu. cn/

國家自然科學(xué)基金（62071262）.

郝嘉駿（1992－）, 男, 山西長治人, 在讀碩士研究生, 主要研究方向: 積分變換與圖像處理. E-mail: 825821801@qq.com

王金平（1962－）, 男, 湖北武漢人, 教授, 主要研究方向: 積分變換與圖像處理. E-mail: wangjinping@nbu.edu.cn

（責(zé)任編輯 韓 超）