摘要：在信號復(fù)原領(lǐng)域，以奈奎斯特采樣率為基準(zhǔn)的采樣方法往往并不高效。這種狀況通常發(fā)生在信號本身相對于帶寬僅包含有限頻率的時候[1]。近年來一些新的采樣系統(tǒng)應(yīng)運而生。本文介紹了一種新的高效采樣系統(tǒng)——隨機(jī)調(diào)制系統(tǒng)[2]。該系統(tǒng)比奈奎斯特采樣系統(tǒng)更有效，僅需要非常少的樣本來復(fù)原信號。但這種系統(tǒng)的解法一般采樣貪婪算法，該算法無法獲取更高的重構(gòu)精度和更少的采樣。為了解決這個問題，本文提出了一種基于凸優(yōu)化的復(fù)原算法——對偶內(nèi)點算法。實驗證明，本文的對偶內(nèi)點算法不但比貪婪算法更高效，同時在復(fù)原信號上也更為精確。

關(guān)鍵詞：壓縮感知 信號復(fù)原 稀疏估計 對偶內(nèi)點法 正交匹配追蹤

1 概述

眾所周知，香農(nóng)采樣理論被廣泛用于信號重構(gòu)。然而，當(dāng)處理稀疏帶限信號時（比如傳感器采集的信號，精確追蹤定位信號等），該采樣方式將會十分低效。

為了解決這個問題，我們引入了一種新的采樣方法，名為隨機(jī)調(diào)制系統(tǒng)。我們定義K為離散的頻率數(shù)，W為帶寬，那么按照本文的算法，每秒僅用O（Klog（W/K））次即可重構(gòu)出信號。這種采樣方式遠(yuǎn)遠(yuǎn)高于奈奎斯特的W hz/s。

該隨機(jī)調(diào)制系統(tǒng)包含三個部分：解調(diào)，低通濾波與低速率采樣。首先，我們對輸入的連續(xù)時間信號與隨機(jī)數(shù)發(fā)生器做線性乘積。然后，我們用低通濾波器來處理偽影。最后，濾波后的信號將按照1/R每秒的速率進(jìn)行采樣。

事實上，隨機(jī)調(diào)制系統(tǒng)本質(zhì)是一個線性系統(tǒng)，他可以把連續(xù)信號映射為離散信號。重構(gòu)信號的核心問題是解決一個L0泛數(shù)問題。盡管L0問題是NP-困難的，我們可以把它轉(zhuǎn)化為L1泛數(shù)問題。該問題可由迭代加權(quán)最小方差[3]，對偶內(nèi)點法[4]或正交匹配追蹤法[5]來解。

本文將建立隨機(jī)調(diào)制系統(tǒng)的線性模型。之后我們將分別比較對偶內(nèi)點法（PDIP），簡化的對偶內(nèi)點法（SPDIP），不穩(wěn)定路徑追蹤法（SDPT3）和正交匹配追蹤法（OMP）。

2 系統(tǒng)設(shè)計[2]

2.1 信號的屬性

本文僅考慮具備如下三條屬性的信號：

①帶限信號：最大頻率有整數(shù)邊界。

②頻率域稀疏：和帶限信號比，我們希望非零元素數(shù)量要很少。

③周期性：該信號必須在時域是周期的。這樣的話，我們可以做傅里葉級數(shù)延展。

2.2 隨機(jī)解調(diào)器結(jié)構(gòu)圖

圖2.1 隨機(jī)解調(diào)器結(jié)構(gòu)圖

如圖1中所示，隨機(jī)數(shù)發(fā)生器等同于ADC按同等的概率隨機(jī)產(chǎn)生+1或-1的值。

其輸出結(jié)果為：

在此之后，連續(xù)信號f（t）將會與該隨機(jī)數(shù)產(chǎn)生器線性相乘：

該系統(tǒng)的最后兩個模塊為積分器和采樣器，作用相當(dāng)于ADC和低通濾波器。

這里m范圍如下：

低通濾波器的本質(zhì)是一個累加器，它會把調(diào)制后的信號按1/r秒的間隔相加。這里Ym序列將會作為輸出。值得注意的是本系統(tǒng)的采樣率R遠(yuǎn)遠(yuǎn)小于奈奎斯特采樣率W。

3 解調(diào)器的矩陣模型

在理想的情況下，隨機(jī)調(diào)制系統(tǒng)是線性的。

3.1 平均信號xn與它的矩陣表達(dá)式

為了構(gòu)建這個線性系統(tǒng)，我們首先定義在1/W秒內(nèi)的平均信號：

根據(jù)連續(xù)時間域的傅里葉級數(shù)，f（t）可以表示如下：

這里，

平均信號xn表示如下：

設(shè)：

則：

設(shè)尺寸為W*W的離散傅里葉變換矩陣F為：

那么，離散的平均信號可以被如下線性表達(dá)式表示：

3.2 解調(diào)器的矩陣表達(dá)式

我們首先考慮作用在f（t）上的隨機(jī)解調(diào)器，它其實是一個具有W元素的對角矩陣：

我們假設(shè)采樣率為R，同時W可被R整除。之后，積分器作用在于yn，它是W/R個連續(xù)被調(diào)制信號的和。因此積分器表達(dá)式相當(dāng)于H，定義如下：

比如當(dāng)W=8，R=2時。H表達(dá)式為：

最終，解調(diào)器的線性模型如下：

3.3 L1范數(shù)凸優(yōu)化問題陳述

從之前的章節(jié)，我們已經(jīng)獲得了調(diào)制系統(tǒng)的表達(dá)式。那么之后的問題就是從y=As中估計出稀疏的s?；謴?fù)信號s的問題可以轉(zhuǎn)化如下：

這里L(fēng)0范數(shù)即統(tǒng)計出向量中的非零元素的個數(shù)。這個問題是NP困難的。解決這個問題有兩類方法。包括凸松弛法即采用L1范數(shù)來替代L0范數(shù)：

該問題可由內(nèi)點法來解。

對于非凸方法，貪婪算法比如正交投影追蹤法（OMP）可以解決此類問題。

3.4 信號重構(gòu)

當(dāng)所有基調(diào)信號被準(zhǔn)確估計后，信號復(fù)原算法如下：

因為在仿真中，我們采用的是離散信號，所以其離散復(fù)原算法如下：

最終f（t）信號被復(fù)原如下：

3.5 復(fù)原定理

定理1（隨機(jī)信號復(fù)原定理）： 假定采樣率為：

同時，R整除W，C為正數(shù)。y=As是從調(diào)制器采集到的信息。那么信號估測值■與信號值s不相等的概率僅為O（W-1）。證明請見[2]。

4 L1范數(shù)最小化問題

本章節(jié)，我們重點討論如何用凸優(yōu)化中的內(nèi)點法解決L1范數(shù)問題。

4.1 線性規(guī)劃

我們需要解決下述問題：

如果x值均為正數(shù)，那么這個問題實際上是個線性規(guī)劃問題：

當(dāng)x包含負(fù)數(shù)時，為使得目標(biāo)函數(shù)處處可導(dǎo)，我們作如下變換：

同時：

，

我們定義新的矩陣如下：

這樣的話，本問題仍可轉(zhuǎn)化一個線性規(guī)劃問題：

總之，無論x是正是負(fù)，他均可被轉(zhuǎn)化為下面的線性規(guī)劃問題：

4.2 主對偶內(nèi)點法[4]

主問題表達(dá)式為：

那么對偶問題為：

當(dāng)存在一個滿足上述主對偶等式的點時，我們有：

當(dāng) 時，存在優(yōu)化的解。此時，上述等式將滿足如下方程組：

這里 ，

4.2.1 搜索方向

搜索方向根據(jù)牛頓法計算如下：

該方向可以定義為：

通過行列消元法其封閉解如下：

最終有：

這里 r4 與P 定義為：

4.2.2 線性搜索與更新

Input：

While （x>0 is false）

End

While

End

Output： S

這里：

4.2.3 主對偶內(nèi)點法

之前2部分講述了如何計算搜索方向的解析表達(dá)式。那么整個算法如下：

假定x滿足： x>0，

Repeat：計算 ，

計算

線性搜索并更新

Until： ， ，

4.3 簡化的主對偶內(nèi)點法

在[6]中，我們找到了主對偶內(nèi)點法的簡化算法（SPDIP）。與主對偶內(nèi)點法的區(qū)別在于，初值的選取是由下面的判據(jù)來決定的：

， ，

這里的初始值 必須在可行集之內(nèi)。我們定義 ， 那么初始點判據(jù)如下：

所有算法如下：

While

Compute

Set

end

4.4 基于不穩(wěn)定路徑追蹤的主對偶內(nèi)點法

基于不穩(wěn)定路徑的主對偶內(nèi)點法是在上述幾種方法的基礎(chǔ)上而完成的，它的特點在于：①具備預(yù)測與糾錯步驟。②考慮對角塊結(jié)構(gòu)與稀疏性。③支持復(fù)數(shù)。④對稱算子有四個搜索方向：AHO，HKM，NT和GT。有興趣的讀者可參見[7]。

5 重建結(jié)果的比較

本章我們將比較以下四種方法：主對偶內(nèi)點法（PDIP），簡化的主對偶內(nèi)點法（SPDIP），基于不穩(wěn)定路徑追蹤的主對偶內(nèi)點法（SDPT3）和正交匹配追蹤法（OMP）。

5.1 PDIP的重構(gòu)結(jié)果

采樣參數(shù)為：W=1000HZ， T=1S， R=25HZ。

（a） 輸入的復(fù)氏級數(shù) （b） 重構(gòu)后的復(fù)氏級數(shù)

圖5.1 PDIP 充足采樣（R=25）

圖5.1展示了原始與復(fù)原譜。很明顯，只有2個調(diào)的強(qiáng)度被復(fù)原出來。

因為復(fù)原譜未被準(zhǔn)確估計，時域的差值信號非常大。

5.2 SPDIP復(fù)原結(jié)果

SDPIP在強(qiáng)度恢復(fù)上略好于PDIP，但從復(fù)原譜來看仍有很多非零元素。

5.3 SDPT3復(fù)原結(jié)果

本實驗中： W=1000HZ， T=1S， R=25HZ。從如下的結(jié)果來看，SDPT3方法復(fù)原效果非常好，所有的譜都被成功復(fù)原出來。

（a） 輸入譜 （b） 重構(gòu)譜

圖5.5 SDPT3 充分采樣（R=25）

重構(gòu)的時域信號也基本無誤差，這點可以由差值信號觀測出來。

5.4 OMP復(fù)原結(jié)果

最終我們將展示基于貪婪算法的信號復(fù)原結(jié)果。本例中R=100HZ。

復(fù)原譜結(jié)果如下，該實驗結(jié)果較為合理，譜的頻域位置基本被完好復(fù)原，但強(qiáng)度有3-4個調(diào)略有誤差?？傮w誤差比SDPT3大些，但是好于其它2種方法。

6 結(jié)論

本文首先介紹了隨機(jī)調(diào)制系統(tǒng)在采樣上較奈奎斯特系統(tǒng)的優(yōu)勢。之后我們采用矩陣分析理論，建立了該調(diào)制系統(tǒng)的線性模型。并發(fā)現(xiàn)了該系統(tǒng)的稀疏解為L1范數(shù)問題。之后我們提出了基于凸優(yōu)化的內(nèi)點法來解決L1范數(shù)問題。根據(jù)我們的實驗，基于不穩(wěn)定路徑追蹤的內(nèi)點法在信號復(fù)原精度和采樣率上超過了傳統(tǒng)的貪婪算法以及其它的內(nèi)點法。因此，我們提出的算法可以用更少的采樣來獲取更高的信號重建精度。

參考文獻(xiàn)：

[1]Simeon Kamdem Kuiteing，“Compressive Hyperspectral Imaging Using Progressive Total Variation，”ICASSP，2014.

[2]J.A.Tropp，“Beyond Nyquist： efficient sampling of sparse bandlimited signals，”IEEE trans. Inf.Theory.，vol.56，no.1，Jan 2010.

[3]I.Daubechies， R.Devore，“iteratively reweighted least squares minimization for sparse recovery，”Commun.Pure appl.math.，2010.

[4]Michael Saunders，“PDCO： Primal-Dual Interior Methods，”Stanford University，online notes，2013.

[5]T.Tong，“Orthogonal Matching Pursuit for sparse signal recovery with noise，”IEEE trans. Inf. Theory.， vol.57，no.7，July 2011.

[6]Renato D.C. Monterio，“interior path following primal dual algorithms art 1 linear programming，”mathematical programming，1989.

[7]R.H.Tutunvu，“Solving semidenite-quadratic-linear programs using SDPT3”，mathematical programming，vol 95，no.2，2003.

通訊作者：李麗（1961-），女，工程師。