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

付 敏, 王金平

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

付 敏, 王金平*

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

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

稀疏重構(gòu); OMP算法; 回溯

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

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

該解不惟一, 而CS理論: 如果一個(gè)信號(hào)是稀疏的, 那么就可以用具有約束等距性(Restricted Isometry Property, RIP)的測(cè)量矩陣來(lái)觀測(cè)該信號(hào), 然后通過(guò)求解一個(gè)優(yōu)化問(wèn)題就可重構(gòu)原始信號(hào)[1].

由CS理論可知, 恢復(fù)稀疏信號(hào)即求解最優(yōu)化問(wèn)題:

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

正交匹配追蹤算法過(guò)程如下.

循環(huán)執(zhí)行各步驟:

步驟3 由最小二乘得到

由步驟1, OMP算法原子選擇標(biāo)準(zhǔn)是選擇與殘差內(nèi)積絕對(duì)值最大的那個(gè)原子, 即

可得

由結(jié)論2, 發(fā)現(xiàn)殘差與前面已選的原子都是正交的, 這可避免重復(fù)選用原子.

2 主要結(jié)果

本節(jié)主要研究相鄰兩次迭代殘差間的關(guān)系, 從而給出一種等價(jià)的原子選擇標(biāo)準(zhǔn), 迭代結(jié)束后, 加入一種回溯機(jī)制來(lái)處理迭代結(jié)果.

證明 (i)由定義1得

(ii)由定義1及內(nèi)積定義得

(iii)由定義1得

將矩陣分塊得

憲法學(xué)研究要立足于新時(shí)代堅(jiān)持和發(fā)展中國(guó)特色社會(huì)主義的偉大實(shí)踐。積極回應(yīng)社會(huì)發(fā)展中重大的憲法關(guān)切，更加注重原創(chuàng)性和本土性研究，把憲法學(xué)的宏大敘事與具象表達(dá)、研究的開(kāi)放性與自主性結(jié)合起來(lái)。堅(jiān)持中國(guó)特色社會(huì)主義的政治優(yōu)勢(shì)和制度優(yōu)勢(shì)，努力提煉并不斷豐富發(fā)展具有中國(guó)特色和中國(guó)氣派的憲法學(xué)理論體系、概念體系、話語(yǔ)體系，不斷增強(qiáng)中國(guó)憲法學(xué)的解釋力、傳播力和影響力。

進(jìn)一步地,

故有

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

從而有

改進(jìn)的正交匹配追蹤算法如下.

3 總結(jié)

本文利用Cholesky迭代式分解, 得到OMP算法中相鄰兩次迭代殘差間的關(guān)系, 可減少計(jì)算殘差的次數(shù). 迭代結(jié)束后, 通過(guò)引入回溯機(jī)制來(lái)對(duì)原子進(jìn)行二次篩選, 從而實(shí)現(xiàn)精確重構(gòu).

[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] 劉學(xué)文, 肖嵩, 王玲, 等. 迭代預(yù)測(cè)正交匹配追蹤算法[J]. 信號(hào)處理, 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.

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

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

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

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

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