王 強(qiáng)，張培林，王懷光，楊望燦，陳彥龍

(軍械工程學(xué)院 車輛與電氣工程系，石家莊 050003)

(*通信作者電子郵箱ZPL1955@163.com)

壓縮感知中測量矩陣構(gòu)造綜述

王 強(qiáng)，張培林*，王懷光，楊望燦，陳彥龍

(軍械工程學(xué)院 車輛與電氣工程系，石家莊 050003)

(*通信作者電子郵箱ZPL1955@163.com)

壓縮感知測量矩陣構(gòu)造方式多樣并不斷發(fā)展，為梳理現(xiàn)有研究成果，掌握測量矩陣發(fā)展動(dòng)態(tài)，對壓縮感知測量矩陣構(gòu)造進(jìn)行系統(tǒng)介紹。首先，針對傳統(tǒng)信號采集理論存在的信息冗余問題，闡述了壓縮感知理論在信號采集過程中資源利用率高、存儲(chǔ)空間小的優(yōu)勢；其次，以壓縮感知理論框架為基礎(chǔ)，從測量矩陣構(gòu)造原則、測量矩陣產(chǎn)生方法、測量矩陣結(jié)構(gòu)設(shè)計(jì)、測量矩陣優(yōu)化方法四個(gè)方面，對壓縮感知測量矩陣構(gòu)造進(jìn)行分析，討論了測量矩陣構(gòu)造過程中不同原則、結(jié)構(gòu)、方法的優(yōu)勢；最后，在總結(jié)現(xiàn)有研究成果的基礎(chǔ)上，對測量矩陣的發(fā)展方向進(jìn)行了展望。

壓縮感知；測量矩陣；有限等距性質(zhì)；信號重構(gòu)；信號采集

0 引言

在傳統(tǒng)奈奎斯特采樣定理?xiàng)l件下，要實(shí)現(xiàn)原始信號的精確重構(gòu)，采樣過程中的采樣頻率至少高于原始信號中最高頻率的兩倍。但奈奎斯特采樣定理是原始信號能夠精確重構(gòu)的充分條件，而非必要條件。依照該定理采樣后的數(shù)據(jù)中包含大量冗余信息，數(shù)據(jù)在應(yīng)用過程中，經(jīng)過處理只保留了部分有用信息，大部分無用信息被舍棄，這就導(dǎo)致在采樣、壓縮過程中，大量時(shí)間、空間被浪費(fèi)。因此學(xué)者們嘗試突破奈奎斯特采樣定理的限制，提出利用少量的采樣數(shù)據(jù)來精確重構(gòu)原始信號。Candes等[1-2]在壓縮感知理論上取得重大突破。他們結(jié)合隨機(jī)矩陣，利用少量隨機(jī)采樣的頻率系數(shù)，通過求解一個(gè)凸優(yōu)化問題，實(shí)現(xiàn)了原始信號的精確重構(gòu)[3]，并提出了魯棒的不確定性原則。隨后，壓縮感知的理論被正式提出，并得到了不斷的完善、發(fā)展與應(yīng)用[4]。在壓縮感知條件下，某個(gè)變換域具有稀疏、近稀疏性的信號或者圖像，可以通過“全息”測量的方式，將采樣與壓縮的過程合并，直接獲得原始信號的有用信息，并能夠通過近似優(yōu)化算法，實(shí)現(xiàn)原始信號的精確重構(gòu)[5]。

壓縮感知理論主要包括信號稀疏表示、測量矩陣構(gòu)造、重構(gòu)算法設(shè)計(jì)三方面的內(nèi)容[6]。在壓縮感知理論中，要求信號具有可壓縮性，信號的稀疏表示是信號可壓縮性能的具體體現(xiàn)，而可壓縮性能的好壞依賴于稀疏字典的設(shè)計(jì)，在壓縮感知之初，信號的稀疏字典是基于變換域(傅里葉變換、小波變換等)的正交基字典[7]，這種方法應(yīng)用廣泛，易于操作，但是適用性不強(qiáng)，對于任意信號，基于變換的正交基字典無法準(zhǔn)確表達(dá)信號的可壓縮性。因此過冗余的稀疏字典設(shè)計(jì)引起越來越多的關(guān)注，并且通過引入學(xué)習(xí)算法，克服稀疏字典構(gòu)造面臨的先驗(yàn)知識依賴缺陷，從而構(gòu)造出與原始信號相適應(yīng)的優(yōu)化字典，如應(yīng)用廣泛的最優(yōu)方向算法(Method of Optimal Directions, MOD)[8]、K-奇異值分解(K-Singular Value Decomposition,K-SVD)[9]等。

測量矩陣的構(gòu)造效果直接影響到壓縮采樣后獲取的信息量，因此矩陣的構(gòu)造理論是壓縮感知理論形成的一大瓶頸，Candes等[10]在對線性編碼系統(tǒng)的系統(tǒng)特性描述中提出：有限等距常數(shù)(Restricted Isometry Constant, RIC)在滿足特定條件下，重構(gòu)信號具有唯一性與準(zhǔn)確性，隨后，Candes[11]針對壓縮感知理論提出測量矩陣的有限等距特性(Restricted Isometry Property, RIP)。RIP作為測量矩陣構(gòu)造的必要條件得到了廣泛認(rèn)可與發(fā)展。以此為基礎(chǔ)，測量矩陣的構(gòu)造原則不斷豐富，但在本質(zhì)上保持著一致性，針對不同的編碼、構(gòu)造方式，滿足的不同條件，都能在一定程度上保證原始信號的唯一精確重構(gòu)。

經(jīng)過壓縮采樣的信號保留了原始信號重構(gòu)的必要信息，但信號的重構(gòu)仍然是一個(gè)NP難問題。重構(gòu)過程利用了原始信號的稀疏特性，在變換域內(nèi)信號的非零系數(shù)有限，這就為信號重構(gòu)提供了可能。解決這類問題的算法主要包括貪婪算法、凸優(yōu)化算法等。貪婪算法包括匹配追蹤[12]、正交匹配追蹤[13]、壓縮采樣匹配追蹤[14]等，這類算法運(yùn)算速度較快，但是運(yùn)算精度有限。凸優(yōu)化算法包括基追蹤算法[15]、梯度投影法[16]、內(nèi)點(diǎn)迭代法[17]等。該類算法運(yùn)算時(shí)間較長，但重構(gòu)精度較高，適用于原始信號的重構(gòu)精度要求較高的情況。

在壓縮感知理論中，測量矩陣作為原始信號的壓縮采樣系統(tǒng)，發(fā)揮了關(guān)鍵的作用，因此引起國內(nèi)外學(xué)者的廣泛關(guān)注，測量矩陣大致可以分成隨機(jī)矩陣以及確定性矩陣。在壓縮感知理論之初，服從特定分布的隨機(jī)矩陣作為測量矩陣，取得了很好的重構(gòu)效果[5]，隨后，貝努力隨機(jī)矩陣[2]、托普利茲測量矩陣[13]以及基于特定編碼[6]的確定性矩陣等被證明也能夠用于壓縮感知的測量矩陣。發(fā)展至今，各種矩陣構(gòu)造方式多樣并不斷發(fā)展，因此本文在總結(jié)國內(nèi)外測量矩陣研究現(xiàn)狀的前提下，對壓縮感知中測量矩陣構(gòu)造進(jìn)行了探討與研究。

1 壓縮感知理論模型

假定離散信號x∈RN，長度為N，把x看作N維列向量，向量中第n個(gè)元素可以表示為：xn(n=1,2,…，N)，給定一組正交基Ψ={Ψ1，Ψ2，…，ΨN}，Ψi為N維列向量，則x可以表示為：

(1)

其中s是由權(quán)重系數(shù)si組成的N維向量，si可以表示為：

si=〈x,Ψi〉=ΨiTx

(2)

其中T表示轉(zhuǎn)置運(yùn)算。x與s是信號在時(shí)域以及Ψ域內(nèi)的不同表現(xiàn)方式，因此二者從本質(zhì)上是等價(jià)的。假設(shè)信號在Ψ域?yàn)镵-稀疏信號，則s向量中非零元素的個(gè)數(shù)為K?N(遠(yuǎn)小于)，x可以看作是K個(gè)基向量的線性組合。若s中只有K個(gè)數(shù)值較大的權(quán)重系數(shù)，N-K個(gè)系數(shù)數(shù)值較小或近似于零時(shí)，信號在Ψ域可以看作為近似K-稀疏信號，滿足上述條件的信號均視為可壓縮信號。

y=Φx=ΦΨs=Θs

(3)

其中感知因子Θ=ΦΨ。當(dāng)原始信號為時(shí)域稀疏信號時(shí)，變換域可以看作是單位陣，此時(shí)，壓縮感知因子與測量矩陣相同，由于M?N，因此從y中直接恢復(fù)x的數(shù)學(xué)模型中，未知量遠(yuǎn)大于方程個(gè)數(shù)，求解過程表現(xiàn)為病態(tài)，但是由于信號具有可壓縮性，即s為K-稀疏信號，這就為y恢復(fù)s提供了可能，因此可以通過感知因子求解信號的稀疏系數(shù)向量s，在已知原始信號稀疏域的條件下，原始信號就能夠得到精確重構(gòu)。壓縮感知理論避免了傳統(tǒng)方法先采樣、后壓縮的復(fù)雜過程，基于壓縮感知理論的信號獲取與傳輸方法中如圖1所示，通過觀測矩陣實(shí)現(xiàn)了傳統(tǒng)方法中采樣與壓縮兩個(gè)過程，因此能夠有效利用資源，提高信號獲取與傳輸?shù)男省?/p>

圖1 信號獲取與傳輸

信號獲取過程是測量矩陣壓縮觀測的過程，信號獲取的效果決定了信號能否被精確重構(gòu)，因此構(gòu)造合理的測量矩陣是信號能夠精確恢復(fù)的關(guān)鍵。針對測量矩陣的構(gòu)造過程，本文將從以下四個(gè)方面進(jìn)行闡述：測量矩陣構(gòu)造原則、測量矩陣產(chǎn)生方法、測量矩陣結(jié)構(gòu)設(shè)計(jì)和測量矩陣優(yōu)化方法。

2 測量矩陣構(gòu)造原則

對于可壓縮信號x，在Ψ域內(nèi)的K-稀疏信號為s，但s中非零元素的位置信息是未知的。感知因子Θ能夠保留稀疏信號s中的足夠信息，滿足信號重構(gòu)的要求。對于稀疏性能已知的可壓縮信號，變換域Ψ已知，因此測量矩陣的設(shè)計(jì)直接影響稀疏信號的感知效果，為進(jìn)一步簡化問題，假設(shè)可壓縮信號x為稀疏信號，因此變換域Ψ為單位陣I，感知因子Θ=ΦΨ=Φ，則壓縮感知過程如圖2所示。

圖2 壓縮感知測量過程

壓縮采樣后得到了M維向量y，測量矩陣構(gòu)造原則通過對測量矩陣Φ進(jìn)行約束，保證了原始信號x壓縮采樣后，依然能夠從降維信號y中得到準(zhǔn)確的恢復(fù)，例如高斯隨機(jī)矩陣，在K≤O(MlogN)的條件下，能夠以很高的概率滿足RIP[18]，RIP是測量矩陣構(gòu)造原則中的一種。圖3為不同條件下測量矩陣對稀疏信號的壓縮感知效果，圖3中原始信號為稀疏信號，仿真電壓信號在時(shí)域的變化趨勢，觀測矩陣為高斯隨機(jī)矩陣。當(dāng)觀測采樣后信號數(shù)據(jù)量由1 024減低到512時(shí)，測量矩陣能夠滿足RIP，信號重構(gòu)后標(biāo)準(zhǔn)差為2.75×10-13，如圖3(c)；當(dāng)壓縮采樣后信號數(shù)量由1 024降低到120時(shí)，測量矩陣不滿足RIP，信號重構(gòu)標(biāo)準(zhǔn)差為1.18，重構(gòu)信號嚴(yán)重失真，如圖3(b)。因此RIP能夠約束測量矩陣，保證原始信號的精確重構(gòu)，除了RIP之外，學(xué)者們對測量矩陣構(gòu)造原則的研究不斷深入，矩陣的構(gòu)造原則不斷豐富，包括RIP1、列相干性等。

圖3 稀疏信號壓縮感知

2.1 RIP

2.1.1RIC

對于可壓縮信號，Armin等[19]給出RIC的定義，若信號為時(shí)域稀疏信號，則RIC定義如下。

定義1 對于任意K=1，2，…，定義矩陣Φ的RICδK為滿足式(4)的最小值：

(4)

其中x為任意K-稀疏信號。

當(dāng)信號在時(shí)域不具有稀疏性時(shí)，需要找到信號的稀疏域，假設(shè)信號為Ψ域稀疏信號，則δK定義如下。

定義2 對于任意任意Ψ域K-稀疏信號，K=1，2，…，定義壓縮感知因子Θ的RICδK為滿足式(5)的最小值：

(5)

對于時(shí)域K-稀疏信號，通常情況下x中非零元素位置未知，要精確重構(gòu)原始信號，需定義δ2K如下。

定義3 對任意索引子集T?{1，2，…，N}，|T|≤2K，ΦT根據(jù)Φ中T所指示的相關(guān)列收縮獲得，c={xj∣j∈T}，則δ2K為滿足式(6)的最小值：

(6)

若信號為Ψ域稀疏信號，則δ2K定義與之相類似，但ΦT不能夠直接測量非稀疏信號，因此δ2K為滿足式(7)的最小值：

(7)

2.1.2RIP的條件描述

RIP通過限制觀測矩陣，保證了不同信號在壓縮觀測后能夠映射到不同的集合，同時(shí)充分保留原始信號的特性，因此能夠保證原始信號的唯一精確重構(gòu)。RIP的提出，是壓縮感知理論上的重要突破：一方面在滿足RIP的條件下，遠(yuǎn)低于奈奎斯特采樣定理的信號采樣存在精確重構(gòu)的可能，為壓縮感知理論提供基礎(chǔ)；另一方面，RIP能夠指導(dǎo)測量矩陣的構(gòu)造，成為部分矩陣構(gòu)造是否合理的評判標(biāo)準(zhǔn)。文獻(xiàn)[20]通過Johnson-Lindenstrauss引理[21]證明，許多密集隨機(jī)矩陣都能夠滿足RIP，保證了壓縮感知重構(gòu)效果。

2.2 RIP1性質(zhì)

滿足RIP條件的密集隨機(jī)矩陣能夠滿足信號重構(gòu)的需求，但是在測量以及重構(gòu)過程中，時(shí)間復(fù)雜度較高，例如基于l1范數(shù)的凸優(yōu)化重構(gòu)算法，重構(gòu)時(shí)間復(fù)雜度為O(n3)，測量個(gè)數(shù)為O(Klog(N/K))。當(dāng)原始信號個(gè)數(shù)N較大時(shí)，測量與重構(gòu)的過程的實(shí)現(xiàn)變得十分困難，為此學(xué)者提出構(gòu)造二進(jìn)制稀疏的測量矩陣，例如離散chirps[16]、邊膨脹圖[22]等，能夠在有限測量次數(shù)以及重構(gòu)時(shí)間復(fù)雜度的條件下精確重構(gòu)原始信號。但是在RIP的理論框架下，證明矩陣是否滿足RIP顯得十分困難，為此學(xué)者們提出RIP1[23]以及統(tǒng)計(jì)有限等距特性(StatisticRestrictedIsometryProperty，StRIP)和保證唯一性的統(tǒng)計(jì)有限等距特性(Uniqueness-guaranteedStatisticRestrictedIsometryProperty，UStRIP)[24]等。

基于邊膨脹圖的測量矩陣構(gòu)造方法被提出之后，Berinde等[23]證明了邊膨脹圖具有與RIP相類似的RIP1性質(zhì)。滿足RIP條件的測量矩陣通過限制壓縮采樣信號與原始信號的歐幾里得距離，保留了原始信號的有用信息，文獻(xiàn)[23]將l2范數(shù)延伸至l1范數(shù)，定義了RIP1性質(zhì)，并指出邊膨脹圖通過限制采樣信號與原始信號的曼哈頓距離，能夠保留原始信號中的有用信息。

定義4 RIP1性質(zhì)[25]。設(shè)Φ為邊膨脹圖V(K，ε)的M×N鄰接矩陣，那么對于任意K-稀疏信號x∈RN，滿足：

(1-2ε)d‖x‖1≤‖Φx‖1≤d‖x‖1

(8)

其中：d為Φ每列中1的個(gè)數(shù)，ε為常數(shù)。

RIP1性質(zhì)是RIP的擴(kuò)展，二者在本質(zhì)上保持著一致性。RIP1通過擴(kuò)展歐幾里得空間至曼哈頓空間，豐富了RIP的應(yīng)用范圍，建立了膨脹圖與壓縮感知之間的聯(lián)系，為邊膨脹圖的確定性矩陣構(gòu)造方式提供依據(jù)。同時(shí)，進(jìn)一步揭示了RIP的實(shí)質(zhì)，即通過保證壓縮觀測過程保留原始信號在歐幾里得空間的基本特性，保證原始信號具有精確重構(gòu)的可能。

2.3 列相干性

為避免RIP的復(fù)雜求解過程，Donoho等[26]從壓縮采樣后信號的精確重構(gòu)條件出發(fā)，提出利用列相干性優(yōu)化測量矩陣設(shè)計(jì)。

Tropp[27]提出，在冗余字典滿足特定列相干性條件的情況下，基追蹤(BasisPursuit,BP)、正交匹配追蹤(OrthogonalMatchingPursuit,OMP)等追蹤算法能夠?qū)υ夹盘枌?shí)現(xiàn)準(zhǔn)確的稀疏近似。在此基礎(chǔ)上，Donoho等[26]將這一結(jié)論應(yīng)用到壓縮感知矩陣優(yōu)化中，作為測量矩陣優(yōu)化標(biāo)準(zhǔn)，提出了基于列相干性的測量矩陣構(gòu)造原則。

定義5 對于任意字典Ψ，其互相干系數(shù)定義為μ以及累積互相干系數(shù)μ1定義為:

(9)

定理1 對于一般字典而言，其相干系數(shù)有下界：

(10)

若字典中所有原子都滿足等式條件，那么字典叫作等角緊框架。

對于可壓縮信號x，其在稀疏字典下的系數(shù)表示為：

x=ψs

(11)

若測量矩陣為Φ，則Θ=ΦΨ，列相干性條件通過感知因子的列相干系數(shù)定義，若滿足：

(12)

則矩陣Θ滿足列相干性條件。

相對于RIP，列相干性條件更為簡單，計(jì)算量相對較小，Rauhut等[28]證明，二者之間存在必然聯(lián)系，定理2對二者的關(guān)系進(jìn)行了描述，可以證明：在滿足列相干性條件的情況下，感知因子滿足RIP。

定理2 若字典互相干系數(shù)為μ以及累積互相干系數(shù)為μ1，則RICδK滿足下列約束：

δK≤μ1(K-1)≤(K-1)·μ

(13)

列相干性從信號重構(gòu)的角度，提出了在壓縮采樣過程，感知因子需要滿足的性質(zhì)。式(13)反映出列相干性與RIP之間的關(guān)系，列相干性條件通過限制感知因子不同列向量之間的相互關(guān)聯(lián)性，保證了感知因子能夠從各個(gè)維度對原始信號完成壓縮感知，因此能夠保證壓縮觀測的效果，為信號的精確重構(gòu)保留足夠的信息量。

2.4 StRIP/UStRIP性質(zhì)

針對RIC以及RIP的計(jì)算困難問題，Calderbank等提出統(tǒng)計(jì)有限等距特性(StRIP)以及保證唯一性的統(tǒng)計(jì)有限等距特性(UStRIP)[24]，同時(shí)，提出StRIP/UStRIP的簡單評判標(biāo)準(zhǔn)，通過判斷測量矩陣是否滿足特定標(biāo)準(zhǔn)，來確定測量矩陣是否滿足StRIP/UStRIP性質(zhì)，具有較強(qiáng)的可行性。

定義6Φ為M×N測量矩陣，對于任意K-稀疏信號x∈RN，若下列不等式能夠以超過1-δ的概率成立：

(1-ε)‖x‖2≤‖Φx/M‖2≤(1+ε)‖x‖2

(14)

則Φ為(K，ε，δ)-StRIP矩陣。

滿足上述條件的StRIP矩陣并不能保證滿足重構(gòu)信號的唯一性要求，因此定義嚴(yán)格約束的UStRIP矩陣。

定義7M×N階測量矩陣Φ為(K，ε，δ)-StRIP矩陣，若下列等式(15)能夠以超過1-δ的概率成立：

(15)

則Φ為(K，ε，δ)-UStRIP矩陣。

以上給出StRIP/UStRIP性質(zhì)的定義，但是在判斷矩陣是否滿足上述性質(zhì)過程中，仍然存在一定困難，為此給出η-StRIP-able矩陣的評判標(biāo)準(zhǔn)定義。

定義8 定義η-StRIP-able矩陣，0<η<1，為滿足以下標(biāo)準(zhǔn)的Φ矩陣。

1)Φ任意行向量正交，并且行元素求和為零。即：

(16)

(17)

其中：j為列索引，a、b為行索引。

2)Φ的任意列向量滿足“逐點(diǎn)相乘”，即對于任意列向量Φj″(a)(j″∈{1,2，…，N})，存在不同的列索引j，j′，對任意x滿足：

Φj″(a)=Φj′(a)Φj(a)

(18)

3)對任意j∈{2，…，N}滿足：

(19)

文獻(xiàn)[24]證明，滿足標(biāo)準(zhǔn)1)～3)的測量矩陣，具有統(tǒng)計(jì)意義上的有限等距性質(zhì)，即具有StRIP/UStRIP性質(zhì)。η-StRIP-able矩陣可行性強(qiáng)，成為許多二進(jìn)制稀疏編碼測量矩陣的評價(jià)指標(biāo)，例如離散Chirp編碼[16]、Bose-Chaudhuri-Hocquenghem編碼[24]等。

StRIP/UStRIP性質(zhì)通過縮小測量矩陣的應(yīng)用對象，簡化了測量矩陣的評價(jià)條件，降低了測量矩陣性質(zhì)的檢驗(yàn)難度。對于滿足條件的稀疏信號而言，簡單的評價(jià)條件具有與RIP類似的性質(zhì)，能夠保證測量矩陣在壓縮觀測過程中充分保留原始信號的有用信息，從而保證原始信號的唯一精確重構(gòu)。

除此之外，測量矩陣構(gòu)造原則還包括Spark理論[29]、零空間理論[30]等，Spark理論與列相干性理論相類似，利用矩陣的最小線性相關(guān)向量組的數(shù)目作為Spark常數(shù)，判斷是否滿足矩陣構(gòu)造條件。零空間理論通過判斷稀疏信號是否在感知因子的零空間內(nèi)，判斷解的唯一性。

3 測量矩陣產(chǎn)生方法

自壓縮感知理論產(chǎn)生以來，壓縮感知測量矩陣的構(gòu)造方法不斷豐富，產(chǎn)生的矩陣大致可以分成隨機(jī)測量矩陣、確定性測量矩陣兩大類。

3.1 隨機(jī)測量矩陣

3.1.1 高斯隨機(jī)矩陣

Candes等[2]證明，獨(dú)立同分布于高斯正態(tài)分布的高斯矩陣，在K≤O(MlogN)的條件下，能夠以很高的概率滿足RIP[18]，因此作為測量矩陣對K-稀疏信號進(jìn)行壓縮采樣后，能夠以很高的概率實(shí)現(xiàn)原始信號的精確重構(gòu)。

高斯隨機(jī)矩陣中，每個(gè)元素獨(dú)立同分布且均值為0、方差為1/n的正態(tài)分布，即：

Φi, j～N(0,1/M)

(20)

其中i、j表示矩陣的第i行、第j列。

3.1.2 貝努力隨機(jī)矩陣

與高斯矩陣性類似，獨(dú)立同分布的貝努力隨機(jī)矩陣能夠以很高的概率滿足RIP。貝努力矩陣為二值隨機(jī)矩陣，兩取值的概率相等，均為1/2，其元素取值可以描述為如下形式：

(21)

文獻(xiàn)[31]豐富了貝努力隨機(jī)矩陣的構(gòu)造方法，提出了通過部分哈達(dá)瑪集合、二進(jìn)制集合以及二者相組合的方式構(gòu)造貝努力隨機(jī)矩陣，并證明了這些方式能夠以超過1-2exp(-c1M)的概率滿足RIP。

與高斯隨機(jī)矩陣相比，貝努力隨機(jī)矩陣保留了高斯矩陣隨機(jī)性以及獨(dú)立性，能夠在相同的測量次數(shù)下滿足RIP，同時(shí)，貝努力隨機(jī)矩陣的數(shù)值變化少，結(jié)構(gòu)相對簡單。

除此之外，隨機(jī)矩陣還包括部分傅里葉矩陣[32]、部分正交矩陣[2]、稀疏隨機(jī)矩陣[33]等。這些隨機(jī)矩陣的獨(dú)立性較好，在一定程度上具有RIP，但是由于其隨機(jī)性，矩陣的硬件實(shí)現(xiàn)較為復(fù)雜，因此學(xué)者們研究確定性矩陣的構(gòu)造算法[34]，通過確定性矩陣來實(shí)現(xiàn)原始信號的壓縮觀測過程。

3.2 確定性測量矩陣

3.2.1 邊膨脹圖鄰接矩陣

Xu等[22]提出利用非平衡二部圖(如圖4)鄰接矩陣作為測量矩陣，應(yīng)用于壓縮觀測過程。非平衡二部圖直接模擬了壓縮感知壓縮觀測過程，其圖形分為左右兩部分，左子圖定義為A1，右子圖定義為A2，圖中包含有兩種節(jié)點(diǎn)。根據(jù)編碼理論的數(shù)值描述，將A1中節(jié)點(diǎn)定義為可變節(jié)點(diǎn)，A2中節(jié)點(diǎn)定義為奇偶校驗(yàn)節(jié)點(diǎn)。A1節(jié)點(diǎn)個(gè)數(shù)為N，對應(yīng)于壓縮感知原始信號x；A2節(jié)點(diǎn)個(gè)數(shù)為M，對應(yīng)于壓縮觀測后信號y。假設(shè)M≤N，A1、A2節(jié)點(diǎn)之間有邊線連接，連接關(guān)系對應(yīng)于鄰接矩陣C：

(22)

其中：i=1，2，…，M；j=1，2，…，N。

圖4 (k，ε)-邊膨脹圖

定理3 定義C(K，ε)-邊膨脹圖為形如圖4的非平衡二部圖V(A1，A2)，|A1|=N，|A2|=M，A1為可變節(jié)點(diǎn)，A2為奇偶檢驗(yàn)節(jié)點(diǎn)。假設(shè)A1的度為d，對于任意S?A1，若|S|≤K，則鄰居節(jié)點(diǎn)數(shù)N(S)滿足：N(S)>(1-ε)|S|。

Jarfarpour等[25]指出，在1≤K≤N/2的情況下，若(K，ε)-邊膨脹圖存在左子圖的度d以及右子圖大小M為：

(23)

則其鄰接矩陣C，對任意K-稀疏信號滿足RIP1性質(zhì)。

3.2.2 多項(xiàng)式確定性矩陣

基于壓縮感知理論，Devore[35]提出利用多項(xiàng)式映射矩陣構(gòu)造確定性矩陣，多項(xiàng)式確定性矩陣?yán)昧擞邢抻虻睦碚摗＜僭O(shè)素?cái)?shù)p，有限域F內(nèi)的元素為p的整數(shù)模，因此有限域F的階為p，即F域內(nèi)有p個(gè)元素，F(xiàn)可以表示為：{0，1，…，p-1}。構(gòu)建p×p矩陣E，因此E中含有p2個(gè)元素，E中元素的賦值方式如下。

定義整數(shù)r(0

(24)

Pr中多項(xiàng)式的個(gè)數(shù)為pr+1，對于任意Q∈Pr，把Q當(dāng)作F→F的映射函數(shù)，則E為t→Q(t)的映射矩陣，滿足：

Q(t)=Et*

(25)

式中t*表示t所有取值的集合。

將矩陣E的位置索引定義為：

(26)

則E中索引為(t,Q(t))位置處元素為1，其他位置為零，將E變換成p2×1的向量vQ，vQ中每p個(gè)元素中包含一個(gè)1，總共有p個(gè)1，多項(xiàng)式系數(shù)取值不同，產(chǎn)生不同的向量，因此當(dāng)系數(shù)取完時(shí)，可以構(gòu)造出pr+1個(gè)向量，將每一個(gè)的向量作為一列，構(gòu)造一個(gè)p2×pr+1的矩陣。

Devore[35]證明，按照上述方式構(gòu)造的確定性矩陣在稀疏信號稀疏度K

3.2.3 編碼矩陣

受有限域思想的啟發(fā)，學(xué)者們擴(kuò)展現(xiàn)有編碼方式的應(yīng)用領(lǐng)域，構(gòu)造用于壓縮觀測的測量矩陣。

Nam等[36]提出利用正交光碼(OpticalOrthogonalCode,OOC)構(gòu)造壓縮感知確定性矩陣，光正交碼的構(gòu)造由Brickell等[37]提出，廣泛應(yīng)用在光線信道的碼分多址信道設(shè)計(jì)，Nam等[36]通過OOC的循環(huán)位移以及哈達(dá)瑪矩陣的嵌套，構(gòu)造了一個(gè)三元實(shí)數(shù)矩陣，并證明了其優(yōu)越性能，OOC定義如下。

定義9 (n,ω,λ)光正交碼(OOC)為一組元素個(gè)數(shù)為n的二元序列，如{v(i)∣0≤i≤n-1}。每一序列的非零元素個(gè)數(shù)為ω，兩序列之間，滿足：

?τ∈[0,n-1],θv(i),v(j)(τ)≤λ;τ=0,若i=j

(27)

(28)

其中⊕表示模n加。

光正交碼的構(gòu)造利用了循環(huán)差集組G，G(n,ω)為ω個(gè)非零模n整數(shù)，任意兩個(gè)整數(shù)之間的差值互異。定義特征序列a={at∣t∈(0,1,…，n-1)}，若t∈G，則at=1，否則at=0，則a∈(n,ω,1)OOC。

在OOC碼的基礎(chǔ)上，測量矩陣的構(gòu)造方式如下：

1)生成S個(gè)0-1序列v(i)(0≤i≤n-1)，屬于(n,ω,λ)OOC碼，將每一序列v(i)進(jìn)行循環(huán)位移，共產(chǎn)生nS個(gè)序列，每一序列作為矩陣B的列向量。

2)構(gòu)造v×v(v=ω+δ,0≤δ≤ω)哈達(dá)瑪矩陣H，對于B的每一列，將元素1用H中不同的行替換，將元素0擴(kuò)展成長度為v的行，元素均為0，生成n×vnS矩陣Be。

除此之外，Bose-Chaudhuri-Hocquenghem編碼[38]、離散Chirp編碼[16]、代數(shù)編碼[39]、Reed-Muller編碼[24]、Berlekamp-Justesen編碼[40]以及各種低密度奇偶校驗(yàn)碼(Low-DensityParity-Check,LDPC)編碼[41]等，均被證明能夠作為壓縮感知測量矩陣，實(shí)現(xiàn)原始信號的精確重構(gòu)。

4 測量矩陣結(jié)構(gòu)設(shè)計(jì)

隨著壓縮感知測量矩陣構(gòu)造算法的不斷豐富，學(xué)者們提出通過優(yōu)化測量矩陣結(jié)構(gòu)設(shè)計(jì)的方法，綜合不同算法的優(yōu)勢，構(gòu)造更為合理的測量矩陣。Do等[42]提出的結(jié)構(gòu)隨機(jī)矩陣，通過隨機(jī)置換不同的列或?qū)⒃氐奈恢盟饕M(jìn)行翻轉(zhuǎn)，構(gòu)造一種正交矩陣，能夠保留原有高斯隨機(jī)矩陣以及貝努力隨機(jī)矩陣的所有優(yōu)勢。常用的測量矩陣的結(jié)構(gòu)設(shè)計(jì)方式主要包括托普利茲輪換矩陣、分塊矩陣、嵌套矩陣。

4.1 托普利茲輪換矩陣

托普利茲矩陣通過向量輪換的方式構(gòu)造矩陣[43]，這種方式的結(jié)構(gòu)化特點(diǎn)明顯，因此易于硬件實(shí)現(xiàn)，與獨(dú)立同分布的隨機(jī)矩陣相比，生成隨機(jī)變量數(shù)目少，運(yùn)算復(fù)雜度低，重構(gòu)算法相對簡單，因此輪換的矩陣構(gòu)造形式引起廣泛關(guān)注。在構(gòu)造過程中首先生成元素為±1貝努力分布的向量g=(g1,g2,…,gn)，并作為托普利茲矩陣的第一行向量，然后通過輪換的方式構(gòu)造矩陣其他行向量，最后按列進(jìn)行歸一化處理，歸一化后元素定義為u，矩陣如式(29)所示：

(29)

Bajwa等[44]提出，當(dāng)矩陣中元素獨(dú)立服從特定P(u)，且M≥K3ln(N/K)時(shí)，存在3K階RICδ3K∈(0,1/3)，滿足RIP。

托普利茲矩陣可以與特定序列相結(jié)合，生成具有托普利茲結(jié)構(gòu)的特定序列矩陣，如離散Chirps托普利茲矩陣[44]等。

4.2 分塊矩陣

大量滿足RIP的測量矩陣在結(jié)構(gòu)上表現(xiàn)為密集矩陣，這種矩陣在原始信號重構(gòu)上表現(xiàn)出優(yōu)異性能，但是在矩陣的構(gòu)造上，由于其密集性，存在存儲(chǔ)困難、計(jì)算復(fù)雜等問題。為此學(xué)者提出了分塊矩陣的結(jié)構(gòu)設(shè)計(jì)方式來克服上述缺陷。

文獻(xiàn)[19]提出分塊對角的矩陣結(jié)構(gòu)設(shè)計(jì)，采用亞高斯的隨機(jī)矩陣構(gòu)造方法，實(shí)現(xiàn)對稀疏信號的壓縮觀測，其模型可以描述為：

(30)

其中測量矩陣Φ為M×N矩陣。若式中每個(gè)矩陣塊Φj元素不同，則稱為不同塊對角矩陣(DistinctBlockDiagonal,DBD)，若相同則稱為重復(fù)塊對角矩陣(RepeatBlockDiagonal,RBD)。Armin等[19]指出，二者在保證測量次數(shù)的條件下，均能夠滿足RIP，實(shí)現(xiàn)與高密度亞高斯隨機(jī)矩陣幾乎相同的測量效果。

除此之外，分塊的矩陣結(jié)構(gòu)與循環(huán)、稀疏矩陣融合，產(chǎn)生分塊循環(huán)矩陣[46]、稀疏分塊循環(huán)矩陣[47]等，在一定程度上都能滿足RIP。

4.3 嵌套矩陣

列相干性是衡量測量矩陣性能的重要指標(biāo)，對于一些二元矩陣而言，由于元素具有非負(fù)性，因此低相干性的矩陣構(gòu)造顯得十分困難，這也使得矩陣維度受到極大限制。Amini等[38]從矩陣結(jié)構(gòu)角度提出了嵌套矩陣的構(gòu)造方法，能夠在保證矩陣列相干性的條件下擴(kuò)展矩陣維度，從而使得確定性矩陣的構(gòu)造方式更加靈活。

定理4 假設(shè)二元矩陣VM×N1，矩陣V中每一列具有相同的非零元素，元素個(gè)數(shù)為p，列相干系數(shù)為μ(V)，矩陣W為p×N2，矩陣中所有元素的絕對值相同，則可以構(gòu)造一個(gè)嵌套矩陣ZM×(N1N2)，列相干性系數(shù)滿足μ(Z)≤max(μ(V),μ(W))。

矩陣構(gòu)造過程如圖5所示，矩陣V中的第i個(gè)非零元素用矩陣W中的第i行代替，零元素延伸至相同維度，直至矩陣中非零元素替換完畢。

圖5 嵌套矩陣

根據(jù)定理4，通過嵌套列相干系數(shù)小的矩陣，可以實(shí)現(xiàn)在列相干系數(shù)不變的條件下擴(kuò)展矩陣維度，如嵌套哈達(dá)瑪矩陣[36]、離散傅里葉變換矩陣[48]等。

5 測量矩陣優(yōu)化方法

無論是確定性觀測矩陣還是隨機(jī)矩陣，由于受限于矩陣的構(gòu)造方式，觀測矩陣構(gòu)造完成后不再發(fā)生改變，但大部分矩陣仍然有很大的優(yōu)化空間，為此學(xué)者們從測量矩陣的性能出發(fā)，提出了對測量矩陣進(jìn)行優(yōu)化的方法，來進(jìn)一步改善壓縮觀測的效果。

5.1 基于Gram的優(yōu)化算法

Elad[49]提出把壓縮感知因子Θ的互相干系數(shù)作為目標(biāo)函數(shù)，通過構(gòu)造Gram矩陣以及閾值縮放處理方法降低測量矩陣Φ與稀疏域Ψ的相干性。根據(jù)互相干系數(shù)的定義，壓縮感知因子互相干系數(shù)為：

(31)

其中Θ經(jīng)過單位化處理，Θi為Θ的第i行，定義Gram矩陣Ξ為：

Ξ=ΘTΘ

(32)

感知因子的互相干系數(shù)的最大值為矩陣Ξ非對角位置元素的最大值，定義Ξ元素為Ξij，則μmax(Θ)=max(Ξij)(i≠j)。因此優(yōu)化過程中，根據(jù)預(yù)設(shè)閾值與矩陣Ξ中元素的大小關(guān)系，來對矩陣Ξ重新進(jìn)行賦值，已達(dá)到降低互相干系數(shù)的目的，整個(gè)優(yōu)化過程通過迭代次數(shù)控制，每次迭代過程中元素賦值方法為：

(33)

經(jīng)過優(yōu)化后，感知因子的互相干系數(shù)變小，測量矩陣與稀疏域的相關(guān)性減弱，文獻(xiàn)[49]表明，采用Elad優(yōu)化算法優(yōu)化的測量矩陣，在壓縮采樣后，重構(gòu)信號的精度得到提高。

Elad算法改善了測量矩陣壓縮采樣效果，但是其復(fù)雜度較高，為此在矩陣Ξ的基礎(chǔ)上，學(xué)者們進(jìn)一步優(yōu)化了目標(biāo)函數(shù)[50]。

對于滿足式(32)的矩陣Ξ，在壓縮感知因子的互相干性系數(shù)為0的理想狀態(tài)下，Ξ為單位陣：

Ξ=ΨTΦTΦΨ=I

(34)

對式(34)進(jìn)行變換得到：

ΨΨTΦTΦΨΨT=ΨΨT

(35)

(36)

式(36)通過改進(jìn)目標(biāo)函數(shù)，測量矩陣的優(yōu)化復(fù)雜度得到明顯降低，優(yōu)化求解的效率得到有效提高。

除此之外，基于Gram矩陣的優(yōu)化方法還包括交互投影法[51]、特征值分解[52]等。不同的優(yōu)化方法都是通過降低Gram矩陣非對角元素的大小，降低測量矩陣與稀疏域的相干性，從而保證感知因子具有較小的互相干系數(shù)，改善壓縮感知效果。

5.2 聯(lián)合優(yōu)化算法

基于Gram矩陣的優(yōu)化算法假設(shè)信號的稀疏變換域?yàn)楣潭ǖ恼换值洌请S著自適應(yīng)稀疏算法的產(chǎn)生，信號的稀疏域更多地轉(zhuǎn)向自適應(yīng)冗余字典。為此測量矩陣與稀疏字典聯(lián)合優(yōu)化的方法得到越來越多的關(guān)注，文獻(xiàn)[53]基于K-SVD算法，提出了稀疏字典-測量矩陣聯(lián)合優(yōu)化的算法，并應(yīng)用在圖像壓縮領(lǐng)域，取得了更高的重構(gòu)精度。

聯(lián)合優(yōu)化算法具體步驟為：

1)初始化稀疏字典Ψ。

2)固定稀疏字典Ψ，采用基于Gram矩陣的優(yōu)化方法，初始化測量矩陣Φ。

3)固定感知因子Θ，利用OMP算法求得稀疏分解系數(shù)矩陣。

4)利用K-SVD算法實(shí)現(xiàn)稀疏字典Ψ與測量矩陣Φ的迭代更新，直至滿足迭代條件。

除此之外，聯(lián)合優(yōu)化算法還包括基于梯度下降的聯(lián)合優(yōu)化[54]、基于奇異值分解的聯(lián)合優(yōu)化[55]等。聯(lián)合優(yōu)化算法引用了自適應(yīng)稀疏字典的學(xué)習(xí)訓(xùn)練過程，通過不斷的迭代，構(gòu)建了一個(gè)與原始信號相適應(yīng)的稀疏字典以及觀測矩陣，因此壓縮感知效果得到改善，但是相比非聯(lián)合優(yōu)化算法而言，算法復(fù)雜度提高，優(yōu)化時(shí)間消耗增加。

6 測量矩陣構(gòu)造發(fā)展方向探討

測量矩陣構(gòu)造為基于壓縮感知理論的信號采集與傳輸提供了支撐，然而目前測量矩陣構(gòu)造方式并不完善，仍然有一些問題需要在今后的研究中取得突破，為此在總結(jié)國內(nèi)外現(xiàn)有研究成果的前提下，對測量矩陣設(shè)計(jì)的發(fā)展方向進(jìn)行展望：

1)在測量矩陣構(gòu)造原則上，RIP是測量矩陣設(shè)計(jì)的必要條件，但是無法有效指導(dǎo)測量矩陣構(gòu)造，列相干性條件與RIP存在一致性，其計(jì)算簡單、指導(dǎo)性強(qiáng)，并且基于列相干性條件的矩陣訓(xùn)練方法被證明能夠用來優(yōu)化測量矩陣，因此列相干性條件在具體指導(dǎo)測量矩陣構(gòu)造中將發(fā)揮越來越大的作用；另一方面J-R引理在證明矩陣RIP上體現(xiàn)出巨大優(yōu)勢，因此其作為評價(jià)矩陣優(yōu)劣的簡單途徑，將得到廣泛應(yīng)用。

2)在測量矩陣產(chǎn)生方法上，確定性矩陣無疑將成為研究熱點(diǎn)，現(xiàn)有確定性矩陣在部分信號的重構(gòu)精度以及普遍適用性上與隨機(jī)矩陣稍顯不足，但是其構(gòu)造復(fù)雜度低、硬件實(shí)現(xiàn)簡單，已經(jīng)得到學(xué)者的廣泛關(guān)注，因此在保證重構(gòu)精度的基礎(chǔ)上，更加適用、簡單的確定性矩陣是測量矩陣產(chǎn)生方法的發(fā)展趨勢。

3)測量矩陣結(jié)構(gòu)設(shè)計(jì)能夠彌補(bǔ)不同測量矩陣產(chǎn)生方法的不足，從而起到優(yōu)化測量矩陣的作用，現(xiàn)階段，矩陣結(jié)構(gòu)設(shè)計(jì)方法相對較少，理論基礎(chǔ)相對薄弱，因此針對測量矩陣的結(jié)構(gòu)設(shè)計(jì)方法有待于進(jìn)一步完善，相應(yīng)的理論有待于進(jìn)一步研究。

4)對于按照特定方式構(gòu)造的測量矩陣，矩陣優(yōu)化方法是對其性能的一種完善，能夠進(jìn)一步改善測量矩陣壓縮觀測效果。隨著自適應(yīng)稀疏分解算法的不斷成熟，測量矩陣與稀疏字典聯(lián)合優(yōu)化的方法將得到越來越多的重視，并逐漸體現(xiàn)出單一測量矩陣優(yōu)化所不具有的優(yōu)化效果。但由于現(xiàn)有聯(lián)合優(yōu)化算法的復(fù)雜度較高，聯(lián)合優(yōu)化算法仍處于理論研究階段，因此未來高效率的聯(lián)合優(yōu)化算法將成為學(xué)者們的研究熱點(diǎn)。

7 結(jié)語

壓縮感知測量矩陣設(shè)計(jì)是壓縮感知理論框架的核心，本文在對國內(nèi)外學(xué)者眾多文獻(xiàn)梳理研究的前提下，對測量矩陣構(gòu)造進(jìn)行系統(tǒng)介紹，分析現(xiàn)有研究成果，從測量矩陣構(gòu)造原則、測量矩陣產(chǎn)生方法、測量矩陣結(jié)構(gòu)設(shè)計(jì)、測量矩陣優(yōu)化方法等角度比較不同方法、理論的優(yōu)缺點(diǎn)，為后續(xù)壓縮感知測量矩陣構(gòu)造提供了參考?，F(xiàn)階段，低復(fù)雜度的測量矩陣構(gòu)造方式、測量矩陣的優(yōu)化方法大多處于理論研究階段，在實(shí)際應(yīng)用過程中壓縮感知效果、適用性有待于進(jìn)一步檢驗(yàn)與提高。此外，本文著重對測量矩陣的構(gòu)造進(jìn)行了介紹，而壓縮感知效果是稀疏字典、測量矩陣、重構(gòu)算法共同作用的結(jié)果，因此構(gòu)建與稀疏字典、重構(gòu)算法相適應(yīng)的測量矩陣有待于進(jìn)一步研究。

)

[1]CANDESEJ,ROMBERGJ.Quantitativerobustuncertaintyprinciplesandoptimallysparsedecompositions[J].FoundationofComputationalMathematics, 2006, 6(2): 227-254.

[2]CANDESEJ,ROMBERGJK,TAOT.Robustuncertaintyprinciples:exactsignalreconstructionfromhighincompletefrequencyinformation[J].IEEETransactionsonInformationTheory, 2006, 52(2): 489-509.

[3]CANDESEJ,ROMBERGJK,TAOT.Stablesignalrecoveryfromincompleteandinaccuratemeasurements[J].CommunicationsonPureandAppliedMathematics, 2006, 59(8): 1207-1223.

[4]BOUCHHIMAB,AMARAR,ALOUANETH.Designofoptimalmatricesforcompressivesensing:applicationtoenvironmentalsounds[C]//Proceedingsofthe2015SignalProcessingConference.Piscataway,NJ:IEEE, 2015: 130-134.

[5]DONOHODL.Compressedsensing[J].IEEETransactionsonInformationTheory, 2006, 52(4): 1289-1306.

[6] 王強(qiáng),李佳,沈毅.壓縮感知中確定性測量矩陣構(gòu)造算法綜述[J].電子學(xué)報(bào),2013,41(10):2041-2050.(WANGQ,LIJ,SHENY.Asurveyondeterministicmeasurementmatrixconstructionalgorithmsincompressivesensing[J].ActaElectronicaSinica, 2013, 41(10): 2041-2050.)

[7] 焦李成,楊淑媛,劉芳,等.壓縮感知回顧與展望[J].電子學(xué)報(bào),2011,39(7):1651-1662.(JIAOLC,YANGSY,LIUF,etal.Developmentandprospectofcompressivesensing[J].ActaElectronicaSinica, 2011, 39(7): 1651-1662.)

[8]ELADM,AHARONM.Imagedenoisingviasparseandredundantrepresentationsoverlearneddictionaries[J].IEEETransactionsonInformationTheory, 2006, 15(12): 3736-3745.

[9]AHARONM,ELADM,BRUCKSTEINAM.TheK-SVD: an algorithm for designing of overcomplete dictionaries for sparse representations [J].IEEE Transactions on Image Processing, 2006, 54(11): 4311-4322.

[10] CANDES E J, TAO T.Decoding by linear programming [J].IEEE Transactions on Information Theory, 2005, 51(12): 4203-4215.

[11] CANDES E J.The restricted isometry property and its implication for compressed sensing [J].Comtes Rendus Mathematique, 2008, 346(9/10): 589-592.

[12] MALLAT S, ZHANG Z F.Matching pursuits with time frequency dictionaries [J].IEEE Transactions on Signal Processing, 1993, 41(12): 3397-3415.

[13] TROPP J A, GILBERT A C.Signal recovery from random measurement via orthogonal matching pursuit [J].IEEE Transactions on Information Theory, 2007, 53(12): 4655-4666.

[14] NEEDELL D, TROPP J A.CoSaMP: iterative signal recovery from incomplete and inaccurate samples [J].Applied and Computational Harmonic Analysis, 2008, 26(3): 301-321.

[15] CHEN S B, DONOHO D L, SAUNDERS M A.Atomic decomposition by basis pursuit [J].SIAM Journal on Scientific Computing, 1998, 20(1): 33-61.

[16] APPLEBAUM L, HOWARD S, SEARLE S, et al.Chirp sensing codes: deterministic compressed sensing measurements for fast recovery [J].Applied and Computational Harmonic Analysis, 2009, 26(2): 283-290.

[17] ROMBERG J.Compressive sensing by random convolution [J].SIAM Journal on Imaging Sciences, 2009, 2(4): 1098-1128.

[18] CANDES E J, TAO T.Near-optimal signal recovery from random projections: universal encoding strategies? [J].IEEE Transactions on Information Theory, 2006, 52(12): 5406-5425.

[19] ARMIN E, LUN Y H, CHRISTOPHER J R, et al.The restricted isometry property for random block diagonal matrices [J].Applied & Computational Harmonic Analysis, 2015, 38(1): 1-31.

[20] BARANIUK R, DAVENPORT M, DEVORE R, et al.A simple proof of the restricted isometry property for random matrices [J].Constructive Approximation, 2008, 28(3): 253-263.

[21] JOHNSON W, LINDENSTRAUSS J.Extensions of Lipschitz maps into a Hilbert space [J].Contemporary Mathematics, 1984, 26: 189-206.

[22] XU W, HASSIBI B.Efficient compressive sensing with deterministic guarantees using expander graphs [C]// ITW’07: Proceedings of the 2007 Information Theory Workshop.Piscataway, NJ: IEEE, 2007: 414-419.

[23] BERINDE R, GILBERT A C, INDYK P, et al.Combining geometry and combinatorics: a unified approach to sparse signal [EB/OL].[2016-05-15].https://arxiv.org/abs/0804.4666.

[24] CALDERBANK R, HOWARD S, JAFARPOUR S.Construction of a large class of deterministic sensing matrices that satisfy a statistical isometry property [J].IEEE Journal of Selected Topics in Signal Processing, 2010, 4(2): 358-374.

[25] RAGINSKY M, JAFARPOUR S, HARMANY Z T, et al.Performance bounds for expander-based compressed sensing in Poisson noise [J].IEEE Transactions on Signal Processing, 2011, 59(9): 4139-4153.

[26] DONOHO D L, ELAD M.Optimally sparse representation in general (nonorthogonal) dictionaries via l1 minimization [J].Proceedings of the National Academy of Sciences, 2003, 100(5): 2197-2202.

[27] TROPP J A.Greed is good: algorithmic results for sparse approximation [J].IEEE Transactions on Information Theory, 2004, 50(10): 2231-2242.

[28] RAUHUT H, SCHNASS K, VANDERGHEYNST P.Compressed sensing and redundant dictionaries [J].IEEE Transactions on Information Theory, 2008, 54(5): 2210-2219.

[29] ELAD M, BRUCKSTEIN A M.A generalized uncertainty principle and sparse representation in pairs bases [J].IEEE Transactions on Information Theory, 2002, 48(9): 2558-2567.

[30] KASHIN B S, TEMLYAKOV V N.A remark on compressed sensing [J].Mathematics and Statistics, 2007, 42(5/6): 748-755.

[31] ZHANG G, JIAO S, XU X, et al.Compressed sensing and reconstruction with Bernoulli matrices [C]// Proceedings of the 2010 International Conference on Information and Automation.Piscataway, NJ: IEEE, 2010: 455-460

[32] GILBERT A C, GUHA S, INDYK P.Near-optimal sparse Fourier representation via sampling [C]// Proceedings on the 34th Annual ACM Symposium on Theory of Computing.New York: ACM, 2006: 152-161.

[33] BERINDE R, INDYK P.Sparse recovery using sparse random matrices [C]// LATIN 2010: Proceedings of the 9th Latin American Symposium on Theoretical Informatics, LNCS 6034.Berlin: Springer, 2010: 157-157.

[34] ZENG L, ZHANG X, CHEN L, et al.Deterministic construction of Toeplitzed structurally chaotic matrix for compressed sensing [J].Circuits, Systems, and Signal Processing, 2015, 34(3):797-813.

[35] DEVORE R A.Deterministic construction of compressed sensing [J].Journal of Complexity, 2007, 23(4/5/6): 918-925.

[36] NAM Y Y, NA Z.Deterministic construction of real-valued ternary sensing matrices using optical orthogonal codes [J].IEEE Signal Processing Letters, 2013, 20(11): 1106-1109.

[37] BRICKELL E F, WEI V K.Optical orthogonal codes and cyclic block designs [J].Congressus Numerantium, 1987, 58: 175-192.

[38] AMINI A, MONTAZERHODJAT V, MARVASTI F.Matrices with small coherence using parry block codes [J].IEEE Transactions on Signal Processing, 2012, 60(1): 172-181.

[39] LI S X, GAO F, GE G N, et al.Deterministic construction of compressed sensing matrices via algebraic curves [J].IEEE Transactions on Information Theory, 2012, 58(8): 5035-5041.

[40] GE X, XIA S T.LDPC codes based on Berlekamp-Justesen codes with large stopping distances [C]// ITW’06: Proceedings of the 2006 IEEE Information Theory Workshop.Piscataway, NJ: IEEE, 2006: 214-218.

[41] DIMAKIS A G, SMARANDACHE R, VONTOBEL P O.LDPC codes for compressed sensing [J].IEEE Transactions on Information Theory, 2010, 58(5): 3093-3114.

[42] DO T T, TRAN T D, LU G.Fast compressive sampling with structurally random matrices [C]// Proceedings of the 2008 IEEE International Conference on Acoustics.Piscataway, NJ: IEEE, 2008: 3369-3372.

[43] 李浩.用于壓縮感知的確定性測量矩陣研究[D].北京：北京交通大學(xué),2011:26-38.(LI H.Research on deterministic measurement matrix for compressed sensing [D].Beijing: Beijing Jiaotong University, 2011: 26-38.)

[44] BAJWA W U, HAUPT J D, RAZ G M, et al.Toeplitz-structured compressed sensing matrices [C]// SSP’ 07: Proceedings of the 2007 IEEE/SP 14th Workshop on Statistical Signal Processing.Washington, DC: IEEE Computer Society, 2007: 294-298.

[45] SALIGRAMA V.Deterministic designs with deterministic guarantees: Toeplitz compressed sensing matrices, sequence design and system ID [J].IEEE Transactions on Information Theory, 2012, 99(PP): 1-1.

[46] SEBERT F, ZOU Y M, YING L.Toeplitz block matrices in compressed sensing and their applications in imagine [C]// Proceedings of the 2008 International Conference on Information Technology and Applications in Biomedicine, Piscataway, NJ: IEEE, 2008: 47-50.

[47] SUN J M, WANG S, DONG Y.Sparse block circulant matrices for compressed sensing [J].IET Communications, 2013, 7(13): 1412-1418.

[48] 夏樹濤,劉璐,劉鑫吉.基于Berlekamp-Justesen碼的壓縮感知確定性測量矩陣的構(gòu)造[J].電子與信息學(xué)報(bào),2015,37(4):763-769.(XIA S T, LIU L, LIU X J.Deterministic constructions of compressive sensing matrices based on Berlekamp-Justesen codes [J].Journal of Electronics & Information Technology, 2015, 37(4): 763-769.

[49] ELAD M.Optimized projections for compressed sensing [J].IEEE Transactions on Signal Processing, 2007, 55(12): 5695-5702.

[50] 張勁東,張弓,潘匯,等.基于濾波器結(jié)構(gòu)的壓縮感知雷達(dá)感知矩陣優(yōu)化[J].航空學(xué)報(bào),2013,34(4):866-868.(ZHANG J D, ZHANG G, PAN H, et al.Optimized sensing matrix design of filter structure based compressed sensing radar [J].Acta Aeeronautica et Astronautica Sinica, 2013, 34(4): 866-868.)

[51] LI B, SHEN Y, LI J.Dictionaries construction using alternating projection method in compressive sensing [J].IEEE Signal Processing Letters, 2011, 18(11): 662-666.

[52] 趙瑞珍,秦周,胡紹海,等.一種特征值分解的測量矩陣優(yōu)化方法[J].信號處理,2012,38(5):654-656.(ZHAO R Z, QIN Z, HU S H, et al.An optimization method for measurement matrix based on eigenvalue decomposition [J].Signal Processing, 2012, 38(5): 654-656.)

[53] DUARTE-CARVAJALINO J M, SAPIRO G.Learning to sense sparse signal： simultaneous sensing matrix and sparsifying dictionary optimization [J].IEEE Transactions on Imagine Processing, 2009, 18(7): 1395-1408.

[54] ABOLGHASEMI V, SAIDEH F, BAHADOR M.On optimization of the measurement matrix for compressive sensing [C]// EUSIPCO 2010: Proceedings of the 18th European Signal Processing Conference, 2010:23-27.

[55] ZHANG J D, ZHU D Y, ZHANG G.Adaptive compressed sensing radar oriented towards cognitive detection in dynamic sparse target scene [J].IEEE Transactions on Signal Processing, 2012, 60(4): 1718-1729.

This work is supported by the Natural Science Foundation of China (E51305454).

WANG Qiang, born in 1992, M.S.candidate.His research interests include signal processing, data compression.

ZHANG Peilin, born in 1955, Ph.D., professor.His research interests include machine condition monitoring, fault diagnosis.

WANG Huaiguang, born in 1979, Ph.D., lecturer.His research interests include signal processing, data compression.

YANG Wangcan, born in 1988, Ph.D.candidate.His research interests include fault diagnosis, pattern recognition.

CHEN Yanlong, born in 1987, Ph.D.candidate.His research interests include fault diagnosis, signal processing.

Survey on construction of measurement matrices in compressive sensing

WANG Qiang, ZHANG Peilin*, WANG Huaiguang, YANG Wangcan, CHEN Yanlong

(DepartmentofVehiclesandElectricalEngineering,OrdnanceEngineeringCollege,ShijiazhuangHebei050003,China)

The construction of measurement matrix in compressive sensing varies widely and is on the development constantly.In order to sort out the research results and acquire the development trend of measurement matrix, the process of measurement matrix construction was introduced systematically.Firstly, compared with the traditional signal acquisition theory, the advantages of high resource utilization and small storage space were expounded.Secondly, on the basis of the framework of compressive sensing and focusing on four aspects: the construction principle, the generation method, the structure design of measurement matrix and the optimal method, the construction of measurement matrix in compressive sensing was summarized, and advantages of different principles, generations and structures were introduced in detail.Finally, based on the research results, the development directions of measurement matrix were prospected.

Compressive Sensing (CS); measurement matrix; Restricted Isometry Property (RIP); signal reconstruction; signal acquisition

2016-08-06;

2016-09-06。 基金項(xiàng)目:國家自然科學(xué)基金資助項(xiàng)目(E51305454)。

王強(qiáng)(1992—)，男，山東棲霞人，碩士研究生，主要研究方向：信號處理、數(shù)據(jù)壓縮； 張培林(1955—)，男，安徽太和人，教授，博士，主要研究方向：機(jī)械狀態(tài)監(jiān)測、故障診斷； 王懷光(1979—)，男，河北石家莊人，講師，博士，主要研究方向：信號處理、數(shù)據(jù)壓縮； 楊望燦(1988—)，男，河北辛集人，博士研究生，主要研究方向：故障診斷、模式識別； 陳彥龍(1987—)，男，四川資陽人，博士研究生，主要研究方向：故障診斷、信號處理。

1001-9081(2017)01-0188-09

10.11772/j.issn.1001-9081.2017.01.0188

TP301.6

A