共軛梯度子空間基追蹤算法及其相關結果

郝嘉駿, 張茜雯, 王金平

共軛梯度子空間基追蹤算法及其相關結果

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

（寧波大學 數學與統計學院, 浙江 寧波 315211）

壓縮感知可以在低于Nyqiust采樣率條件下實現稀疏信號的精確恢復. 重構算法是壓縮感知的主要研究內容之一. 本文基于子空間基追蹤算法的回溯思想與共軛梯度法, 提出了共軛梯度子空間基追蹤算法. 通過仿真實驗驗證了算法的有效性, 并討論了該算法利用幾種常見測量矩陣對稀疏信號的重構效果. 結果顯示, 當測量矩陣為部分Fourier矩陣時, 該算法具有最優的重構效果.

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

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

壓縮感知理論經過十幾年的快速發展, 已產生了許多具有不同復雜性和性能特征的有效算法, 其中貪婪算法因其結構簡單、易于實現而得到廣泛關注. 人們提出了很多改進算法, 例如正交匹配追蹤(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]. 近幾年來, 人們開始關注將共軛梯度法與貪婪算法結合. 2015年Blanchard等[10]提出了共軛梯度硬閾值(Conjugate Gradient Iterative Hard Thresholding, CGIHT)算法. 在此之后又相繼出現了共軛硬閾值基追蹤(Conjugate Gradient Hard Thresholding Pursuit, CGHTP)算法[11]與改進的共軛硬閾值基追蹤(Modified Conjugate Gradient Hard Thresholding Pursuit, CCGHTP)算法[12]. 受此啟發, 本文將共軛梯度法與SP算法相結合, 對SP算法加以改進得到相關結果.

1 預備知識

1.1 投影與殘差

1.2 SP算法

初始化:

迭代: 在第次迭代中, 作

1.3 測量矩陣的限制等距性質

這等價于

1.4 常見的測量矩陣

1.4.1 Gauss隨機測量矩陣

1.4.2 Bernoulli隨機測量矩陣

1.4.3部分Fourier矩陣

1.4.4部分Hadamard矩陣

1.4.5稀疏隨機測量矩陣

1.4.6 Toeplitz矩陣和循環矩陣

Toeplitz矩陣通過行向量循環位移生成. 因為矩陣容易實現, 所以應用前景較好. 一般形式為

循環矩陣則是Toeplitz矩陣的一種特殊形式, 可表示為

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

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

CGSP算法:

迭代: 若迭代次數小于等于2次,

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

(6)給出最佳步長

3 仿真實驗

3.1 稀疏信號單次恢復實驗

圖1 不同測量矩陣單次恢復結果

通過不同測量矩陣恢復該稀疏信號時, 對應的誤差值見表1.

表1 不同測量矩陣恢復誤差

由圖1與表1可以看出, 在實驗所設條件下, CGSP算法以7種常用矩陣為測量矩陣時均可以實現稀疏信號的精確恢復, 且測量矩陣為Fourier矩陣時重構誤差最小, 測量矩陣為隨機稀疏測量矩陣時誤差最大. 實驗初步證明本文所提算法可以對滿足要求的稀疏信號進行精確恢復.

3.2 無噪聲稀疏信號測量矩陣效果實驗

本實驗為特定情況下測試算法對稀疏信號的恢復效果, 共分為3部分.

圖2 不同稀疏度的恢復成功率

表2 4種測量矩陣實現穩定恢復的稀疏度區間

圖3 不同測量數的恢復成功率

表3 4種測量矩陣穩定重構最小測量數

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

(c)在對應的稀疏度和測量矩陣行數對稀疏信號進行1000次恢復實驗, 取每次實驗所得誤差值的算術平均值與恢復時間的算術平均值.

實驗結果見表4.

表4 4種測量矩陣的恢復參數

圖4 4種測量矩陣的恢復誤差與時間

4 結論

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

[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] 李小波. 基于壓縮感知的測量矩陣研究[D]. 北京: 北京交通大學, 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.

寧波大學學報（理工版）網址: http://journallg. nbu. edu. cn/

國家自然科學基金（62071262）.

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

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

（責任編輯 韓 超）