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

王楠楠，汪立新，2

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

2.通信系統(tǒng)信息控制技術(shù)國(guó)家級(jí)重點(diǎn)實(shí)驗(yàn)室，浙江嘉興 314001

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

王楠楠1，汪立新1，2

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

2.通信系統(tǒng)信息控制技術(shù)國(guó)家級(jí)重點(diǎn)實(shí)驗(yàn)室，浙江嘉興 314001

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

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

1 引言

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

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

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

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

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

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

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

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

3 算法步驟

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

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

tr(·)表示矩陣的跡運(yùn)算?？紤]矩陣運(yùn)算中矩陣的導(dǎo)數(shù)規(guī)則，將式（6）簡(jiǎn)化成如下的式子：

然后整個(gè)更新方程可以寫(xiě)成：

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

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

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

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

輸出測(cè)量矩陣Φ

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

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

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

4 仿真結(jié)果

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

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

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

5 結(jié)束語(yǔ)

從第4章可以看出，當(dāng)初始信號(hào)維數(shù)為64、稀疏度為7時(shí)，隨著測(cè)量數(shù)M的增加，隨機(jī)測(cè)量矩陣對(duì)初始信號(hào)的恢復(fù)性能逐漸變得更好，而對(duì)于相同且較小的測(cè)量數(shù)M情況下，優(yōu)化后的測(cè)量矩陣比原始隨機(jī)測(cè)量矩陣的性能要好很多；隨著測(cè)量數(shù)M的繼續(xù)增加并達(dá)到一定程度后，設(shè)計(jì)的測(cè)量矩陣和隨機(jī)測(cè)量矩陣之間的性能差別則逐漸減小。因此，通過(guò)此方法可以在相同條件下減少測(cè)量數(shù)M，降低壓縮成本。另外和等角緊框架（ETF）[16]相比，此方法設(shè)計(jì)測(cè)量矩陣的(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é)報(bào)，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]劉丹華，石光明，周佳社.一種冗余字典下的信號(hào)稀疏分解新方法[J].西安電子科技大學(xué)學(xué)報(bào)：自然科學(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)域?yàn)樾盘?hào)處理；汪立新（1966—），男，教授，研究員，研究領(lǐng)域?yàn)樾盘?hào)處理。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