李　博，李云鶴，李廣才

（肇慶學(xué)院 電子信息與機電工程學(xué)院，廣東 肇慶　526061）

1　概述

由采樣定理知，只有當(dāng)采樣率大于2個信號帶寬時，才能知道相似信號可用高質(zhì)量的方法進(jìn)行恢復(fù).這些年隨著信息量的增加，信息傳送的帶寬得到了提高，對信息獲取時的采樣和處理速度要求也變得越來越高.Donoho、Candes和其他專家學(xué)者[1-3]在其研究中詳細(xì)說明了壓縮傳感理論，其采樣標(biāo)準(zhǔn)要比Nyquist低很多，用這種方法重建原始信號非常可靠.信號復(fù)原是重要的，這一點無可爭議，而其難點在于將理論付諸實踐.貪心算法、凸優(yōu)化算法[4-5]和組合優(yōu)化算法[6-7]都是用于理論的通用方法.這些算法犧牲了復(fù)原的精確性和復(fù)雜性，使用迭代來持續(xù)更新支撐集，最終接近原始信號，其中包含了很多門類，主要包含倒溯法（一種基于正交匹配追蹤算法OMP的算法）[8-9].倒溯法重構(gòu)的精確性相對較高，子空間追蹤算法在此門類中為代表性方法，其在各方面均有許多優(yōu)勢：較低的復(fù)雜度和較高的精確度；但是，與規(guī)則OMP即ROMP算法[10]相比，信號已知稀疏度是精確重構(gòu)原始信號的基本條件.其1次迭代會被投影2次，投影的復(fù)雜性隨著稀疏度的提高而急劇上升，從而對重構(gòu)信號的質(zhì)量造成嚴(yán)重影響并將其變小.

為彌補以上缺陷，本文設(shè)計了一個應(yīng)用范圍較大并且高效的信號重構(gòu)法.通過快速稀疏度評估的方法處理稀疏度未知的信號；同時，在重構(gòu)過程中，避免了迭代時產(chǎn)生的觀測向量的投影運行，進(jìn)一步減少運行的復(fù)雜性.在深入總結(jié)現(xiàn)存指數(shù)后，提供了更全面和科學(xué)的評估分析指數(shù)，以此來評估帶缺陷的當(dāng)前重構(gòu)算法的性能.

2　本文算法

考慮到目前的方法只能重構(gòu)稀疏度已知的信號，筆者在文中設(shè)計的重構(gòu)法中使用一個快速評估方法，它可以有效提高疏密度評估的效率，在很大程度上縮短疏密度預(yù)估值與實際值的差距.另外，文中的算法儲存了候選集觀測向量的投影過程，這個候選集是傳統(tǒng)追蹤算法的一部分.通過這種方法，其集合被全部儲存起來；避免了支撐集上的投影步驟，讓這個步驟最終簡單易懂.

2.1　疏密度的評估

首先在這里詳細(xì)說明評估方法.在將被重構(gòu)的信號中，受限等距性質(zhì)是重構(gòu)的基礎(chǔ).該性質(zhì)表現(xiàn)如下：如果向量x滿足‖x‖0≤K,那就有一個矩陣A滿足如下條件：

A滿足(K,d)參數(shù)條件下的受限等距性.在方程中，‖x‖2是xl2的范數(shù)，得出不等式(1)的最小值dK,0＜dK＜1.

上述性質(zhì)導(dǎo)出了下列法則1.

法則1假設(shè)信號稀疏度為k,A滿足(K,d)參數(shù)條件下的受限等距性.若k=K,則

公式（2）中，|(A,y)|表示向量y和第i個A之間的向量絕對值，G0是k的最大值，AG0是由A和G0組成的子矩陣.

例1假設(shè)信號稀疏度是k,A滿足基于(K,δ)系數(shù)的受限等距性質(zhì)，當(dāng)k3K,則

根據(jù)例2的逆否命題，可得推論1.

推論1假設(shè)A符合(K,δK)的特性.當(dāng)預(yù)估稀疏度

法則1可以根據(jù)推論1和例1證明.

使ui=在遞減的途徑中安排ui,形成一個新的數(shù)列.然而這樣方程（3）可以按照如下描述：

使用符合公式（4）的最大數(shù)k作為稀疏度K的下限，記為Kmin;符合公式（4）的最大值表示下舍入.

與之前的方法作比較，僅總結(jié)了U′中元素的平方數(shù)，將公式（4）中第1次和最后1次的元素數(shù)量記為Kmin和Kmax,這樣就避免了檢驗，因此花費的時間減少了很多.在相關(guān)專家的研究結(jié)果中[11-12]，當(dāng)稀疏度處于上限或下限時，應(yīng)該停止運行，因為這會造成稀疏度預(yù)估值的誤差較大.比如，當(dāng)實驗性稀疏度接近下限時，實際值就接近上限，將代入就可以終止上述情況，使預(yù)測結(jié)果更精確.

2.2　算法的迭代過程

一般在迭代算法中，迭代過程分別在候選集和支撐集上，必須要介入1次關(guān)聯(lián)最大化（correlation maximum，簡稱CM），還必須經(jīng)過1次投影運行.為了簡化描述，使用proj(Cn)和proj(Sn)來表示第n個迭代中，候選集Cn和支撐集Sn各自的觀測向量y的投影過程[9].相關(guān)專家和學(xué)者表示迭代過程的復(fù)雜性主要在于CM，但并未注意重構(gòu)方法上第2個投影的嚴(yán)重干涉.針對這個，本文專門分析了單個迭代過程的復(fù)雜性.當(dāng)y和A分別為M×1和M×N維度矩陣時，每個CM過程必須要經(jīng)過M×N次的相乘，O(MN)表示其復(fù)雜性.通過MGS（modified gram schmidt）方法[13-14]得出proj(Sn),復(fù)雜性為O(MN2).假設(shè)在第n個迭代候選集中有Vn個元素，則在此背景下K≤Vn≤2K,O(MV2n)為計算得出proj(Cn)的復(fù)雜性.整個迭代的計算復(fù)雜性為O(MN+Mv2n+MK2).當(dāng)K較小時，可以將其視為O(MN);當(dāng)K持續(xù)增加，上面第2個投影的復(fù)雜性將急劇上升.這個時候，它對重構(gòu)法復(fù)雜性的影響要比CM大很多.

本文設(shè)計的重構(gòu)方法理論如圖1所示：在實現(xiàn)重構(gòu)算法集合保持基本不變的情況下，減少迭代中的投影次數(shù)，使算法的復(fù)雜性降低.首先使用預(yù)估算法決定K后，執(zhí)行迭代重構(gòu).在第n個迭代中，每個A列的最后1個迭代的關(guān)聯(lián)余量rn-1,加上關(guān)聯(lián)系數(shù)絕對值的最大數(shù)K和最后迭代的sn-1,根據(jù)這個條件形成Cn.然后把y投影到Cn,使用投影絕對值的最大系數(shù)k作為這一輪的Sn,使用Sn的投影值作為此次迭代中重構(gòu)信號Zn的非零部分ZSn;可以決定當(dāng)前迭代余量rn=y-ASnZSn,當(dāng)它滿足|rn|＞|rn-1|時，迭代過程終止；若其不滿足這個條件，則繼續(xù)下一個迭代.當(dāng)Sn是指數(shù)列時，ASn是A中產(chǎn)生的子矩陣.圖1展示了這個特殊演變的步驟.

圖1　設(shè)計算法的基本步驟

3　算法的重構(gòu)性能指數(shù)

稀疏信號重構(gòu)過程中，會造成重構(gòu)幅度和位置的2個誤差，如圖2所示.圖2a是原始稀疏信號，其長度和稀疏度分別為10和4；圖2b和圖2c為當(dāng)幅度和位置誤差分別發(fā)生時的重構(gòu)稀疏信號.將稀疏信號幅度中非零部分的重構(gòu)可能性定義為I，將II定義成整個稀疏信號的重構(gòu)可能性.當(dāng)│重構(gòu)信號-原始信號│不大于10-8時，那么構(gòu)建成功.重構(gòu)信號如圖2b和圖2c所示，相應(yīng)的重構(gòu)可能性I和II分別為0.75和0.9；0.75和0.8.主要方法是使用I作為評估算法重構(gòu)性能的指數(shù)，但是在研究中發(fā)現(xiàn)：當(dāng)I相同時，重構(gòu)誤差不同，II也會不同.無法說明這2個重構(gòu)誤差，所以無法僅通過I來判斷整個系數(shù)信號的重構(gòu)可能性.

在重構(gòu)過程中，最好的結(jié)果是重構(gòu)了整個系數(shù)信號，而不僅僅只重構(gòu)非零部分.為解決這個問題，將II用作評估指數(shù)來判斷文中方法的重構(gòu)性能，下面進(jìn)行模擬分析.

圖2　重構(gòu)信號的2個誤差

4　稀疏度的評估

首先，通過仿真判斷本文推薦的稀疏度預(yù)估法的精確度（下文稱為OASP）.實驗中，采樣次數(shù)M和信號長度分別為128和256；所觀察的矩陣是一個M×N維度的高斯隨機矩陣；其結(jié)果為1 000次模擬輸出的平均數(shù).不同K值下稀疏度預(yù)估的對比情況如圖3所示，圖3對比了K=36時各個δk值上的估值.通過分析，得知當(dāng)δk=0.15時，估值和實際值的差距為最小，而且比較穩(wěn)定.

圖3　不同K值下稀疏度預(yù)估的對比

2種方法模擬次數(shù)的對比如表1所示.對比2種不同方法的模擬次數(shù)，也就是1 000次Monte Carlo實驗的總和.實驗中，N=512,M=256,當(dāng)結(jié)束條件相同時，測試2個不同信號重構(gòu)算法的次數(shù).通過對比OASP和SP，從表1中可以發(fā)現(xiàn)，在任何稀疏度之下，前一個算法的時間要比后者短，而且隨著K的持續(xù)增加，前者減少的時間變得愈加明顯.

對比獲得結(jié)束條件相同的2個算法的迭代次數(shù)，情況如圖4所示.實驗中，N=256，M=138，結(jié)果為500次Monte Carlo實驗輸出的平均值.由圖4可以發(fā)現(xiàn)：當(dāng)K較小時，2個獲得結(jié)束條件相同的算法的迭代次數(shù)幾乎相同，接近log(K).當(dāng)K持續(xù)增加時，前一個算法的迭代次數(shù)的幅度也逐漸增加時，而后一個算法正好相反，因此，前者節(jié)約的時間將隨著K的逐漸增加而增加.

表1　2種方法的模擬次數(shù)的對比

分析不同算法中不同K值下的II的對比情況，如圖 5所示.實驗中，N=256,M=128.當(dāng)|重構(gòu)信號-原始信號|≤10-12時，重構(gòu)成功，其結(jié)果是1 000次Monte Carlo實驗的輸出平均值.同時，分析了許多其他方法，比如SAMP（稀疏度適應(yīng)性配對追求法）[15-16].在圖5中發(fā)現(xiàn)ROMP，OMP和SAMP在K=56的時候會逐漸喪失其性能；此時，SP算法具有良好的重構(gòu)能力，而在K=56時開始喪失；注意到K=60時OASP喪失了其效果.根據(jù)上述對比，發(fā)現(xiàn)本文詳細(xì)描述的算法具備最明顯的優(yōu)勢，在稀疏信號的重構(gòu)完成中具有最高效用.盡管本文展示的算法擁有明顯優(yōu)勢，隨著K進(jìn)一步增加，II的減少幅度很大，但是SAMP的減少幅度相對較低.

圖4　迭代次數(shù)

圖5　不同算法的重構(gòu)可能性II的對比

5　總結(jié)

為有效解決未知稀疏度壓縮信號的快速重構(gòu)，筆者在本文中提出了一個應(yīng)用范圍寬闊、效果卓越的信號重構(gòu)方法.以等距性質(zhì)為基礎(chǔ)，獲得壓縮信號的上、下邊界，而最接近其中間值的整數(shù)為信號稀疏度的預(yù)估值；減少迭代中投影在支撐集上觀測向量的次數(shù)，從而降低此方法的算法復(fù)雜性；推出了一個可以反映整個信號重構(gòu)可能性的預(yù)估系統(tǒng)，該系統(tǒng)證實并分析了該方法的效果.實驗顯示該方法有效地實現(xiàn)了未知稀疏度信號的快速重建，而且其重構(gòu)的成功可能性要比當(dāng)前的倒溯法要高.

參考文獻(xiàn)：

[1]LV Z.Managing big city information based on WebVRGIS[J].IEEEAccess,2016(4)：407-415.

[2]HU Jinyu,GAO Zhiwei.Modules identification in gene positive networks of hepatocellular carcinoma using Pearson agglomerative method and Pearson cohesion coupling modularity[J].Journal ofApplied Mathematics,2012(3)：1-16.

[3]WANG K,ZHOU X,LI T.Optimizing load balancing and data-locality with data-aware scheduling[C].Big Data：IEEE 2014 IEEE International Conference,2014：119-128.

[4]GENG Yishuang,CHEN Jin,FU Ruijun,et al.Enlighten wearable physiological monitoring systems：On-body rf characteristics based human motion classification using a support vector machine[J].IEEE transactions on mobile computing,2015,1(1)：1-15.

[5]LV Z,HALAWANI A,FENG S.Multimodal hand and foot gesture interaction for handheld devices[J].ACM Transactions on Multimedia Computing,2014,11(1s)：10.

[6]ZHANG L,HE B,SUN J.Double image multi-encryption algorithm based on fractional chaotic time series[J].Journal of Com-putational and Theoretical Nanoscience,2015,12：1-7.

[7]SU T,LV Z,GAO S.3d seabed：3d modeling and visualization platform for the seabed[C].Multimedia and Expo Workshops(ICMEW)：2014 IEEE International Conference,2014：1-6.

[8]LIANG Ying,WANG Peigang.Influence of prudential value on the subjective well-being of chinese urban-rural residents[J].Social Indicators Research,2014,118(3)：1 249-1 267.

[9]LIANG Ying,LI Shuqin.Landless female peasants living in resettlement residential areas in China have poorer quality of life than males：results from a household study in the Yangtze River Delta region[J].Health and Quality of Life Outcomes,2014(12)：71,1-17.

[10]LV Z,TEK A,DA F.Game on,science-how video game technology may help biologists tackle visualization challenges[J].Plos One,2013,8(3)：e57 990.

[11]SU T,WANG W,LV Z.Rapid Delaunay triangulation for randomly distributed point cloud data using adaptive Hilbert curve[J].Computers&Graphics,2016,54：65-74.

[12]HU Jinyu,GAO Zhiwei,PAN Weisen.Multiangle social network recommendation algorithms and similarity network evaluation[J].Journal ofApplied Mathematics,2013：3 600-3 611.

[13]LIU Guanxiong,GENG Yishuang,KAVEH P,Effects of calibration RFID tags on performance of inertial navigation in indoor environment[C].Networking and Communications(ICNC)：2015 International Conference on Computing,2015.

[14]HE Jie,GENG Yishuang,WAN Yadong,et al.A cyber physical test-bed for virtualization of RF access environment for body sensor network[J].IEEE Sensor Journal,2013,13(10)：3 826-3 836.

[15]ZHOU Shuang,MI Liang,CHEN Hao,et al.Building detection in Digital surface model[C].2013 IEEE International Conference on Imaging Systems and Techniques(IST),2012.

[16]HE Jie,GENG Yishuang,KAVEH P.Toward accurate human tracking：Modeling time-of-arrival for wireless wearable sensors in multipath environment[J].IEEE Sensor Journal,2014,14(11)：3 996-4 006.