基于分散式壓縮感知的低能耗信號重構模型

李　博，李云鶴，李廣才

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

1　概述

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

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

2　本文算法

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

2.1　疏密度的評估

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

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

上述性質導出了下列法則1.

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

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

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

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

推論1假設A符合(K,δK)的特性.當預估稀疏度

法則1可以根據推論1和例1證明.

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

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

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

2.2　算法的迭代過程

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

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

圖1　設計算法的基本步驟

3　算法的重構性能指數

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

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

圖2　重構信號的2個誤差

4　稀疏度的評估

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

圖3　不同K值下稀疏度預估的對比

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

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

表1　2種方法的模擬次數的對比

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

圖4　迭代次數

圖5　不同算法的重構可能性II的對比

5　總結

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

參考文獻：

[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.