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

程　濤

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

?

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

程濤1,2,3

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

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

壓縮感知；測量矩陣；信號；相關性；解空間

0　引言

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

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

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

1　壓縮感知理論

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

minx0s.t.y=Φx

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

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

minx1s.t.y=Φx

(2)

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

(1-σK)x2≤Φx2≤

(3)

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

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

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

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

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

表1列出了測量矩陣采用哈達瑪矩陣ΦH、高斯矩陣ΦG、高斯優(yōu)化矩陣ΦGO、稀疏循環(huán)矩陣ΦS、稀疏循環(huán)優(yōu)化矩陣ΦSO、稀疏循環(huán)近似矩陣ΦST的各種統(tǒng)計學參數(shù)(表1中各行數(shù)據(jù)，除“Jarque-Bera檢驗”外，“/”號左邊的數(shù)據(jù)表示最小值，“/”號右邊的數(shù)據(jù)表示最大值；“Jarque-Bera檢驗”行，“/”號左邊的數(shù)據(jù)表示符合檢驗的列數(shù)，“/”號右邊的數(shù)據(jù)表示符合檢驗的行數(shù))。μcmax表示列間相關系數(shù)絕對值的最大值；μrmax表示行間相關系數(shù)絕對值的最大值。各類矩陣的大小都是128×256。ΦH是從元素為+1和-1的哈達瑪方陣中隨機抽取M行；ΦG的各元素服從N(0,1/M)分布；ΦS的初始行向量是包含32個隨機分布的1的稀疏行向量，各行向量都是前一個行向量各元素依次右移2位的結果；Φ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)迭代多次，以使測量矩陣的性質趨于穩(wěn)定收斂。本文設定迭代次數(shù)都為100次。

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

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

3　實驗結果和分析

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

圖1　哈達瑪矩陣的重構概率與稀疏度的關系Fig.1　Prob. of exact recovery vs. the sparsity by Hadamard matrices.

圖2　高斯和哈達瑪矩陣的重構概率與稀疏度的關系Fig.2　Prob. of exact recovery vs. the sparsity by Gauss and Hadamard matrices.

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

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

比較圖1—圖3中的圖(b)可以發(fā)現(xiàn)，所有矩陣(ΦH、ΦHZ、ΦHZO、ΦHY、ΦHYO、ΦG、ΦGO、ΦS、ΦSO和ΦST)的重構曲線幾乎都重合在一起。這是因為，ΦHZ、ΦHZO、ΦHY、ΦHYO、ΦGO、ΦSO和ΦST都只是相當于在ΦH、ΦG和ΦS的左邊乘以一個滿秩的方陣，并不會改變原方程的解空間[4, 11-12]。因此BP算法還是在原空間的可行域內做全局搜索。由此可見基于l1范數(shù)的BP算法受測量矩陣的列不相關性的影響較小。基于同一信號集，所有矩陣的任意列組的列秩幾乎都是一樣的，其中ΦS并不具有好的RIP性質。所以在實際操作中，好的RIP性質并不是能夠取得好的重構效果的必要條件。解空間和矩陣及其子矩陣的列秩才是判斷能否取得好的重構效果的必要條件。

4　結論

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

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

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

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

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

[5]趙光輝, 張?zhí)戽I, 沈方芳, 等. 低信噪比下穩(wěn)健壓縮感知成像 [J]. 航空學報, 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]. 光學學報, 2013, 33(2): 2200011-2200016.

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

[13]程濤, 劉玉安. 基于單像素相機重構矩陣優(yōu)化的影像采集和重構方法 [J]. 探測與控制學報, 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

國家自然科學基金資助項目(41461082);中國博士后科學基金資助項目(2016M592525)；廣西自然科學基金資助項目(2014GXNSFAA118285);廣西高校科學技術研究項目資助(YB2014212);廣西科技大學博士基金資助項目(校科博13Z12)

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

TP391

A

1008-1194(2016)04-0072-05