基于凸优化的稀疏带限信号的高效采样方法

摘要：在信号复原领域，以奈奎斯特采样率为基准的采样方法往往并不高效。这种状况通常发生在信号本身相对于带宽仅包含有限频率的时候[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-），女，工程师。