在信号复原领域，以奈奎斯特采样率为基准的采样方法往往并不高效。这种状况通常发生在信号本身相对于带宽仅包含有限频率的时候[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]主问题表达式为：
zssi那么对偶问题为：
当存在一个满足上述主对偶等式的点时，我们有：
当 时，存在优化的解。此时，上述等式将满足如下方程组：
这里 ，
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：计算 ，
计算
vb连接sql数据库线性搜索并更新
Until： ， ，
4.3 简化的主对偶内点法
在[6]中，我们到了主对偶内点法的简化算法（SPDIP）。与主对偶内点法的区别在于，初值的选取是由下面的判据来决定的：
， ，
这里的初始值 必须在可行集之内。我们定义 ， 那么初始点判据如下：
所有算法如下：
While
Compute
Set粗糙的布片
end
4.4 基于不稳定路径追踪的主对偶内点法
基于不稳定路径的主对偶内点法是在上述几种方法的基础上而完成的，它的特点在于：①具备预测与纠错步骤。②考虑对角块结构与稀疏性。③支持复数。④对称算子有四个搜索方向：AHO，HKM，NT和GT。有兴趣的读者可参见[7]。
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议