一種適用于TDOMP算法的測(cè)量矩陣優(yōu)化方法

趙 娟白 霞

（北京理工大學(xué)信息與電子學(xué)院 北京 100081）

一種適用于TDOMP算法的測(cè)量矩陣優(yōu)化方法

趙 娟*白 霞

（北京理工大學(xué)信息與電子學(xué)院 北京 100081）

測(cè)量矩陣的優(yōu)化設(shè)計(jì)有利于提高壓縮感知中信號(hào)的重構(gòu)性能。該文研究了適用于TDOMP （Two Dictionaries OMP）重構(gòu)算法的測(cè)量矩陣優(yōu)化方法。TDOMP算法是一種改進(jìn)的OMP算法，該算法使用與感知矩陣互相關(guān)性低的匹配矩陣來辨識(shí)正確的感知矩陣原子。所提方法利用交替投影的思想來優(yōu)化測(cè)量矩陣從而得到相關(guān)性低的感知矩陣和匹配矩陣，然后用于TDOMP算法來提高信號(hào)的重建性能。仿真實(shí)驗(yàn)驗(yàn)證了所提方法的有效性。

壓縮感知；測(cè)量矩陣；Gram矩陣；互相關(guān)

引用格式：趙娟， 白霞. 一種適用于TDOMP算法的測(cè)量矩陣優(yōu)化方法［J］. 雷達(dá)學(xué)報(bào)， 2016， 5（1）： 8-15. DOI：10.12000/JR15131.

Reference format： Zhao Juan and Bai Xia. Measurement matrix optimization method for TDOMP algorithm［J］. Journal of Radars， 2016， 5（1）： 8-15. DOI： 10.12000/JR15131.

1 引言

壓縮感知（Compressed Sensing， CS）［1-3］是一種新的信號(hào)獲取與處理的理論框架，其基本思想是利用信號(hào)的稀疏性或者可壓縮性，在信號(hào)采樣的同時(shí)進(jìn)行壓縮，能以遠(yuǎn)低于奈奎斯特采樣定理所需的測(cè)量值精確重建原始信號(hào)，廣泛應(yīng)用于雷達(dá)、通信、核磁成像等領(lǐng)域［4-6］。

壓縮感知理論包括3個(gè)方面：信號(hào)的稀疏表征、測(cè)量矩陣的設(shè)計(jì)以及重構(gòu)算法。假設(shè)信號(hào)在某個(gè)基下能稀疏表征，即x=Ψs，其中是稀疏表征矩陣，s中只有k個(gè)非零元素，且k＜＜n。設(shè)計(jì)測(cè)量矩陣對(duì)信號(hào)x進(jìn)行線性測(cè)量，得到y(tǒng)=Φx，其中） 為測(cè)量矩陣。由于m＜n，由y重建x是病態(tài)問題。利用信號(hào)x的稀疏性，可以通過求解l0范數(shù)最小化問題來恢復(fù)原始信號(hào)，即其中l(wèi)0范數(shù)表示向量中的非零元素的個(gè)數(shù)，矩陣稱為感知矩陣。對(duì)于重構(gòu)算法，主要有基于凸優(yōu)化的l1范數(shù)最小化算法（比如基追蹤算法（Basis Pursuit， BP）［7］）和貪婪類算法（比如正交匹配追蹤算法（Orthogonal Matching Pursuit，OMP）［8］）等。

信號(hào)能夠稀疏表征是應(yīng)用壓縮感知的前提，而測(cè)量矩陣的設(shè)計(jì)對(duì)信號(hào)采樣和重構(gòu)環(huán)節(jié)有重要影響。測(cè)量矩陣把信號(hào)從高維空間投影到低維空間，必須保證降維后的低維信號(hào)不丟失原始信號(hào)的信息才能準(zhǔn)確重建原始信號(hào)。這就要求設(shè)計(jì)的測(cè)量矩陣Φ和稀疏矩陣Ψ不相干。文獻(xiàn)［9］中證明了當(dāng)測(cè)量矩陣是高斯隨機(jī)矩陣時(shí)，能夠滿足與大多數(shù)稀疏矩陣不相關(guān)，因而隨機(jī)測(cè)量矩陣常被用在壓縮感知中。近年來很多文獻(xiàn)［10-13］指出，對(duì)隨機(jī)測(cè)量矩陣進(jìn)行優(yōu)化可使其與稀疏矩陣之間的相關(guān)性進(jìn)一步減小，從而提高信號(hào)的重建性能。它們的基本思想是優(yōu)化測(cè)量矩陣使得感知矩陣的不同列（也稱為原子）間的相關(guān)性變得更小，即減小感知矩陣的Gram矩陣的非對(duì)角元素。這些測(cè)量矩陣優(yōu)化方法主要是在稀疏矩陣Ψ確定的情況下來優(yōu)化設(shè)計(jì)測(cè)量矩陣Φ，并未結(jié)合重構(gòu)算法的特點(diǎn)來設(shè)計(jì)測(cè)量矩陣。

在壓縮感知重構(gòu)算法中，貪婪類算法由于計(jì)算復(fù)雜度低而受到廣泛關(guān)注，其主要思想是通過迭代尋找稀疏信號(hào)非零分量相對(duì)應(yīng)的原子，然后根據(jù)這些原子重構(gòu)出原始信號(hào)。OMP是經(jīng)典的貪婪算法，其重構(gòu)性能與感知矩陣的相關(guān)系數(shù)有關(guān)，感知矩陣的相關(guān)性越低，越能準(zhǔn)確識(shí)別正確的原子［8］。因此，文獻(xiàn)［14］提出一種改進(jìn)的OMP算法，本文稱之為雙字典正交匹配追蹤算法（Two Dictionaries OMP， TDOMP），該算法通過引入一個(gè)新矩陣D（稱為匹配矩陣）來識(shí)別原子，并且匹配矩陣和感知矩陣之間具有更低的相關(guān)性，從而提高原子識(shí)別的準(zhǔn)確性。本文主要針對(duì)TDOMP算法的特點(diǎn)，提出了一種適用于TDOMP算法的測(cè)量矩陣優(yōu)化方法，其主要思想是通過交替投影來優(yōu)化測(cè)量矩陣，使得構(gòu)造的匹配矩陣與感知矩陣具有更小的相關(guān)性，從而進(jìn)一步提高重構(gòu)性能。1維稀疏信號(hào)和2維圖像重構(gòu)實(shí)驗(yàn)驗(yàn)證了所提方法的性能，仿真結(jié)果顯示使用優(yōu)化測(cè)量矩陣的TDOMP算法的性能將明顯提高。

2 用于TDOMP的測(cè)量矩陣優(yōu)化算法

2.1TDOMP算法

TDOMP算法［14］是一種改進(jìn)的OMP算法，它從降低感知矩陣Θ的相關(guān)性的思想出發(fā)，通過構(gòu)造與感知矩陣互相關(guān)性低的匹配矩陣D來辨識(shí)正確的感知矩陣的原子。該算法用到兩個(gè)字典Θ和D，因此稱為雙字典正交匹配追蹤算法。TDOMP算法和OMP算法的區(qū)別在于感知原子階段，OMP算法使用感知矩陣Θ對(duì)原子進(jìn)行識(shí)別，而TDOMP算法使用匹配矩陣D對(duì)原子進(jìn)行辨識(shí)。令感知矩陣Θ的每

給出了TDOMP算法的流程［15］。

表 1 TDOMP算法Tab. 1 TDOMP algorithm

在TDOMP算法中，為了構(gòu)造與感知矩陣Θ相關(guān)性低的匹配矩陣D，其基本思想是使偽Gram矩陣G=DTΘ在Frobenius范數(shù)意義下與理想的Gram矩陣充分接近，即文獻(xiàn)［14］采用交替投影的方法來解決上述問題，從而得到與Θ相關(guān)性低的匹配矩陣D，其具體方法如表2所示。

根據(jù)上述方法，給定感知矩陣Θ就可以得到和Θ相關(guān)性低的矩陣D。已有研究表明，OMP算法識(shí)別原子的能力依賴于感知矩陣自身的相關(guān)系數(shù)，而TDOMP感知原子的能力依賴于感知矩陣和匹配矩陣兩者的相關(guān)系數(shù)。當(dāng)D和Θ的相關(guān)系數(shù)低于Θ自身的相關(guān)系數(shù)時(shí)，TDOMP算法的重構(gòu)性能將好于OMP算法［15］。

2.2基于交替投影的測(cè)量矩陣優(yōu)化算法

本節(jié)主要研究測(cè)量矩陣的優(yōu)化來進(jìn)一步提高TDOMP算法的性能，其基本思想是設(shè)計(jì)測(cè)量矩陣使得偽Gram矩陣G=DTΘ=DTΦΨ在Frobenius范數(shù)意義下與理想的Gram矩陣充分接近。與式（1）不同的是，感知矩陣Θ在優(yōu)化過程中可以變化，從而可以優(yōu)化設(shè)計(jì)測(cè)量矩陣。仍采用交替投影的方法來求得優(yōu)化的測(cè)量矩陣Φ以及與Θ相關(guān)性低的匹配矩陣D，所提算法具體如表3所示。

因此，當(dāng)測(cè)量矩陣可以設(shè)計(jì)時(shí)，首先基于表3的交替投影法構(gòu)造出測(cè)量矩陣Φopt和匹配矩陣D，此時(shí)觀測(cè)方程為yopt=ΦoptΨs，然后由Θ=ΦoptΨ和D，利用TDOMP算法重構(gòu)稀疏信號(hào)。

表 2 構(gòu)造低相關(guān)性的匹配矩陣Tab. 2 Construction of matching matrix with low cross-coherence

表 3 基于交替投影的測(cè)量矩陣優(yōu)化算法Tab. 3 Measurement matrix optimization method based on alternative projection

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

本節(jié)對(duì)所提的針對(duì)TDOMP重構(gòu)算法的測(cè)量矩陣優(yōu)化方法進(jìn)行仿真，分析測(cè)量矩陣優(yōu)化前后對(duì)重構(gòu)性能的影響。

3.11維稀疏信號(hào)仿真實(shí)驗(yàn)

假設(shè)稀疏信號(hào)x=Ψs，稀疏矩陣Ψ為高斯隨機(jī)矩陣或者離散余弦變換（Discrete Cosine Transform，DCT）矩陣；稀疏系數(shù)s為高斯稀疏信號(hào)或者0-1稀疏信號(hào)。對(duì)信號(hào)x采用不同的測(cè)量矩陣進(jìn)行觀測(cè)，然后采用OMP算法和TDOMP算法來重構(gòu)稀疏系數(shù)。下面主要從準(zhǔn)確重構(gòu)概率和重構(gòu)誤差來比較測(cè)量矩陣優(yōu)化前后的重構(gòu)性能。若重構(gòu)的稀疏系數(shù)滿則認(rèn)為準(zhǔn)確重構(gòu)，準(zhǔn)確重構(gòu)概率為準(zhǔn)確重構(gòu)次數(shù)與總重構(gòu)次數(shù)的比值。重■構(gòu)誤差采用均方根誤差，其定義為

仿真中主要比較4種情況：采用Gaussian隨機(jī)陣的OMP算法（用--*表示）、采用Gaussian隨機(jī)陣的TDOMP算法（用--o表示）、采用優(yōu)化測(cè)量矩陣的OMP算法（其中優(yōu)化算法為Duarte［10］所提，用--表示）、采用所提優(yōu)化測(cè)量矩陣的TDOMP算法（稱為Optimized TDOMP，用--☆表示），如表4所示。

表 4 仿真說明Tab. 4 Simulation description

仿真實(shí)驗(yàn)1：稀疏信號(hào)長(zhǎng)度n=128，稀疏基Ψ為128×128，測(cè)量矩陣Φ為64×128。給定測(cè)量數(shù)m=64的情況下，觀察不同測(cè)量矩陣下的準(zhǔn)確重構(gòu)概率和重構(gòu)誤差隨信號(hào)稀疏度k變化的情況。每個(gè)稀疏度下，獨(dú)立重復(fù)500次仿真實(shí)驗(yàn)。

稀疏基為高斯隨機(jī)矩陣，稀疏系數(shù)為高斯稀疏信號(hào)和0-1稀疏信號(hào)的結(jié)果如圖1和圖2所示?？梢钥闯觯跍y(cè)量數(shù)m固定不變的情況下，隨著稀疏度k的增加，信號(hào)的準(zhǔn)確重構(gòu)概率降低，重構(gòu)誤差增大。采用所提優(yōu)化的測(cè)量矩陣的TDOMP算法的重構(gòu)效果最好，但優(yōu)化測(cè)量矩陣對(duì)TDOMP算法重構(gòu)性能的提高程度不如優(yōu)化測(cè)量矩陣對(duì)OMP算法重構(gòu)性能的提高程度。

圖 1 高斯稀疏基下OMP和TDOMP算法重構(gòu)高斯稀疏系數(shù)的性能比較Fig. 1 The performance comparison of recovering Gaussian sparse coefficients by using OMP and TDOMP with Gaussian sparse basis

圖 2 高斯稀疏基下OMP和TDOMP算法重構(gòu)0-1稀疏系數(shù)的性能比較Fig. 2 The performance comparison of recovering 0-1 sparse coefficients by using OMP and TDOMP with Gaussian sparse basis

圖 3 DCT稀疏基下OMP和TDOMP算法重構(gòu)高斯稀疏系數(shù)的性能比較Fig. 3 The performance comparison of recovering Gaussian sparse coefficients by using OMP and TDOMP with DCT sparse basis

圖 4 DCT稀疏基下OMP和TDOMP算法重構(gòu)0-1稀疏系數(shù)的性能比較Fig. 4 The performance comparison of recovering 0-1 sparse coefficients by using OMP and TDOMP with DCT sparse basis

稀疏基采用DCT矩陣，稀疏系數(shù)為高斯稀疏信號(hào)和0-1稀疏信號(hào)的結(jié)果如圖3和圖4所示?？梢钥闯觯捎脙?yōu)化測(cè)量矩陣的TDOMP算法的重構(gòu)效果最好。與稀疏系數(shù)為0-1稀疏信號(hào)的情況相比，優(yōu)化后的測(cè)量矩陣對(duì)高斯稀疏系數(shù)的重構(gòu)效果提高得更為顯著。

仿真實(shí)驗(yàn)2：稀疏信號(hào)長(zhǎng)度n=128，稀疏基Ψ為128×128，采用高斯隨機(jī)矩陣和DCT矩陣，稀疏系數(shù)為高斯稀疏信號(hào)和0-1稀疏信號(hào)。給定稀疏度k，觀察不同測(cè)量矩陣下的準(zhǔn)確重構(gòu)概率和重構(gòu)誤差隨信號(hào)測(cè)量數(shù)m變化的情況。測(cè)量數(shù)m從64到96以步長(zhǎng)4變化，每個(gè)測(cè)量數(shù)下，獨(dú)立重復(fù)500次仿真實(shí)驗(yàn)。固定稀疏度k，當(dāng)稀疏系數(shù)是高斯時(shí)，k=30；當(dāng)稀疏系數(shù)為0-1信號(hào)時(shí)，k=19。

稀疏矩陣采用高斯隨機(jī)矩陣，稀疏系數(shù)為高斯稀疏信號(hào)和0-1稀疏信號(hào)的結(jié)果如圖5和圖6所示。稀疏矩陣采用DCT矩陣，稀疏系數(shù)為高斯稀疏信號(hào)和0-1稀疏信號(hào)的結(jié)果如圖7和圖8所示。可以看出，在稀疏度k固定不變時(shí)，隨著測(cè)量數(shù)m的增加，信號(hào)的準(zhǔn)確重構(gòu)概率增加，重構(gòu)誤差下降。實(shí)驗(yàn)結(jié)果表明，采用優(yōu)化的測(cè)量矩陣的TDOMP算法的重構(gòu)效果最好。

3.22維圖像信號(hào)仿真實(shí)驗(yàn)

為了進(jìn)一步驗(yàn)證測(cè)量矩陣優(yōu)化算法的性能，本節(jié)將對(duì)2維圖像信號(hào)進(jìn)行重構(gòu)實(shí)驗(yàn)。源圖像采用256×256的Lena圖像，如圖9所示。稀疏基采用DCT基。重構(gòu)效果采用PSNR （Power Signal-to-Noise Ration）值來進(jìn)行評(píng)價(jià)，其計(jì)算公式為：當(dāng)測(cè)量值為140（即壓縮比m/n=0.55）時(shí)，給出4種情況下的仿真結(jié)果，如圖10所示。

圖 5 高斯稀疏基下OMP和TDOMP算法重構(gòu)高斯稀疏系數(shù)的性能比較Fig. 5 The performance comparison of recovering Gaussian sparse coefficients by using OMP and TDOMP with Gaussian sparse basis

圖 6 高斯稀疏基下OMP和TDOMP算法重構(gòu)0-1稀疏系數(shù)的性能比較Fig. 6 The performance comparison of recovering 0-1 sparse coefficients by using OMP and TDOMP with Gaussian sparse basis

圖 7 DCT稀疏基下OMP和TDOMP算法重構(gòu)高斯稀疏系數(shù)的性能比較Fig. 7 The performance comparison of recovering Gaussian sparse coefficients by using OMP and TDOMP with DCT sparse basis

圖 8 DCT稀疏基下OMP和TDOMP算法重構(gòu)0-1稀疏系數(shù)的性能比較Fig. 8 The performance comparison of recovering 0-1 sparse coefficients by using OMP and TDOMP with DCT sparse basis

圖 9 原始圖像Fig. 9 Original image

圖 10 在不同測(cè)量矩陣下OMP和TDOMP算法的重建圖像Fig. 10 Reconstructed images by using OMP and TDOMP with different measurement matrix

圖10中，圖10（a）為采用高斯隨機(jī)測(cè)量矩陣下OMP的仿真結(jié)果，圖10（b）為采用高斯隨機(jī)測(cè)量矩陣下TDOMP的仿真結(jié)果，圖10（c）為采用Duarte［10］所提優(yōu)化測(cè)量矩陣下OMP的仿真結(jié)果，圖10（d）為采用本文所提優(yōu)化測(cè)量矩陣下TDOMP的仿真結(jié)果，測(cè)量矩陣優(yōu)化情況下的TDOMP稱為Optimized TDOMP。從圖10可以看出，TDOMP算法對(duì)圖像的重構(gòu)效果好于OMP算法的重構(gòu)能力，而對(duì)于TDOMP算法，測(cè)量矩陣優(yōu)化后對(duì)圖像的重構(gòu)效果好于沒有優(yōu)化的測(cè)量矩陣的重構(gòu)效果。但優(yōu)化測(cè)量矩陣對(duì)TDOMP算法重構(gòu)性能的提高程度不如優(yōu)化測(cè)量矩陣對(duì)OMP算法重構(gòu)性能的提高程度。

4 結(jié)束語

本文研究了針對(duì)特定重構(gòu)算法TDOMP的測(cè)量矩陣優(yōu)化方法。TDOMP算法通過構(gòu)造與感知矩陣相關(guān)性低的匹配矩陣來提高原子識(shí)別的準(zhǔn)確性。所提測(cè)量矩陣優(yōu)化方法首先利用交替投影法構(gòu)造相關(guān)性低的感知矩陣和匹配矩陣，然后基于其中的新感知矩陣?yán)米钚《藢?shí)現(xiàn)測(cè)量矩陣的優(yōu)化。最后，通過對(duì)1維稀疏信號(hào)和2維圖像的仿真實(shí)驗(yàn)，驗(yàn)證了該優(yōu)化測(cè)量矩陣顯著提高了TDOMP算法的重構(gòu)性能。

［1］Donoho D L. Compressed sensing［J］. IEEE Transactions on Information Theory， 2006， 52（4）： 1289-1306.

［2］Candes E J， Romberg J， and Tao T. Robust uncertainty principles： exact signal reconstruction from highly incomplete frequency information［J］. IEEE Transactions on Information Theory， 2006， 52（2）： 489-509.

［3］Tsaig Y and Donoho D L. Extensions of compressed sensing［J］.Signal Processing， 2006， 86（3）： 549-571.

［4］Ender J H G. On compressive sensing applied to radar［J］. Signal Processing， 2010， 90（5）： 1402-1414.

［5］Sharma S K， Patwary M and Abdel-Maguid M. Spectral efficient compressive transmission framework for wireless communication systems［J］. IET Signal Processing， 2013，7（7）： 558-564.

［6］Majumdar A and Ward R K. On the choice of compressed sensing priors and sparsifying transforms for MR image reconstruction： an experimental study［J］. Signal Processing：Image Communication， 2012， 27（9）： 1035-1048.

［7］Kim S， Koh K， Lustig M， et al.. An interior-point method for large scale l1regularized least squares［J］. IEEE Journal of Selected Topics in Signal Processing， 2007， 1（4）： 606-617.

［8］Tropp J A. Greed is good： algorithmic results for sparse approximation［J］. IEEE Transactions on Information Theory， 2004， 50（10）： 2231-2242.

［9］Donoho D L， Elad M， and Temlyakov V N. Stable recovery of sparse overcomplete representations in the presence of noise［J］. IEEE Transactions on Information Theory， 2006，52（1）： 6-18.

［10］Duarte J M and Sapiro G. Learning to sense sparse signals：simultaneous sensing matrix and sparsifying dictionary optimization［J］. IEEE Transactions on Image Processing，2009， 18（7）： 1395-1408.

［11］Abolghasemi V， Ferdowsi S， and Sanei S. A gradient-based alternating minimization approach for optimization of the measurement matrix in compressive sensing［J］. Signal Processing， 2012， 92（4）： 999-1009.

［12］Elad M. Optimized projections for compressed sensing［J］. IEEE Transactions on Signal Processing， 2007， 55（12）：5695-5702.

［13］Xu J， Pi Y， and Cao Z. Optimized projection matrix for compressive sensing［J］. EURASIP Journal on Advances in Signal Processing， 2010： 560349.

［14］Schnass K and Vandergheynst P. Dictionary preconditioning for greedy algorithms［J］. IEEE Transactions on Signal Processing， 2008， 56（5）： 1994-2002.

［15］Zhao Juan， Bai Xia， Bi Shi-he， et al.. Coherence-based analysis of modified orthogonal matching pursuit using sensing dictionary［J］. IET Signal Processing， 2015， 9（3）：218-225.

Measurement Matrix Optimization Method for TDOMP Algorithm

Zhao Juan Bai Xia
（School of Information and Electronics， Beijing Institute of Technology， Beijing 100081， China）

Optimizing the measurement matrix can improve reconstruction performance in compressed sensing. In this study， we study the measurement matrix optimization method regarding its application to the Two Dictionaries Orthogonal Matching Pursuit （TDOMP） algorithm. The TDOMP is a modified OMP， which uses a matching matrix with low cross-coherence to identify the correct atoms of the sensing matrix. The proposed optimization method is based on alternative projection technique to construct the measurement and matching matrices with low cross-coherence to improve the performance of the TDOMP. Experimental results verify the effectiveness of the proposed method.

Compressed Sensing （CS）； Measurement matrix； Gram matrix； Mutual coherence

s： The National Natural Science Foundation of China （61421001， 61331021）， Beijing Higher Education Young Elite Teacher Project （YETP1159）

TN911.7

A

2095-283X（2016）01-0008-08

10.12000/JR15131

趙 娟（1975-），女，四川人，北京理工大學(xué)信息與電子學(xué)院副教授，博士，主要研究領(lǐng)域?yàn)閴嚎s感知理論及應(yīng)用。

E-mail： juanzhao@bit.edu.cn

白 霞（1978-），女，遼寧人，北京理工大學(xué)信息與電子學(xué)院講師，博士，主要研究領(lǐng)域?yàn)镾AR信號(hào)處理。

E-mail： bai@bit.edu.cn

2015-12-26；改回日期：2016-01-24；網(wǎng)絡(luò)出版：2016-02-17

趙娟 juanzhao@bit.edu.cn

國(guó)家自然科學(xué)基金（61421001， 61331021），北京市高等教育青年英才資助課題（YETP1159）