一種適用于TDOMP算法的測量矩陣優化方法

趙 娟白 霞

（北京理工大學信息與電子學院 北京 100081）

一種適用于TDOMP算法的測量矩陣優化方法

趙 娟*白 霞

（北京理工大學信息與電子學院 北京 100081）

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

壓縮感知；測量矩陣；Gram矩陣；互相關

引用格式：趙娟， 白霞. 一種適用于TDOMP算法的測量矩陣優化方法［J］. 雷達學報， 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］是一種新的信號獲取與處理的理論框架，其基本思想是利用信號的稀疏性或者可壓縮性，在信號采樣的同時進行壓縮，能以遠低于奈奎斯特采樣定理所需的測量值精確重建原始信號，廣泛應用于雷達、通信、核磁成像等領域［4-6］。

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

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

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

2 用于TDOMP的測量矩陣優化算法

2.1TDOMP算法

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

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

表 1 TDOMP算法Tab. 1 TDOMP algorithm

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

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

2.2基于交替投影的測量矩陣優化算法

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

因此，當測量矩陣可以設計時，首先基于表3的交替投影法構造出測量矩陣Φopt和匹配矩陣D，此時觀測方程為yopt=ΦoptΨs，然后由Θ=ΦoptΨ和D，利用TDOMP算法重構稀疏信號。

表 2 構造低相關性的匹配矩陣Tab. 2 Construction of matching matrix with low cross-coherence

表 3 基于交替投影的測量矩陣優化算法Tab. 3 Measurement matrix optimization method based on alternative projection

3 仿真實驗

本節對所提的針對TDOMP重構算法的測量矩陣優化方法進行仿真，分析測量矩陣優化前后對重構性能的影響。

3.11維稀疏信號仿真實驗

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

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

表 4 仿真說明Tab. 4 Simulation description

仿真實驗1：稀疏信號長度n=128，稀疏基Ψ為128×128，測量矩陣Φ為64×128。給定測量數m=64的情況下，觀察不同測量矩陣下的準確重構概率和重構誤差隨信號稀疏度k變化的情況。每個稀疏度下，獨立重復500次仿真實驗。

稀疏基為高斯隨機矩陣，稀疏系數為高斯稀疏信號和0-1稀疏信號的結果如圖1和圖2所示。可以看出，在測量數m固定不變的情況下，隨著稀疏度k的增加，信號的準確重構概率降低，重構誤差增大。采用所提優化的測量矩陣的TDOMP算法的重構效果最好，但優化測量矩陣對TDOMP算法重構性能的提高程度不如優化測量矩陣對OMP算法重構性能的提高程度。

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

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

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

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

稀疏基采用DCT矩陣，稀疏系數為高斯稀疏信號和0-1稀疏信號的結果如圖3和圖4所示?？梢钥闯?，采用優化測量矩陣的TDOMP算法的重構效果最好。與稀疏系數為0-1稀疏信號的情況相比，優化后的測量矩陣對高斯稀疏系數的重構效果提高得更為顯著。

仿真實驗2：稀疏信號長度n=128，稀疏基Ψ為128×128，采用高斯隨機矩陣和DCT矩陣，稀疏系數為高斯稀疏信號和0-1稀疏信號。給定稀疏度k，觀察不同測量矩陣下的準確重構概率和重構誤差隨信號測量數m變化的情況。測量數m從64到96以步長4變化，每個測量數下，獨立重復500次仿真實驗。固定稀疏度k，當稀疏系數是高斯時，k=30；當稀疏系數為0-1信號時，k=19。

稀疏矩陣采用高斯隨機矩陣，稀疏系數為高斯稀疏信號和0-1稀疏信號的結果如圖5和圖6所示。稀疏矩陣采用DCT矩陣，稀疏系數為高斯稀疏信號和0-1稀疏信號的結果如圖7和圖8所示?？梢钥闯觯谙∈瓒萲固定不變時，隨著測量數m的增加，信號的準確重構概率增加，重構誤差下降。實驗結果表明，采用優化的測量矩陣的TDOMP算法的重構效果最好。

3.22維圖像信號仿真實驗

為了進一步驗證測量矩陣優化算法的性能，本節將對2維圖像信號進行重構實驗。源圖像采用256×256的Lena圖像，如圖9所示。稀疏基采用DCT基。重構效果采用PSNR （Power Signal-to-Noise Ration）值來進行評價，其計算公式為：當測量值為140（即壓縮比m/n=0.55）時，給出4種情況下的仿真結果，如圖10所示。

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

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

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

圖 8 DCT稀疏基下OMP和TDOMP算法重構0-1稀疏系數的性能比較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 在不同測量矩陣下OMP和TDOMP算法的重建圖像Fig. 10 Reconstructed images by using OMP and TDOMP with different measurement matrix

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

4 結束語

本文研究了針對特定重構算法TDOMP的測量矩陣優化方法。TDOMP算法通過構造與感知矩陣相關性低的匹配矩陣來提高原子識別的準確性。所提測量矩陣優化方法首先利用交替投影法構造相關性低的感知矩陣和匹配矩陣，然后基于其中的新感知矩陣利用最小二乘實現測量矩陣的優化。最后，通過對1維稀疏信號和2維圖像的仿真實驗，驗證了該優化測量矩陣顯著提高了TDOMP算法的重構性能。

［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-），女，四川人，北京理工大學信息與電子學院副教授，博士，主要研究領域為壓縮感知理論及應用。

E-mail： juanzhao@bit.edu.cn

白 霞（1978-），女，遼寧人，北京理工大學信息與電子學院講師，博士，主要研究領域為SAR信號處理。

E-mail： bai@bit.edu.cn

2015-12-26；改回日期：2016-01-24；網絡出版：2016-02-17

趙娟 juanzhao@bit.edu.cn

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