正交匹配追蹤算法的迭代殘差重建方法

付 敏, 王金平

正交匹配追蹤算法的迭代殘差重建方法

付 敏, 王金平*

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

正交匹配追蹤(Orthogonal Matching Pursuit, OMP)算法是一種重要的壓縮感知重構算法. OMP算法在每次迭代中選擇與當前殘差最相關的原子. 針對每次迭代需要重新計算殘差的問題, 本文考慮偶數次迭代下殘差未知的情況. 首先, 研究了奇數次迭代的殘差與下一次迭代的殘差之間的關系, 得到了一種偶數次迭代時選擇原子的標準. 然后, 引入一種回溯機制來處理前面所得的迭代結果, 這種機制通過剔除其中多余的原子來實現精確重建. 據此, 提出了可減少計算殘差的改進型正交匹配追蹤算法.

稀疏重構; OMP算法; 回溯

壓縮感知(Compressed Sensing, CS)理論[1]作為一種新的信號采樣理論突破了傳統Nyquist采樣定理的限制, 它充分利用信號的稀疏性, 將高維信號沒有損失地壓縮采樣成低維信號, 最后通過重構算法精確或高概率地重建原始信號. CS理論主要涉及稀疏表示、測量矩陣、重構算法等3個核心方面. 其中, 重構算法是將CS理論推向實用化的關鍵之一. 目前, 重構算法主要分為3類: (1)基追蹤算法, (2)貪婪算法, (3)組合算法. 這些算法中, 貪婪算法因其結構簡單易實現的優勢而得到了廣泛應用. OMP算法[2]是一種常用的壓縮感知貪婪算法. 以OMP算法為原型, 研究者們提出了很多改進算法, 例如對原子正則化的正則化正交匹配追蹤(Regularized OMP, ROMP)算法[3], 使用回溯思想的壓縮采樣匹配追蹤(Compressive Sampling MP, CoSaMP)算法[4]和子空間追蹤(Subspace Pursuit, SP)算法[5], 采用門限閾值的分段正交匹配追蹤(Stage- wise OMP, StOMP)算法[6], 還有稀疏度自適應的自適應匹配追蹤(Sparsity Adaptive MP, SAMP)算法[7]以及利用統計學方法來進行迭代預測的迭代預測匹配追蹤(Iterative Forecast OMP, IFOMP)算法[8]. 在前人研究的基礎上, 本文對OMP算法加以改進, 得到相關結果.

1 預備知識

該解不惟一, 而CS理論: 如果一個信號是稀疏的, 那么就可以用具有約束等距性(Restricted Isometry Property, RIP)的測量矩陣來觀測該信號, 然后通過求解一個優化問題就可重構原始信號[1].

由CS理論可知, 恢復稀疏信號即求解最優化問題:

OMP算法的基本思想是在每次迭代過程中, 選擇與殘差最相關的原子, 并將測量信號正交投影到已選原子集合生成的超平面上, 剩余部分作為新的殘差, 繼續迭代, 直到達到設置的迭代次數為止. OMP算法的階模型為

正交匹配追蹤算法過程如下.

循環執行各步驟:

步驟3 由最小二乘得到

由步驟1, OMP算法原子選擇標準是選擇與殘差內積絕對值最大的那個原子, 即

可得

由結論2, 發現殘差與前面已選的原子都是正交的, 這可避免重復選用原子.

2 主要結果

本節主要研究相鄰兩次迭代殘差間的關系, 從而給出一種等價的原子選擇標準, 迭代結束后, 加入一種回溯機制來處理迭代結果.

證明 (i)由定義1得

(ii)由定義1及內積定義得

(iii)由定義1得

將矩陣分塊得

憲法學研究要立足于新時代堅持和發展中國特色社會主義的偉大實踐。積極回應社會發展中重大的憲法關切，更加注重原創性和本土性研究，把憲法學的宏大敘事與具象表達、研究的開放性與自主性結合起來。堅持中國特色社會主義的政治優勢和制度優勢，努力提煉并不斷豐富發展具有中國特色和中國氣派的憲法學理論體系、概念體系、話語體系，不斷增強中國憲法學的解釋力、傳播力和影響力。

進一步地,

故有

將式(7)代入式(6), 得到

從而有

改進的正交匹配追蹤算法如下.

3 總結

本文利用Cholesky迭代式分解, 得到OMP算法中相鄰兩次迭代殘差間的關系, 可減少計算殘差的次數. 迭代結束后, 通過引入回溯機制來對原子進行二次篩選, 從而實現精確重構.

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

[2] Tropp 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.

[3] 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.

[4] 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.

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

[6] 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.

[7] Do T T, Gan L, Nguyen N, et al. Sparsity adaptive matching pursuit algorithm for practical compressed sensing[C]. Asilonar Conference on Signals, Systems, and Computers, 2008:581-587.

[8] 劉學文, 肖嵩, 王玲, 等. 迭代預測正交匹配追蹤算法[J]. 信號處理, 2017, 33(2):178-184.

[9] Baraniuk R G. Compressive sensing[J]. IEEE Signal Processing Magazine, 2007, 24(4):118-121.

An iterative residual reconstruction method of the orthogonal matching pursuit algorithm

FU Min, WANG Jinping*

( school of Mathematics and Statistics, Ningbo University, Ningbo 315211, China )

Orthogonal Matching Pursuit (OMP) is an important compressed sensing reconstruction algorithm. The OMP algorithm selects the atoms which are most associated to the current residual in each iteration. For the problem of recalculating the residual in each iteration, we consider the case where the residual of even number iterations is unknown. First, we study the relationship between the residuals of odd number iterations and the residuals of the next iteration followed by obtaining a benchmark for selecting atoms in even number iterations. Then we introduce a backtracking mechanism to process the results of previous iterations. The mechanism achieves the precise reconstruction by removing the extra atoms. An improved orthogonal matching pursuit algorithm is thus presented in this study.

sparse reconstruction; OMP algorithm; backtracking

O177.92

A

1001-5132（2021）01-0050-05

2020?06?01.

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

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

付敏（1997－）, 女, 安徽合肥人, 在讀碩士研究生, 主要研究方向: 積分變換與圖像處理. E-mail: 2818391447@qq.com

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

（責任編輯 韓 超）