壓縮感知中的信號重構(gòu)方法分析

魯周迅，徐曉梅

（南京工業(yè)大學(xué),江蘇 南京 211800)

現(xiàn)代信息技術(shù)的飛速發(fā)展，使得人們對信息量的要求劇增，對信號帶寬采樣速度和處理速度的要求也越來越高。傳統(tǒng)的奈奎斯特采樣定律要求信號的采樣速度至少要達(dá)到信號帶寬的兩倍才能重構(gòu)原信號，這就為現(xiàn)代信息技術(shù)較高的要求設(shè)置了障礙。另外，在實(shí)際應(yīng)用中，為了降低存儲(chǔ)、處理和傳輸?shù)某杀?，人們常采用壓縮方式以較少的比特?cái)?shù)表示信號，大量的非重要的數(shù)據(jù)被拋棄,這種高速采樣在壓縮的過程浪費(fèi)了大量的采樣資源。

為了解決這個(gè)問題,由Candes和Donoho等人提出了壓縮感知理論CS(Compressive Sensing)[1-2]。該理論可以理解為將模擬數(shù)據(jù)節(jié)約地轉(zhuǎn)換成壓縮數(shù)字形式，避免了資源的浪費(fèi)，即在采樣信號的同時(shí)就對數(shù)據(jù)進(jìn)行適當(dāng)?shù)膲嚎s，相當(dāng)于在采樣過程中尋找最少的系數(shù)來表示信號，并能用適當(dāng)?shù)闹貥?gòu)算法從壓縮數(shù)據(jù)中恢復(fù)出原始信號。壓縮感知的核心概念在于試圖從理論上降低對一個(gè)信號進(jìn)行測量的成本。壓縮感知理論包含了許多重要的數(shù)學(xué)理論，具有廣泛的應(yīng)用前景。

本文就壓縮感知理論進(jìn)行了分析，著重介紹了其重構(gòu)方法，并對其效果進(jìn)行了詳細(xì)分析。

1 壓縮感知概述

假設(shè)一個(gè)采樣信號s,s∈RN。用一個(gè)與變換矩陣不相關(guān)的 M×N(M＜＜N)測量矩陣 Φ對信號進(jìn)行線性投影,得到線性測量值 y=Φs。測量值 y是一個(gè) M×1矩陣，這樣使測量對象從N維降為M維，觀測過程是非自適應(yīng)的,即測量矩陣Φ的選擇不依賴于信號s,測量矩陣的設(shè)計(jì)要求信號從f轉(zhuǎn)換為y的過程中,所測量到的K個(gè)測量值不會(huì)破壞原始信號的信息,保證信號的精確重構(gòu)。由于壓縮感知要求信號是可稀疏表示的，且K＜＜M，所以滿足有效等距的性質(zhì)(RIC)，即對于任意的稀疏信號s和常數(shù) δs，δs∈(0,1)。 滿足：

其中，|T|≤S, 對于系數(shù)序列(cj)，j∈T。

根據(jù) RIC性質(zhì)可知，當(dāng) δ2s+δ3s＜1時(shí)，信號 s可由下式重構(gòu)：

Φ 為高斯隨機(jī)序列，Φi,j～N(0,1/M)。 如果滿足式(3)信號可被準(zhǔn)確地重構(gòu)。

2 用戶的壓縮頻譜感知

對信號進(jìn)行直接采樣時(shí)，要求高速度的模數(shù)轉(zhuǎn)換器(ADC)并且要存儲(chǔ)和傳輸大量的數(shù)據(jù)。模擬信號轉(zhuǎn)換器(ADC)可以實(shí)現(xiàn)這樣的功能?；鶐盘杧(t)是經(jīng)AIC采樣得到的信號。根據(jù)參考文獻(xiàn)[3-4]，AIC可以看作是工作于奈奎斯特定律下的ADC。ADC輸入端的堆棧向量為：

壓縮信號的N×N和 M×M自相關(guān)矩陣和式 (4)、式(5)有如下的關(guān)系：

其中：H指 Hermitian矩陣；[Ry]ij=ry(i-j)=ry*(j-i);[Rx]ij=rx(i-j)=rx*(j-i)。

根據(jù)式(4)、式(5)壓縮信號的 2N×1和 2M×1自相關(guān)矩陣可以寫成下面的形式：

其中，第一個(gè)0值是人為加入的，并且這些向量的第一排和第一列分別是自相關(guān)矩陣。為了得到CS的重構(gòu)信號，根據(jù)式(8)、式(9)，應(yīng)用矩陣的運(yùn)算，可以得到：

[4]知：

其中，Zs是 2N×1 向量，G=(Γfw)-1。 2N×2N 矩陣 w 和 f分別指基帶濾波和傅里葉變換，聯(lián)合式(10)、式(11)可以得到CS信號邊緣頻譜重構(gòu)的優(yōu)化條件:

3 信息重構(gòu)方法

目前為止出現(xiàn)的重構(gòu)算法可以分為如下幾類：

(1)貪婪追蹤算法:這類方法是通過每次迭代時(shí)選擇一個(gè)局部最優(yōu)解來逐步逼近原始信號。這些算法包括MP算法、OMP算法、分段OMP算法和正則化OMP算法。

(2)凸松弛法:這類方法通過將非凸問題轉(zhuǎn)化為凸問題求解找到信號的逼近，如BP算法、內(nèi)點(diǎn)法、梯度投影方法和迭代閾值法。

(3)組合算法：這類方法要求信號的采樣支持通過分組測試快速重建,如傅里葉采樣、鏈?zhǔn)阶粉櫤虷HS(Heavg Hitters on Steroids)追蹤等。

每種算法都有其固有的缺點(diǎn)，凸松弛法重構(gòu)信號所需的觀測次數(shù)最少，但往往計(jì)算負(fù)擔(dān)很重。貪婪追蹤算法在運(yùn)行時(shí)間和采樣效率上都位于另兩類算法之間。由此可知，重構(gòu)算法和所需的觀測次數(shù)密切相關(guān)。當(dāng)前，壓縮感知理論的信號重構(gòu)問題的研究主要集中在如何構(gòu)造穩(wěn)定的、計(jì)算復(fù)雜度較低的、對觀測數(shù)量要求較少的重構(gòu)算法來精確地恢復(fù)原信號。本文將用梯度投影算法(GP)和 Projected Barzilai-Borwein(PBB)來重構(gòu)信號，并對這兩種算法進(jìn)行仿真分析。

3.1 GP算法介紹

根據(jù)前面的壓縮感知理論，假設(shè)A=ΦG,即

在第j個(gè)感知用戶中，引進(jìn)向量uj和vj來代替zs。zs,j=uj-vj，uj≥0，vj≥0，j=1，…，J。 其中，對于所有的 i=1,…,2N,都 有 uj(i)=(zs,j(i))+=max{0,zs,j(i)}，vj(i)=(-zs,j(i))+=max{0,-zs,j(i)}(a)+=max(0,a)。于是，可以得到其中 12N=[1,1,…,1]T。 式(12)可以寫成下面的形式：

式(14)可以寫成帶約束二次規(guī)劃的形式（BCQP）:

3.2 基本GP算法

3.3 GBB重構(gòu)算法

4 仿真結(jié)果分析

根據(jù)上面的理論，文章對這兩種方法進(jìn)行了仿真分析，并作出了比較。仿真結(jié)果如圖1、圖2所示。

圖1表明：在壓縮感知中，當(dāng)壓縮率減小的時(shí)候，MSE增加。如果考慮多用戶的頻譜感知機(jī)制，MSE也會(huì)隨著用戶的減少而增加。因此，可以采用降低壓縮率，而增加感知用戶的方法來進(jìn)行壓縮感知，不會(huì)降低重構(gòu)的性能。同時(shí)，PBB算法比基本GP算法效果更好一點(diǎn)。

圖2表明：當(dāng)用戶增加時(shí)，檢測概率增加，虛警概率減小。PBB算法和基本GP算法的結(jié)論是基本一致的。

為了更好地重構(gòu)信號，壓縮感知是很有必要的，而且壓縮感知可以降低硬件消耗，減少存儲(chǔ)空間的浪費(fèi)。在壓縮感知理論的信號重構(gòu)方法中，梯度投影算法和PBB算法會(huì)取得比較好的效果。在未來的研究中，將嘗試改進(jìn)這種算法，使壓縮感知理論更加完善。

參考文獻(xiàn)

[1]DONOHO D.Compressed sensing[J].IEEE Trans.Information Theroy,2006,52(4):1289-1306.

[2]DONOHO D L.Compressed sensing[J].IEEE Transactions on Information Theory,2006,52(4):1289-1306.

[3]KIROLOS S,RAGHEB T,LASKA J et al.Practial issues in implementing analog-to-information conventers[J].in The 6thInternational Workshop on System-on-Chip for Real-Time Applications,2006:141-146.

[4]LASKA J N,KIROLOS S,DUARTE M F,et al.Theory and implementation of an analog-to-information converter using random demodulation[J].In IEEE international symposium on Circuits and Systems(ISCAS),2007:1959-1962.

[5]傅迎華.可壓縮感知重構(gòu)算法與近似QR分解[J].計(jì)算機(jī)應(yīng)用，2008,28（9）：2300-2302.