一種梯度交替迭代設(shè)計測量矩陣的方法

王楠楠，汪立新，2

1.杭州電子科技大學(xué)通信工程學(xué)院，杭州品牌 310018

2.通信系統(tǒng)信息控制技術(shù)國家級重點實驗室，浙江嘉興 314001

一種梯度交替迭代設(shè)計測量矩陣的方法

王楠楠1，汪立新1，2

1.杭州電子科技大學(xué)通信工程學(xué)院，杭州品牌 310018

2.通信系統(tǒng)信息控制技術(shù)國家級重點實驗室，浙江嘉興 314001

在壓縮采樣中，測量矩陣應(yīng)該和表達(dá)字典有盡可能小的相干性，隨機(jī)測量矩陣一直被使用是因為其和任何表達(dá)字典都有較小的相干性。提出一種基于梯度迭代最小化方法，作為格拉斯曼框架設(shè)計的一種變體，通過優(yōu)化一個初始的隨機(jī)測量矩陣來得到相干性更小的測量矩陣。仿真結(jié)果表明所設(shè)計的測量矩陣具有更好的性能。

壓縮采樣；測量矩陣；等角緊框架；梯度下降；稀疏性

1 引言

稀疏信號恢復(fù)問題已經(jīng)在信號和圖像處理方面被研究了很多年，一個有潛在稀疏結(jié)構(gòu)的信號比非稀疏信號能夠被更有效或更高效地壓縮、存儲和發(fā)送。這種最佳的狀況需要一個新穎的抽樣方案和一個恰當(dāng)?shù)闹亟ㄋ惴ǎ煌趥鹘y(tǒng)的技術(shù)，壓縮采樣技術(shù)在給出測量值y和恢復(fù)矩陣D后，主要的問題就在于解決下面的問題：

其中y∈Rm，恢復(fù)矩陣D∈Rm×n(m＜n)，稀疏解α∈Rn必須能夠被求解出來。?0范數(shù)(‖·‖0)能夠計數(shù)非零元素的個數(shù)同時也能測量信號的稀疏度。在不同的域（比如傅里葉、小波、離散余弦（DCT））中很多情況下原始信號都是稀疏的。在這種情況下，標(biāo)記為：y=Φx=ΦΨα= Dα，其中Φ∈Rm×n，Ψ∈Rn×n分別叫作測量矩陣和表達(dá)字典。和稀疏信號恢復(fù)相關(guān)的理論叫壓縮采樣（Compressive Sampling，CS），在CS理論[1-9]中，不僅僅要為式（1）找到最優(yōu)解，而且要能夠產(chǎn)生性能好的測量矩陣來對原始信號進(jìn)行壓縮，保證通過壓縮后的測量值y能夠很好地恢復(fù)出原始信號。壓縮采樣在一定意義上突破了奈奎斯特理論，更有效地利用原始信號的稀疏性，并且和信號的帶寬無直接關(guān)系。式（1）已經(jīng)被簡化為：

盡管信號具有稀疏性在CS中是非常必要的，但并不能保證一定能夠完全恢復(fù)出原始信號。到目前為止，為了通過盡可能少的測量數(shù)m就能穩(wěn)定地重建原始信號，測量矩陣Φ需要有特殊的要求[11]，這里主要是互相干性。一個性能好的測量矩陣Φ應(yīng)該設(shè)計成和表達(dá)字典Ψ有盡可能小的相干性，換句話說就是在恢復(fù)矩陣D=ΦΨ中，任意兩個不同列之間應(yīng)該有盡可能小的相干性，也就意味著恢復(fù)矩陣D應(yīng)接近于正交矩陣。高斯分布或者貝努力分布的隨機(jī)矩陣可以以很高的概率滿足這樣的性質(zhì)而且可以非自適應(yīng)地產(chǎn)生。盡管測量矩陣Φ通常選擇為隨機(jī)測量矩陣，但是最近的一些研究都在嘗試著構(gòu)造較隨機(jī)測量矩陣性能更好的測量矩陣。

因此為研究具有更好性能的測量矩陣Φ，本文提出了基于梯度下降的方法來優(yōu)化一個隨機(jī)的測量矩陣，降低其與已選擇的表達(dá)字典之間的相干性，目的在于在交替迭代的過程構(gòu)造出一個性能更好的測量矩陣。

2 測量矩陣的優(yōu)化

按照前面的標(biāo)記方法，假設(shè)α具有s個非零值稱作s-稀疏，比較好的壓縮采樣要求Φ和表達(dá)字典Ψ是非相干的，為了更好地度量這兩個矩陣之間的相干性定義如下：

定義1對于一個矩陣D，它的互相干性可以定義為不同的列之間的標(biāo)準(zhǔn)內(nèi)積絕對值的最大值，可以用下面式子來描述：

本文的目標(biāo)是優(yōu)化設(shè)計的測量矩陣Φ和表達(dá)字典Ψ間有較小的μmax。另外一種可以描述μmax的是矩陣D對應(yīng)的格拉姆矩陣=T，其中是矩陣D的列歸一化后得到的矩陣。設(shè)定一個測量值基于這個矩陣：可以看出應(yīng)當(dāng)使得這個μmax越小越好。所以矩陣D應(yīng)該具有最小的互相干性，也就是說對應(yīng)的格拉姆矩陣的非主對角線元素的值應(yīng)該接近于0，主對角線元素的值應(yīng)接近于1，即矩陣應(yīng)該接近于單位矩陣。格拉姆矩陣能夠等于單位矩陣只有在m=n的情況下才能實現(xiàn)，在這里不符合本文的要求。另一個有很小相干性的矩陣是等角緊框架（Equiangular Tight Frame，ETF）[12-13]，它是格拉斯曼框架的一種特殊情況，緊框架是正交基的推廣情況。正交基中所有的列向量的模都是1且任意兩個不同列之間的內(nèi)積為0，關(guān)于等角緊框架有如下定義：

3 算法步驟

開始先初始化一個隨機(jī)矩陣Φ（列獨立同分布），保持H不變，同時應(yīng)用梯度迭代方法最小化式（4）。記矩陣Φ的第i行j列元素為φij，定義成本函數(shù)：

最小化方法為φij←φij-η?χ/(?φij)，其中η＞0是迭代的步長，為了對矩陣Φ的所有元素都應(yīng)用所提出的方法，計算χ對于矩陣Φ的梯度（表示為▽Φχ=?χ/?Φ），具體為：

tr(·)表示矩陣的跡運算。考慮矩陣運算中矩陣的導(dǎo)數(shù)規(guī)則，將式（6）簡化成如下的式子：

然后整個更新方程可以寫成：

這里k是迭代的索引次數(shù)，β=4η，標(biāo)量步進(jìn)大小β可以是一個固定的值也可以是一個自適應(yīng)的隨著迭代而更新的值。在第k步迭代用式（8）更新測量矩陣后，再進(jìn)行更新矩陣H的過程。

為了使得測量矩陣Φ和表達(dá)字典Ψ間相干性盡可能地減小，恢復(fù)矩陣D應(yīng)接近于等角緊框架，在更新矩陣H的過程中使得其非對角線上元素的絕對值接近符號取其對應(yīng)的格拉姆矩陣G中對應(yīng)元素的符號即

gij為矩陣G=ΨTΦTΦΨ的第i行j列元素。這樣矩陣H的更新能夠保證在下一步測量矩陣Φ的更新中和表達(dá)字典Ψ具有較高相干性的元素得到很好的抑制。下面是該算法的偽代碼：

輸入表達(dá)字典Ψ，步長β和迭代次數(shù)：L和K

輸出測量矩陣Φ

在解決式（4）時，矩陣H主對角線元素單位化使得矩陣D=ΦΨ的列可以歸一化，但是在上述算法中沒有對矩陣D的列進(jìn)行規(guī)范化，這樣做可以減少算法中的運算量。然而，為了能夠前后一致地表示結(jié)果，計算基于列規(guī)范化矩陣D的相干性，標(biāo)記為D，相應(yīng)的G=DTD（其中G是矩陣D對應(yīng)的格拉姆矩陣，根據(jù)矩陣的運算法則可以從這個等式中看出G中的非對角線元素值能夠很好地反應(yīng)出矩陣D的不同列之間的相關(guān)性）。本文提出的算法重復(fù)迭代一定的次數(shù)，矩陣Φ和H交替進(jìn)行更新來減少式（4）的值，通過一個梯度下降方法來更新測量矩陣保證式（4）的逐漸下降并且收斂到一個局部的最小值，圖1為逐步迭代過程中式（4）的收斂情況。

圖1 不同測量數(shù)下式（4）收斂情況

圖1中可以看出不同測量數(shù)下收斂情況不同，本仿真實驗中連續(xù)兩次迭代式（4）值相差小于0.001時停止迭代。下面是采用此方法的matlab仿真結(jié)果。

4 仿真結(jié)果

這章將通過軟件仿真來驗證所提出的方法構(gòu)造出的測量矩陣的性能。首先產(chǎn)生一個高斯分布的隨機(jī)測量矩陣，然后運用提出的方法對其進(jìn)行優(yōu)化，生成新的測量矩陣，然后分別用這兩個測量矩陣對相同的原始信號在理想無噪聲情況下采用OMP算法進(jìn)行重建。

實驗中采用的表達(dá)字典是64×64的傅里葉正變換矩陣，原始信號稀疏度為7，圖2是在不同的測量數(shù)M情況下兩種測量矩陣（高斯隨機(jī)測量矩陣和優(yōu)化后的測量矩陣）對信號的恢復(fù)性能對比，結(jié)果用重建信號和初始信號之間的均方誤差大小來表示，均方誤差是通過計算重建出的信號及原始信號之差的模和原始信號模的比值來得到。均方誤差越小顯示出對應(yīng)的測量矩陣的性能越好，因此均方誤差的大小可以作為判定測量矩陣形態(tài)好壞的準(zhǔn)則，圖2中紅色的線表示優(yōu)化后的測量矩陣重建出的信號和原始信號的均方誤差大小，藍(lán)色的表示隨機(jī)測量矩陣重建出的信號和原始信號的均方誤差大小，可以明顯看出優(yōu)化后的測量矩陣對應(yīng)的均方誤差更小一些，也就是其性能較隨機(jī)測量矩陣更好。

圖2 不同測量數(shù)下均方誤差對比

5 結(jié)束語

從第4章可以看出，當(dāng)初始信號維數(shù)為64、稀疏度為7時，隨著測量數(shù)M的增加，隨機(jī)測量矩陣對初始信號的恢復(fù)性能逐漸變得更好，而對于相同且較小的測量數(shù)M情況下，優(yōu)化后的測量矩陣比原始隨機(jī)測量矩陣的性能要好很多；隨著測量數(shù)M的繼續(xù)增加并達(dá)到一定程度后，設(shè)計的測量矩陣和隨機(jī)測量矩陣之間的性能差別則逐漸減小。因此，通過此方法可以在相同條件下減少測量數(shù)M，降低壓縮成本。另外和等角緊框架（ETF）[16]相比，此方法設(shè)計測量矩陣的(M，N)參數(shù)的選擇比較靈活，而等角緊框架則有較大的限制。

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

[2]Candes E J，Wakin M B.An introduction to compressive sampling[J].IEEE Signal Processing Magazine，2008，25（2）：21-30.

[3]Romberg J.Imaging via compressing sampling[J].IEEE Signal Processing Magazine，2008，25（2）：14-20.

[4]Rauhut H，Schnass K，Vandergheynst P.Compressed sensing and redundant dictionaries[J].IEEE Transactions on Information Theory，2008，54（5）：2210-2219.

[5]DeVore R.Deterministic constructions of compressed sensing matrices[J].Journal of Complexity，2007，23（4-6）：918-925.

[6]Haupt J，Bajwa W U，Raz G，et al.Toeplitz compressed sensing matrices with applications to sparse channel estimation[J].IEEE Transactions on Information Theory，2010，56（11）：5862-5875.

[7]Candes E，Tao T.Near optimal signal recovery from random projections：universal encoding strategies[J].IEEE Transactions on Information Theory，2006，52（12）：5406-5425.

[8]Candes E J.Compressive sampling[C]//Proceedings of the International Congress of Mathematicians，Madrid，2006：1433-1452.

[9]石光明，劉丹華，高大化，等.壓縮感知理論及其研究進(jìn)展[J].電子學(xué)報，2009，5（5）：1070-1082.

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

[11]劉丹華，石光明，周佳社.一種冗余字典下的信號稀疏分解新方法[J].西安電子科技大學(xué)學(xué)報：自然科學(xué)版，2008，35（2）：228-232.

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

[13]Strohmer T.A note on equiangular tight frames[J].Linear Alg Appl，2008，429：326-330.

[14]Tropp J A，Dhillon I S，Heath R W，et al.Designingstructured tight frames via an alternating projectionmethod[J].IEEE Transactions on Information Theory，2005，51（1）：188-209.

[15]Zahedi R，Pezeshki A，Chong E K P.Robust measurementdesign for detecting sparse signals：equiangularuniform tight frames and Grassmannian packings[C]//American Control Conference，2010：4070-4075.

[16]Renes J M.Equiangular tight frames from Paley tournaments[J].Linear Alg Appl，2007，426：497-501.

WANG Nannan1,WANG Lixin1，2

1.School of Communication Engineering,Hangzhou Dianzi University,Hangzhou 310018,China
2.National Laboratory of Information Control Technology for Communication System,Jiaxing,Zhejiang 314001,China

In compressive sampling,measurement matrices should have very small coherence with the sparsity basis.Random measurement matrices have been used since they present small coherence with almost any sparsity basis.This paper proposes a gradient-based alternating minimization approach which is a variant of Grassmannian frame designing.The purpose is to optimize an initially random measurement matrix to a matrix which presents a smaller coherence than the initial one.The simulation results prove that measurement matrix generated by the proposed method has better performance. Key words：compressed sensing;measurement matrix;Equiangular Tight Frame（ETF）;gradient descent;sparsity

A

TN911

10.3778/j.issn.1002-8331.1208-0488

WANG Nannan,WANG Lixin.Gradient alternating iterative approach for designing measurement matrix.Computer Engineering and Applications,2014,50（6）：197-199.

王楠楠（1987—），男，碩士研究生，研究領(lǐng)域為信號處理；汪立新（1966—），男，教授，研究員，研究領(lǐng)域為信號處理。E-mail：wangnannanhello@163.com

2012-09-05

2013-01-18

1002-8331（2014）06-0197-03

CNKI網(wǎng)絡(luò)優(yōu)先出版：2013-02-20,http://www.cnki.net/kcms/detail/11.2127.TP.20130220.1555.010.html