基于凸優化的稀疏帶限信號的高效采樣方法

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

關鍵詞：壓縮感知 信號復原 稀疏估計 對偶內點法 正交匹配追蹤

1 概述

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

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

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

事實上，隨機調制系統本質是一個線性系統，他可以把連續信號映射為離散信號。重構信號的核心問題是解決一個L0泛數問題。盡管L0問題是NP-困難的，我們可以把它轉化為L1泛數問題。該問題可由迭代加權最小方差[3]，對偶內點法[4]或正交匹配追蹤法[5]來解。

本文將建立隨機調制系統的線性模型。之后我們將分別比較對偶內點法（PDIP），簡化的對偶內點法（SPDIP），不穩定路徑追蹤法（SDPT3）和正交匹配追蹤法（OMP）。

2 系統設計[2]

2.1 信號的屬性

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

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

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

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

2.2 隨機解調器結構圖

圖2.1 隨機解調器結構圖

如圖1中所示，隨機數發生器等同于ADC按同等的概率隨機產生+1或-1的值。

其輸出結果為：

在此之后，連續信號f（t）將會與該隨機數產生器線性相乘：

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

這里m范圍如下：

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

3 解調器的矩陣模型

在理想的情況下，隨機調制系統是線性的。

3.1 平均信號xn與它的矩陣表達式

為了構建這個線性系統，我們首先定義在1/W秒內的平均信號：

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

這里，

平均信號xn表示如下：

設：

則：

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

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

3.2 解調器的矩陣表達式

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

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

比如當W=8，R=2時。H表達式為：

最終，解調器的線性模型如下：

3.3 L1范數凸優化問題陳述

從之前的章節，我們已經獲得了調制系統的表達式。那么之后的問題就是從y=As中估計出稀疏的s。恢復信號s的問題可以轉化如下：

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

該問題可由內點法來解。

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

3.4 信號重構

當所有基調信號被準確估計后，信號復原算法如下：

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

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

3.5 復原定理

定理1（隨機信號復原定理）： 假定采樣率為：

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

4 L1范數最小化問題

本章節，我們重點討論如何用凸優化中的內點法解決L1范數問題。

4.1 線性規劃

我們需要解決下述問題：

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

當x包含負數時，為使得目標函數處處可導，我們作如下變換：

同時：

，

我們定義新的矩陣如下：

這樣的話，本問題仍可轉化一個線性規劃問題：

總之，無論x是正是負，他均可被轉化為下面的線性規劃問題：

4.2 主對偶內點法[4]

主問題表達式為：

那么對偶問題為：

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

當 時，存在優化的解。此時，上述等式將滿足如下方程組：

這里 ，

4.2.1 搜索方向

搜索方向根據牛頓法計算如下：

該方向可以定義為：

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

最終有：

這里 r4 與P 定義為：

4.2.2 線性搜索與更新

Input：

While （x>0 is false）

End

While

End

Output： S

這里：

4.2.3 主對偶內點法

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

假定x滿足： x>0，

Repeat：計算 ，

計算

線性搜索并更新

Until： ， ，

4.3 簡化的主對偶內點法

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

， ，

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

所有算法如下：

While

Compute

Set

end

4.4 基于不穩定路徑追蹤的主對偶內點法

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

5 重建結果的比較

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

5.1 PDIP的重構結果

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

（a） 輸入的復氏級數 （b） 重構后的復氏級數

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

圖5.1展示了原始與復原譜。很明顯，只有2個調的強度被復原出來。

因為復原譜未被準確估計，時域的差值信號非常大。

5.2 SPDIP復原結果

SDPIP在強度恢復上略好于PDIP，但從復原譜來看仍有很多非零元素。

5.3 SDPT3復原結果

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

（a） 輸入譜 （b） 重構譜

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

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

5.4 OMP復原結果

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

復原譜結果如下，該實驗結果較為合理，譜的頻域位置基本被完好復原，但強度有3-4個調略有誤差。總體誤差比SDPT3大些，但是好于其它2種方法。

6 結論

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

參考文獻：

[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-），女，工程師。