信號重構(gòu)中測量矩陣性能的判據(jù)

程　濤

(1. 深圳大學(xué)光電工程學(xué)院,光電子器件與系統(tǒng)重點(diǎn)實(shí)驗(yàn)室，廣東 深圳　518060；2. 廣西科技大學(xué)汽車與交通學(xué)院，廣西 柳州　545006；3.深圳大學(xué)光電工程學(xué)院，深圳生物醫(yī)學(xué)光學(xué)微納檢測與成像重點(diǎn)實(shí)驗(yàn)室，廣東 深圳　518060)

?

信號重構(gòu)中測量矩陣性能的判據(jù)

程濤1,2,3

(1. 深圳大學(xué)光電工程學(xué)院,光電子器件與系統(tǒng)重點(diǎn)實(shí)驗(yàn)室，廣東 深圳518060；2. 廣西科技大學(xué)汽車與交通學(xué)院，廣西 柳州545006；3.深圳大學(xué)光電工程學(xué)院，深圳生物醫(yī)學(xué)光學(xué)微納檢測與成像重點(diǎn)實(shí)驗(yàn)室，廣東 深圳518060)

針對壓縮感知中測量矩陣性能判據(jù)混亂的問題，提出基于不同類型重構(gòu)算法的測量矩陣性能判據(jù)。該判據(jù)比傳統(tǒng)方法的可操作性更好，在矩陣的其他性質(zhì)都近乎一致的條件下實(shí)現(xiàn)了對具有不同列不相關(guān)性矩陣的嚴(yán)格對比實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果表明，對于OMP(orthogonal matching pursuit)算法，測量矩陣的列不相關(guān)性可作為測量矩陣性能判據(jù)，但當(dāng)列不相關(guān)性達(dá)到一定程度(即μcmax>0.25)后對測量矩陣性能再無影響。對于BP(Basis Pursuit)算法，具有相同解空間的測量矩陣性能與列不相關(guān)性無關(guān)；測量矩陣的列不相關(guān)性不是判斷測量矩陣性能的主要判據(jù)。一個矩陣能達(dá)到的理論上限就是等規(guī)模的哈達(dá)瑪矩陣的重構(gòu)能力。

壓縮感知；測量矩陣；信號；相關(guān)性；解空間

0　引言

信息技術(shù)的飛速發(fā)展使得獲取和利用海量數(shù)據(jù)和信號成為可能。信號的數(shù)字化是通過從模擬信源采樣實(shí)現(xiàn)的。但是，奈奎斯特采樣定理指出，帶限信號的采樣頻率必須大于其帶寬的兩倍以上才能確保由采樣完全重構(gòu)原始信號。只有增加信號帶寬才能攜帶更多的信息。但是信號帶寬的增加又導(dǎo)致采樣頻率的提高。因此，現(xiàn)有技術(shù)的采樣頻率和處理速度越來越難以與日益增長的寬帶信號處理需求相匹配[1-3]。

信號中存在大量的冗余信息，人們開發(fā)了各種壓縮算法，以降低存儲、處理和傳輸?shù)某杀?。壓縮比大的多為損壓縮方式。例如，在快速傅里葉變換中，大量不重要的高頻系數(shù)被丟棄。這種前期采集大量數(shù)據(jù)，又在后期壓縮過程中丟棄大量數(shù)據(jù)的格局造成了資源的嚴(yán)重浪費(fèi)了。人們一直期望一種采集壓縮一體化的信號采集處理格局。這樣就可采集、傳輸、存儲、處理和管理很少的數(shù)據(jù)，就可實(shí)現(xiàn)對原始信號的完全或近似重構(gòu)。從而擺脫傳統(tǒng)技術(shù)的窘境，節(jié)約巨大的人力物力資源[4]。

壓縮感知就能以遠(yuǎn)低于奈奎斯特采樣定理要求的頻率采樣，在采集信號的同時實(shí)現(xiàn)對信號的壓縮，并能高質(zhì)量地恢復(fù)原始信號。壓縮感知在圖像處理、視頻分析、雷達(dá)遙感、信息通信、數(shù)據(jù)挖掘、軍事偵察、資源探測和醫(yī)學(xué)成像等領(lǐng)域有廣闊的應(yīng)用前景和巨大的經(jīng)濟(jì)效益[4]。壓縮感知的研究內(nèi)容主要分為三個部分：測量矩陣、稀疏表示和重構(gòu)算法。測量矩陣主要研究測量矩陣設(shè)計、優(yōu)化、性能分析等；稀疏表示主要研究信號的稀疏化方法等；重構(gòu)算法主要研究壓縮感知的各種求解方法。其中測量矩陣是壓縮感知研究的核心。本文針對壓縮感知中測量矩陣性能判據(jù)混亂的問題，提出基于不同類型重構(gòu)算法的測量矩陣性能判據(jù)。

1　壓縮感知理論

壓縮感知理論表明，如果信號是稀疏的，就能以遠(yuǎn)低于奈奎斯特(Nyquist)采樣頻定理的采樣率采集信號，并能以高概率精確重建稀疏信號[5]，壓縮感知模型如式(1)所示，求解式(1)就可以重構(gòu)出稀疏信號x。

minx0s.t.y=Φx

(1)式(1)中，y是測量數(shù)據(jù)，y∈RM；Φ是測量矩陣，Φ∈RM×N，M

式(1)屬于非凸優(yōu)化問題，缺乏完善的理論基礎(chǔ)。因此，一般把式(1)轉(zhuǎn)化成如式(2)所示的凸松弛優(yōu)化問題。如果Φ滿足RIP(Restricted isometry property)性質(zhì)，求解式(2)就能以極高概率得到與求解式(1)一樣的稀疏信號x。而且凸優(yōu)化問題具有更完善的理論基礎(chǔ)，更易于做理論分析和提高計算速度。

minx1s.t.y=Φx

(2)

測量矩陣Φ的性質(zhì)是關(guān)系信號重構(gòu)效果的關(guān)鍵。當(dāng)前判斷測量矩陣Φ性能優(yōu)劣的主要判據(jù)為是否滿足RIP性質(zhì)，如式(3)所示[6]。但是一個矩陣及其子矩陣是否滿足RIP性質(zhì)的驗(yàn)證可操作性不強(qiáng)，現(xiàn)在只有一些定性的說明。例如，隨機(jī)矩陣的RIP性質(zhì)一般都較好。但是有的隨機(jī)矩陣(例如，0-1隨機(jī)矩陣)在式(3)中的最小和最大特征值并不是一個接近1的值。

(1-σK)x2≤Φx2≤

(3)

由于RIP的不易操作性，Donoho提出測量矩陣設(shè)計判斷三原則：測量矩陣的列向量應(yīng)滿足一定的不相關(guān)性、測量矩陣列向量的元素應(yīng)具有獨(dú)立隨機(jī)性、基于l1范數(shù)的解就是最優(yōu)解[1]。但是這些原則也是只是基于l1范數(shù)的基礎(chǔ)上提出的，不適用于基于l0范數(shù)的貪婪算法，例如OMP(orthogonal matching pursuit)算法。而且由于各類矩陣的各種性質(zhì)都不一樣，缺乏可比性，因而Donoho三原則缺乏真實(shí)對比實(shí)驗(yàn)的支持。

文獻(xiàn)[1, 9—10]提出測量矩陣的行向量正交化以及列向量單位化的設(shè)計準(zhǔn)則。文獻(xiàn)[11—13]進(jìn)一步根據(jù)哈達(dá)瑪矩陣的特點(diǎn)，通過數(shù)學(xué)推導(dǎo)和證明，提出了適用于l0范數(shù)的測量矩陣設(shè)計五原則：行模相近、列模相近、各行不相關(guān)性好和各列不相關(guān)性好以及行列元素服從隨機(jī)分布，并據(jù)此設(shè)計出具有不同列不相關(guān)性的高斯矩陣。但是由于文獻(xiàn)[12]中的各種實(shí)驗(yàn)采用的不是同一套數(shù)據(jù)集，因而導(dǎo)致實(shí)驗(yàn)結(jié)果不是很準(zhǔn)確，無法精確把握問題的本質(zhì)。列不相關(guān)性比RIP和Donoho三原則有更好的可操作性。Elad[14]和Duarte[15]等人的矩陣設(shè)計思路也是以列相關(guān)性最小化或平均化為目標(biāo)。

2　測量矩陣性能的判據(jù)

一般來說，測量矩陣的列不相關(guān)性越好，那么RIP性質(zhì)也越好，也意味著OMP和BP的重構(gòu)效果也越好。但這都是基于過去具有不同列不相關(guān)性的不同類型測量矩陣實(shí)驗(yàn)得到的經(jīng)驗(yàn)性結(jié)論，并非嚴(yán)格意義上的對比試驗(yàn)。測量矩陣性能受到眾多因素的影響。如果能排除測量矩陣其他各種因素的影響，就可研究清楚單一因素對測量矩陣性能的影響。然后，在這一基礎(chǔ)上就可進(jìn)一步研究其他各個因素的作用。本文設(shè)計了具有不同列不相關(guān)性的矩陣，矩陣的其他性質(zhì)都近乎一致。在此基礎(chǔ)上做對比實(shí)驗(yàn)，就可研究清楚列不相關(guān)性對矩陣性能的真實(shí)影響。從而確定基于不同類型重構(gòu)算法的測量矩陣性能判據(jù)。

本文設(shè)計了具有不同列不相關(guān)性的哈達(dá)瑪矩陣ΦH、高斯矩陣ΦG、高斯優(yōu)化矩陣ΦGO、稀疏循環(huán)矩陣ΦS、稀疏循環(huán)優(yōu)化矩陣ΦSO、稀疏循環(huán)近似矩陣ΦST，以及哈達(dá)瑪矩陣ΦH左乘高斯方陣ΦGZ得到的ΦHZ、哈達(dá)瑪矩陣左乘高斯方陣后的優(yōu)化矩陣ΦHZO、哈達(dá)瑪矩陣ΦH右乘高斯方陣ΦGY得到的ΦHY、哈達(dá)瑪矩陣右乘高斯方陣后的優(yōu)化矩陣ΦHYO。除ΦG、ΦS、ΦHZ和ΦHY之外，這些矩陣基本都滿足行模相近、列模相近、各列不相關(guān)性好以及行列元素服從隨機(jī)分布，如表1所示。

表1列出了測量矩陣采用哈達(dá)瑪矩陣ΦH、高斯矩陣ΦG、高斯優(yōu)化矩陣ΦGO、稀疏循環(huán)矩陣ΦS、稀疏循環(huán)優(yōu)化矩陣ΦSO、稀疏循環(huán)近似矩陣ΦST的各種統(tǒng)計學(xué)參數(shù)(表1中各行數(shù)據(jù)，除“Jarque-Bera檢驗(yàn)”外，“/”號左邊的數(shù)據(jù)表示最小值，“/”號右邊的數(shù)據(jù)表示最大值；“Jarque-Bera檢驗(yàn)”行，“/”號左邊的數(shù)據(jù)表示符合檢驗(yàn)的列數(shù)，“/”號右邊的數(shù)據(jù)表示符合檢驗(yàn)的行數(shù))。μcmax表示列間相關(guān)系數(shù)絕對值的最大值；μrmax表示行間相關(guān)系數(shù)絕對值的最大值。各類矩陣的大小都是128×256。ΦH是從元素為+1和-1的哈達(dá)瑪方陣中隨機(jī)抽取M行；ΦG的各元素服從N(0,1/M)分布；ΦS的初始行向量是包含32個隨機(jī)分布的1的稀疏行向量，各行向量都是前一個行向量各元素依次右移2位的結(jié)果；ΦGO是采用優(yōu)化算法基于ΦG得到的測量矩陣；ΦSO和ΦST是采用優(yōu)化算法基于ΦS得到的測量矩陣；ΦHZ的左乘高斯方陣；ΦHZO和ΦHYO是采用優(yōu)化算法基于ΦHZ和ΦHY得到的測量矩陣。其中ΦGZ的各元素服從N(0,1/M)分布，ΦGY的各元素服從N(0,1/N)分布。優(yōu)化算法就是對不同的測量矩陣依次做行向量正交規(guī)范化和列向量單位化操作并循環(huán)迭代多次，以使測量矩陣的性質(zhì)趨于穩(wěn)定收斂。本文設(shè)定迭代次數(shù)都為100次。

OMP是基于l0范數(shù)的經(jīng)典算法，BP(Basis Pursuit)是基于l1范數(shù)的經(jīng)典算法。絕大多數(shù)重構(gòu)算法都是在OMP和BP的基礎(chǔ)上改進(jìn)升級得到的。OMP和BP算法原理簡單，不涉及信號先驗(yàn)信息，受信號和重構(gòu)矩陣(測量矩陣)類型影響小，因而更適用于理論研究。

表1　各類矩陣的相關(guān)參數(shù)

3　實(shí)驗(yàn)結(jié)果和分析

圖1—圖3是采用OMP和BP兩種算法重構(gòu)不同稀疏度高斯信號的精確重構(gòu)概率和稀疏度關(guān)系曲線。圖1—圖3都采用同一數(shù)據(jù)集，每種不同稀疏度的實(shí)驗(yàn)以不同信號重復(fù)500次。圖1是哈達(dá)瑪矩陣ΦH、哈達(dá)瑪矩陣左乘高斯方陣ΦHZ、哈達(dá)瑪矩陣左乘高斯方陣后的優(yōu)化矩陣ΦHZO、哈達(dá)瑪矩陣右乘高斯方陣ΦHY、哈達(dá)瑪矩陣右乘高斯方陣后的優(yōu)化矩陣ΦHYO的重構(gòu)結(jié)果。圖2是哈達(dá)瑪矩陣、高斯矩陣ΦG和高斯優(yōu)化矩陣ΦGO的重構(gòu)結(jié)果。圖3是哈達(dá)瑪矩陣、稀疏循環(huán)矩陣ΦS、稀疏循環(huán)矩陣的優(yōu)化矩陣ΦSO和近似矩陣ΦST的重構(gòu)結(jié)果。圖1—圖3中的曲線ΦH都是同一條曲線。

圖1　哈達(dá)瑪矩陣的重構(gòu)概率與稀疏度的關(guān)系Fig.1　Prob. of exact recovery vs. the sparsity by Hadamard matrices.

圖2　高斯和哈達(dá)瑪矩陣的重構(gòu)概率與稀疏度的關(guān)系Fig.2　Prob. of exact recovery vs. the sparsity by Gauss and Hadamard matrices.

圖3　稀疏循環(huán)和哈達(dá)瑪矩陣的重構(gòu)概率與稀疏度的關(guān)系Fig.3　Prob. of exact recovery vs. the sparsity by sparse circulant and Hadamard matrices.

根據(jù)計算結(jié)果可知，ΦHZ和ΦHZO的μc max分別為0.431和0.172；ΦHY和ΦHYO的μc max分別為0.372和0.258。ΦH的μc max分別為0.172。比較圖1-圖3中的圖(a)可以發(fā)現(xiàn)，ΦHZ、ΦHY、ΦG和ΦS的列不相關(guān)性最差，而且行模和列模也不近似相等。各行列也不全服從隨機(jī)分布，所以重構(gòu)效果最差。ΦH、ΦHZO、ΦHYO、ΦGO、ΦSO和ΦST的μr max幾乎都完全不相關(guān)，行模和列模都近似相等。盡管μc max最大為0.254，最小為0.172，相差較大，但是重構(gòu)結(jié)果都幾乎一樣，幾乎都與曲線ΦH重合。這說明，對于基于l0范數(shù)的OMP算法，測量矩陣的列不相關(guān)性達(dá)到一定程度(即μc max>0.25)就不會對信號的重構(gòu)結(jié)果再產(chǎn)生大的影響。因此一味追求測量矩陣高的列不相關(guān)性是不合適的。這是因?yàn)镺MP算法中存在最小二乘法的矩陣運(yùn)算，在物理幾何意義上就是平行四邊形法則在高維空間的展開。只要任意兩列向量間夾角大于一定程度(即μc max>0.25)，就可以避免計算機(jī)中的精度不足問題，因而重構(gòu)結(jié)果變化不大。

比較圖1—圖3中的圖(b)可以發(fā)現(xiàn)，所有矩陣(ΦH、ΦHZ、ΦHZO、ΦHY、ΦHYO、ΦG、ΦGO、ΦS、ΦSO和ΦST)的重構(gòu)曲線幾乎都重合在一起。這是因?yàn)椋礖Z、ΦHZO、ΦHY、ΦHYO、ΦGO、ΦSO和ΦST都只是相當(dāng)于在ΦH、ΦG和ΦS的左邊乘以一個滿秩的方陣，并不會改變原方程的解空間[4, 11-12]。因此BP算法還是在原空間的可行域內(nèi)做全局搜索。由此可見基于l1范數(shù)的BP算法受測量矩陣的列不相關(guān)性的影響較小?；谕恍盘柤芯仃嚨娜我饬薪M的列秩幾乎都是一樣的，其中ΦS并不具有好的RIP性質(zhì)。所以在實(shí)際操作中，好的RIP性質(zhì)并不是能夠取得好的重構(gòu)效果的必要條件。解空間和矩陣及其子矩陣的列秩才是判斷能否取得好的重構(gòu)效果的必要條件。

4　結(jié)論

本文提出基于不同類型重構(gòu)算法的測量矩陣性能判據(jù)。基于列不相關(guān)性和解空間的判據(jù)比傳統(tǒng)方法的可操作性更好，在矩陣的其他性質(zhì)都近乎一致的條件下實(shí)現(xiàn)了對具有不同列不相關(guān)性矩陣的嚴(yán)格對比實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果表明，對于OMP(orthogonalmatchingpursuit)算法，測量矩陣的列不相關(guān)性可作為測量矩陣性能判據(jù)，但當(dāng)列不相關(guān)性達(dá)到一定程度(即μc max>0.25)后對測量矩陣性能再無影響。對于BP(BasisPursuit)算法，具有相同解空間的測量矩陣性能與列不相關(guān)性無關(guān)；測量矩陣的列不相關(guān)性不是判斷測量矩陣性能的主要判據(jù)。一個矩陣能達(dá)到的理論上限就是等規(guī)模的哈達(dá)瑪矩陣的重構(gòu)能力。擬設(shè)計更多具有不同列不相關(guān)性的測量矩陣深入探究列不相關(guān)性和解空間之間的關(guān)聯(lián)和差異。

[1]DONOHODL.Compressedsensing[J].InformationTheory,IEEETransactionson, 2006, 52(4): 1289-1306.

[2]戴瓊海, 付長軍, 季向陽. 壓縮感知研究 [J]. 計算機(jī)學(xué)報, 2011, 34(3): 425-433.

[3]石光明, 劉丹華, 高大化, 等. 壓縮感知理論及其研究進(jìn)展 [J]. 電子學(xué)報, 2009, 37(5): 1070-1081.

[4]程濤. 基于壓縮感知的遙感變化檢測研究 [D]. 武漢： 武漢大學(xué), 2013.

[5]趙光輝, 張?zhí)戽I, 沈方芳, 等. 低信噪比下穩(wěn)健壓縮感知成像 [J]. 航空學(xué)報, 2012, 33(3): 1-10.

[6]TAOC.Restrictedconformalpropertyofcompressivesensing[C]//WaveletActiveMediaTechnologyandInformationProcessing(ICCWAMTIP). 2014 11thInternationalComputerConference. 2014: 152-161.

[7]WEID,MILENKOVICO.SubspacePursuitforCompressiveSensingSignalReconstruction[J].InformationTheory,IEEETransactionson, 2009, 55(5): 2230-2249.

[8]CANDESEJ,TAOT.Decodingbylinearprogramming[J].InformationTheory,IEEETransactionson, 2005, 51(12): 4203-4215.

[9]DONOHODL,TSAIGY,DRORII,etal.SparseSolutionofUnderdeterminedSystemsofLinearEquationsbyStagewiseOrthogonalMatchingPursuit[J].InformationTheory,IEEETransactionson, 2012, 58(2): 1094-1121.

[10]CANDESEJ,TAOT.Near-OptimalSignalRecoveryFromRandomProjections:UniversalEncodingStrategies[J].InformationTheory,IEEETransactionson, 2006, 52(12): 5406-5425.

[11]程濤, 朱國賓, 劉玉安. 基于0-1稀疏循環(huán)矩陣的測量矩陣分離研究 [J]. 光學(xué)學(xué)報, 2013, 33(2): 2200011-2200016.

[12]程濤, 朱國賓, 劉玉安. 壓縮感知中高斯矩陣的優(yōu)化研究 [J]. 計算機(jī)應(yīng)用研究, 2014, 31(12): 3599-3602.

[13]程濤, 劉玉安. 基于單像素相機(jī)重構(gòu)矩陣優(yōu)化的影像采集和重構(gòu)方法 [J]. 探測與控制學(xué)報, 2014, 36(4): 30-35.

[14]ELADM.OptimizedProjectionsforCompressedSensing[J].SignalProcessing,IEEETransactionson, 2007, 55(12): 5695-5702.

[15]DUARTE-CARVAJALINOJM,SAPIROG.LearningtoSenseSparseSignals:SimultaneousSensingMatrixandSparsifyingDictionaryOptimization[J].ImageProcessing,IEEETransactionson, 2009, 18(7): 1395-1408.

Performance Criteria of Measurement Matrices in Signal Reconstruction

CHENG Tao1,2,3

(1. Key Laboratory of Optoelectronic Devices and Systems of Ministry of Education and Guangdong Province, College of Optoelectronic Engineering, Shenzhen University, Shenzhen 518060, China; 2. Automotive & Transportation Engineering Institute，Guangxi University of Science and Technology, Liuzhou, 545006, China;3. Shenzhen Key Laboratory of Micro-Nano Measuring and Imaging in Biomedical Optics of Shenzhen, College of Optoelectronic Engineering, Shenzhen University, Shenzhen, 518060, China)

Aiming at the confusing problem of measurement matrix performance criteria, the performance criteria of the measurement matrix based on different types of reconstruction algorithms were proposed. The operatebility of this criterion was better than the traditional method. The strict contrast experiments were implemented on matrices with different columns correlation by this method when other properties of matrices were almost identical. Experimental results showed that column incoherence of a measurement matrix could be taken as the performance criteria of the measurement matrix for OMP (orthogonal matching pursuit). However, the performance of the measurement matrix did not be affected when the correlation was enough between the columns. The performance of the measurement matrices with the same solution space had no relation with the column correlation for BP(Basis Pursuit). Measurement matrix correlation was not the main criteria to determine the performance of the measurement matrix. Theoretical upper limit of the matrix was reconstruction ability of Hadamard matrix in same scale.

compressive sensing; measurement matrix; signal correlation; solution space

2016-02-15

國家自然科學(xué)基金資助項(xiàng)目(41461082);中國博士后科學(xué)基金資助項(xiàng)目(2016M592525)；廣西自然科學(xué)基金資助項(xiàng)目(2014GXNSFAA118285);廣西高校科學(xué)技術(shù)研究項(xiàng)目資助(YB2014212);廣西科技大學(xué)博士基金資助項(xiàng)目(?？撇?3Z12)

程濤(1976—)，男，廣西柳州人，博士，副教授，研究方向：壓縮感知和遙感。E-mail:ctnp@163.com。

TP391

A

1008-1194(2016)04-0072-05