基于BFGS拟牛顿法的压缩感知SL0重构算法

孙娜; 刘继文; 肖东亮

doi:10.11999/JEIT170813

基于BFGS拟牛顿法的压缩感知SL0重构算法

doi: 10.11999/JEIT170813

中国农业大学信息与电气工程学院北京 100083

基金项目: 国家自然科学基金(61271273)

详细信息

作者简介:
孙娜：女，1975年生，副教授，研究方向为信号处理与压缩感知

刘继文：男，1990年生，硕士，研究方向为压缩感知

肖东亮：男，1968年生，副教授，研究方向为无线通信与信息安全

通讯作者:
孙娜　 sunnacau@126.com

中图分类号: TN911.7
计量
- 文章访问数: 2087
- HTML全文浏览量: 1022
- PDF下载量: 268
- 被引次数: 25
出版历程
- 收稿日期: 2017-08-16
- 修回日期: 2018-07-19
- 网络出版日期: 2018-07-26
- 刊出日期: 2018-10-01

SL0 Reconstruction Algorithm for Compressive Sensing Based on BFGS Quasi Newton Method

College of Information and Electrical Engineering, China Agricultural University, Beijing 100083, China

Funds: The National Natural Science Foundation of China (61271273)

摘要

摘要: 平滑l₀范数(SL0)算法是一种基于近似l₀范数的压缩感知信号重构算法，采用最速下降法和梯度投影原理，通过选择一个递减序列来逐步逼近最优解，具有匹配度高、计算量低、不需要已知信号稀疏度等优点。但是，其迭代方向为负梯度方向，使得在迭代过程中产生“锯齿现象”，导致在最优解附近收敛速度较慢。牛顿法具有较快的收敛速度，但是对初值的要求较高，并且需要计算Hesse矩阵。拟牛顿法则克服了这个缺点，利用BFGS公式计算Hesse矩阵的近似矩阵，只需要计算1阶导数信息。该文在SL0算法的基础上，结合BFGS拟牛顿法，提出一种改进的压缩感知信号重构算法。首先采用最速下降法迭代得到信号的某个估计值，然后将此估计值作为拟牛顿法的初值继续迭代，直至得到最优解。计算机仿真结果表明，在相同的条件下，该算法在重构精度、峰值信噪比和重建匹配度等方面均有较大提高。
- 压缩感知 /
- 重构算法 /
- 平滑l₀范数 /
- BFGS
Abstract: Smoothed l₀ norm (SL0) algorithm is a compressive sensing reconstruction algorithm based on approximate l₀ norm, which uses the steepest descent method and gradient projection principle, by selecting a decreasing sequence to get the optimal solution. It has the advantages of high matching degree, low computational complexity and without knowing the signal sparsity. However, the iterative direction of steepest descent method is negative gradient direction, which leads to the " sawtooth phenomenon” and the slower convergence speed in the vicinity of the optimal solution. The Newton method has a good convergence speed but has higher requirement of the initial value and needs to calculate the Hessian matrix. The quasi Newton method overcomes this shortcoming and uses BFGS formula to calculate the approximate matrix of the Hessian matrix, it only needs the first derivative information. On the basis of SL0 algorithm and BFGS quasi Newton method, an improved reconstruction algorithm for Compressed Sensing (CS) signal is proposed. The steepest descent method is first used to get an estimated value, and then is taken as the initial value of quasi Newton method, using BFGS method to update the iterative direction until retaining the optimal solution. The simulation results show that the proposed algorithm has great improvement in reconstruction accuracy, peak signal to noise ratio and reconstruction matching degree.
- Compressive Sensing (CS) /
- Reconstruction algorithm /
- Smoothed l₀ norm /
- BFGS

HTML全文

1. 引言

传统的奈奎斯特采样定理要求采样频率至少为信号带宽的两倍时才可以不失真地重构出原始信号，该理论需要较高的采样率，并且采样所得到的信息中，绝大多数都是冗余的，造成了采样资源的严重浪费。压缩感知(Compressive Sensing, CS)^[1–3]理论是基于信号稀疏性或可压缩性而提出的一种全新的信号处理理论。该理论表明，通过少量的测量值就可以实现稀疏或可压缩信号的精确重构，克服了采样数据量大，采样时间以及数据存储空间等物理资源严重浪费的问题。现已在图像处理，认知无线电通信，无线传感器网络，雷达成像等领域^[4–7]得到广泛应用。该理论主要包括信号的稀疏表示、编码测量以及重构算法3个方面。其中，重构算法是压缩感知的核心，关键问题是如何用较少的低维测量值来快速、稳定、精确或最大程度地恢复出原始信号。目前已有的重构算法从广义上主要分为两类：一类是基于l₀范数最小化的贪婪迭代匹配追踪系列算法^[8–11]，另一类是基于l₁范数最小化的松弛算法^{[12, 13]}。

平滑l₀范数(Smoothed l₀ Norm, SL0)算法是Mohimani等人^[14]于2009年提出的，是一种基于过完备稀疏分解的快速算法。该算法使用带参数的平滑函数去逼近向量的最小l₀范数，将求解最小l₀范数问题转化为求解平滑函数的极值问题。2011年林婉娟等人^[15]用双曲正切函数替代高斯函数，利用牛顿法更新迭代方向，提出了NSL0算法； 2012年杨良龙等人^[16]用近似双曲正切函数替代高斯函数，提出了ANSL0(Almost Newton Smoothedl₀ Norm)算法，同年，王军华等人^[17]通过利用快速不动点构造下降方向，提出了ISL0(Iterative SL0)算法，2013年Ye等人^[18]将压缩感知用于稀疏信道估计，提出了l₂-SL0算法；2014年Mohammadi等人^[19]将压缩感知用于求解非负条件下的稀疏分解，提出了CSL0(Constrained SL0)算法；2015年李颖等人^[20]利用反正切函数近似高斯函数，提出了L0AM(l₀ Norm Approximation Minimization)算法。本文在SL0算法的基础上，结合BFGS拟牛顿法，提出了一种改进的压缩感知信号重构算法(以下简称BFGS-SL0算法)。首先利用最速下降法迭代得到一个估计值，然后将此估计值作为拟牛顿法的初值继续迭代，用BFGS公式更新迭代方向，结合不精确1维搜索求取步长，直至得到最优解。经过计算机仿真，验证了该算法在重构精度、峰值信噪比(Peak Signal to Noise Ratio, PSNR)和重建匹配度^[21](Reconstruction Matching Degree, ReMD)等方面均有较大提高。

本文第2节介绍了SL0算法基础，第3节详细给出了BFGS-SL0算法的步骤，第4节进行了计算机仿真，并对结果进行了分析和比较，最后给出了结论。

2. SL0算法

压缩感知重构算法的基本模型是求解式(1), SL0算法通过选取平滑的连续函数去逼近矢量的l₀范数，利用凸优化算法中的最速下降法和梯度投影原理，求出使l₀范数最小的量。

$\left. {\begin{array}{*{20}{l}}{\min \mathop {\left\| {{x}} \right\|}\nolimits_0 }\\{{\rm{s}}.{\rm{t}}.\;\;{{y}} = {{Φ}}{{x}}}\end{array}} \right\}$

(1)

定义标准高斯函数：

${{f} _\sigma }{\rm{(}}x{\rm{) = }}{{\rm{e}}^{ - \frac{{{{x} ^2}}}{{2{\sigma ^2}}}}}$

(2)

其中， $\sigma > 0$ 。可以推出：

$\mathop {{\rm{lim}}}\limits_{\sigma \to 0} {f_\sigma }{\rm{(}}x{\rm{)}} = \left\{ {\begin{array}{*{20}{c}}{{\rm{0}} ,\;\;x \ne 0 }\\{1 ,\;\;x = 0}\end{array}} \right.$

(3)

假设有式(4)定义：

${{{F}}_\sigma }{\rm{(}}{{x}}{\rm{) = }}n - \sum\limits_{i = 1}^n {{f_\sigma }{\rm{(}}{x_i}{\rm{)}}}$

(4)

其中， ${x_i}$ 表示向量 ${{x}}$ 中的第 $i$ 个分量。由以上性质可得

$\mathop {\left\| x \right\|}\nolimits_0 = \mathop {{\rm{lim}}}\limits_{\sigma \to 0} {{{F}}_\sigma }{\rm{(}}{{x}}{\rm{)}}$

(5)

$\sigma$ 的取值决定了 ${{{F}}_\sigma }$ 函数的光滑程度： $\sigma$ 值越大， ${{{F}}_\sigma }$ 函数越光滑，越容易求得极小值； $\sigma$ 值越小， ${{{F}}_\sigma }$ 函数越粗糙，局部极小值越多，越接近向量 ${{x}}$ 的l₀范数。当 $\sigma = 0$ 时， $\mathop {\left\| {{x}} \right\|}\nolimits_0 = {{{F}}_\sigma }{\rm{(}}{{x}}{\rm{)}}$ ，但这是不存在的，只能选择一个 $\sigma$ 递减序列来逐步逼近l₀范数。

SL0算法利用最速下降法即负梯度方向来更新迭代方向，仅需要计算1阶导数信息，计算量较小，但是在迭代过程中存在“锯齿现象”，使得收敛速度减慢并且不容易收敛到最优解。牛顿法具有较快的收敛速度，但是需要计算2阶偏导数，而且目标函数的Hesse矩阵可能非正定，计算量增大的同时可能导致求解问题为病态的。拟牛顿法则克服了这个缺点，用不包含2阶导数的矩阵近似牛顿法中的Hesse矩阵的逆矩阵^[22]，从而减小了计算量。因此，本文针对SL0算法的不足，结合BFGS拟牛顿法，提出了BFGS-SL0算法。

3. BFGS-SL0算法

3.1 BFGS拟牛顿法

牛顿法的迭代公式为

${{{x}}^{{\rm{(}}k{\rm{ + 1)}}}} = {{{x}}^{(k)}} + {\lambda _k}{{{d}}^{{\rm{(}}k{\rm{)}}}}$

(6)

其中， ${{{d}}^{{\rm{(}}k{\rm{)}}}}$ 是在点 ${{{x}}^{(k)}}$ 处的牛顿方向，

${{{d}}^{{\rm{(}}k{\rm{)}}}} = - {\nabla ^2}f{{\rm\Big{(}}{{{x}}^{{\rm{(}}k{\rm{)}}}}{\rm{\Big)}}^{ - 1}}\nabla f{\rm\Big{(}}{{{x}}^{{\rm{(}}k{\rm{)}}}}{\rm{\Big)}}$

(7)

${\lambda _k}$ 是从 ${{{x}}^{(k)}}$ 出发沿牛顿方向的最优步长。

设在第 $k$ 次迭代后，得到点 ${{{x}}^{{\rm{(}}k{\rm{ + 1)}}}}$ ，将目标函数 $f{\rm{(}}{{x}}{\rm{)}}$ 在点 ${{{x}}^{{\rm{(}}k{\rm{ + 1)}}}}$ 展开为Taylor级数，并取2阶近似，得到

$\begin{aligned}f{\rm{(}}{{x}}{\rm{)}} \approx & f{\rm\Big{(}}{{{x}}^{{\rm{(}}k + 1{\rm{)}}}}{\rm{\Big) + }}\nabla f{{\rm\Big{(}}{{{x}}^{{\rm{(}}k + 1{\rm{)}}}}{\rm{\Big)}}^{\rm{T}}}{\rm\Big{(}}{{x}} - {{{x}}^{{\rm{(}}k + 1{\rm{)}}}}{\rm{\Big)}}\\& {\rm{ +\! }}\frac{1}{2}{{\rm\!\Big{(}\!}{{x}} \!-\! {{{x}}^{{\rm{(}}k + 1{\rm\!{)}}}}{\rm\!{\Big)}}^{\rm{T}}}{\nabla ^2}f{\rm\Big{(}}{{{x}}^{{\rm{(}}k + 1{\rm{)}}}}{\rm\!{\Big)\!\Big(}}{{x}}\! -\! {{{x}}^{{\rm{(}}k + 1{\rm{)}}}}{\rm{\Big)}}\end{aligned}$

(8)

由此可知，在 ${{{x}}^{{\rm{(}}k{\rm{ + 1)}}}}$ 附近有

$\nabla f{\rm{(}}{{x}}{\rm{)}} \!\approx\! \nabla f{\rm\Big{(}}{{{x}}^{{\rm{(}}k + 1{\rm{)}}}}{\rm\!{\Big{)}\!+\! }}{\nabla ^2}f{\rm\Big{(}}{{{x}}^{{\rm{(}}k \!+\! 1{\rm{)}}}}{\rm{\Big{)}\!\Big(}}{{x}} - {{{x}}^{{\rm{(}}k + 1{\rm{)}}}}{\rm\Big{)}}$

(9)

令 ${{x}} = {{{x}}^{(k)}}$ ，有

$\begin{aligned}\nabla f\!{\rm\Big{(}}\!{{{x}}^{{\rm{(}}k{\rm{)}}}}{\rm{\Big)}}\! \approx & \! \nabla f{\rm\!\Big{(}}{{{x}}^{{\rm{(}}k + 1{\rm{)}}}}{\rm{\Big)\! \!+\! }}{\nabla ^2}f{\rm\!\Big{(}}{{{x}}^{{\rm{(}}k + 1{\rm{)}}}}\!{\rm{\Big)}} \\ & \cdot {\rm{\Big(}}{{{x}}^{{\rm{(}}k{\rm{)}}}} - {{{x}}^{{\rm{(}}k + 1{\rm{)}}}}{\rm{\Big)}}\!\end{aligned}$

(10)

记

$\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!{{{p}}^{(k)}} = {{{x}}^{{\rm{(}}k + 1{\rm{)}}}} - {\rm{ }}{{{x}}^{{\rm{(}}k{\rm{)}}}}$

(11)

${{{q}}^{{\rm{(}}k{\rm{)}}}} = \nabla f{\rm\Big{(}}{{{x}}^{{\rm{(}}k + 1{\rm{)}}}}{\rm{\Big)}} - \nabla f{\rm\Big{(}}{{{x}}^{{\rm{(}}k{\rm{)}}}}{\rm{\Big)}}$

(12)

则有

${{{q}}^{{\rm{(}}k{\rm{)}}}} \approx {\nabla ^2}f{\rm\Big{(}}{{{x}}^{{\rm{(}}k + 1{\rm{)}}}}{\rm{\Big)}}{{{p}}^{(k)}}$

(13)

又设Hesse矩阵 ${\nabla ^2}f{\rm\Big{(}}{{{x}}^{{\rm{(}}k + 1{\rm{)}}}}{\rm\Big{)}}$ 可逆，则

${{{p}}^{(k)}} \approx {\nabla ^2}f{{\rm\Big{(}}{{{x}}^{{\rm{(}}k + 1{\rm{)}}}}{\rm{\Big)}}^{ - 1}}{{{q}}^{{\rm{(}}k{\rm{)}}}}$

(14)

这样，计算出 ${{{p}}^{(k)}}$ 和 ${{{q}}^{{\rm{(}}k{\rm{)}}}}$ 后，可以根据式(14)估计在 ${{{x}}^{{\rm{(}}k{\rm{ + 1)}}}}$ 处的Hesse矩阵的逆。因此，可以用不包含2阶导数的矩阵 ${{H}_{k + 1}}$ 取代牛顿法中的Hesse矩阵 ${\nabla ^2}f{\rm\Big{(}}{{{x}}^{{\rm{(}}k + 1{\rm{)}}}}{\rm{\Big)}}$ 的逆矩阵，得到拟牛顿条件

${{{p}}^{(k)}} \approx {{H}_{k + 1}}{{{q}}^{{\rm{(}}k{\rm{)}}}}$

(15)

当 ${\nabla ^2}f{{\rm\Big{(}}{{{x}}^{{\rm{(}}k + 1{\rm{)}}}}{\rm{\Big)}}^{ - 1}}$ 是 $n$ 阶对称正定矩阵时，满足拟牛顿条件的矩阵 ${{{H}}_k}$ 也应该是 $n$ 阶对称正定矩阵。构造这样近似矩阵的一般策略是， ${{{H}}_1}$ 取为任意一个 $n$ 阶对称正定矩阵，通常取 $n$ 阶单位矩阵 ${{I}}$ ，然后通过修正 ${{{H}}_k}$ 给出 ${{{H}}_{k + 1}}$ ，令

${{{H}}_{k + 1}} = {{{H}}_k} + \Delta {{{H}}_k}$

(16)

其中， $\Delta {{{H}}_k}$ 称为校正矩阵。

令

$\begin{aligned}\Delta {{{H}}_k}= & \left( {1 + \frac{{{{{q}}^{{\rm{(}}k{\rm{)}T}}}{{{H}}_k}{{{q}}^{{\rm{(}}k{\rm{)}}}}}}{{{{{p}}^{{\rm{(}}k{\rm{)}T}}}{{{q}}^{{\rm{(}}k{\rm{)}}}}}}} \right)\frac{{{{{p}}^{(k)}}{{{p}}^{{\rm{(}}k{\rm{)}T}}}}}{{{{{p}}^{{\rm{(}}k{\rm{)}T}}}{{{q}}^{{\rm{(}}k{\rm{)}}}}}}\\& - \frac{{{{{p}}^{(k)}}{{{q}}^{{\rm{(}}k{\rm{)}T}}}{{{H}}_k} + {{{H}}_k}{{{q}}^{{\rm{(}}k{\rm{)}}}}{{{p}}^{{\rm{(}}k{\rm{)}T}}}}}{{{{{p}}^{{\rm{(}}k{\rm{)}T}}}{{{q}}^{{\rm{(}}k{\rm{)}}}}}}\end{aligned}$

(17)

则得到BFGS公式：

$\begin{aligned}{{{H}}_{k + 1}} = &{{{H}}_k} + \Delta {{{H}}_k}\\ = &{{{H}}_k} + \left( {1 + \frac{{{{{q}}^{{\rm{(}}k{\rm{)}T}}}{{{H}}_k}{{{q}}^{{\rm{(}}k{\rm{)}}}}}}{{{{{p}}^{{\rm{(}}k{\rm{)}T}}}{{{q}}^{{\rm{(}}k{\rm{)}}}}}}} \right)\frac{{{{{p}}^{(k)}}{{{p}}^{{\rm{(}}k{\rm{)}T}}}}}{{{{{p}}^{{\rm{(}}k{\rm{)}T}}}{{{q}}^{{\rm{(}}k{\rm{)}}}}}} \\ & - \frac{{{{{p}}^{(k)}}{{{q}}^{{\rm{(}}k{\rm{)}T}}}{{{H}}_k} + {{{H}}_k}{{{q}}^{{\rm{(}}k{\rm{)}}}}{{{p}}^{{\rm{(}}k{\rm{)}T}}}}}{{{{{p}}^{{\rm{(}}k{\rm{)}T}}}{{{q}}^{{\rm{(}}k{\rm{)}}}}}}\end{aligned}$

(18)

3.2 BFGS-SL0算法

选取 $\sigma$ 递减序列 $\left[ {{\sigma _1},{\sigma _2}, ·\!·\!· {\sigma _{{\rm{th}}1}}, ·\!·\!· {\sigma _{{\rm{th}}2}}} \right]$ ，其中， ${\sigma _{{\rm{th}}1}}$ 与 ${\sigma _{{\rm{th}}2}}$ 为两个阈值。前已提及，牛顿法的计算速度较快，但是对初值的要求较高，同样，拟牛顿法也有这样的特点，所以本文结合最速下降法进行迭代寻优。当 $\sigma > {\sigma _{{\rm{th}}1}}$ 时利用最速下降法迭代，得到信号的某个估计值，从而可以将最优解限定在可行域内；当 $\sigma > {\sigma _{{\rm{th}}2}}$ 时，将上述估计值作为拟牛顿法的初值，利用拟牛顿法继续迭代，同时用拟牛顿条件更新迭代公式。与之前所述算法有所不同，在求解步长时，以往都是按照精确1维搜索规则，目的是让每一步迭代都能使目标函数的下降量达到最大。尽管最优步长的计算是一个单元函数的极大值问题，其计算量却是非常大的，因为在有限步内要得到严格意义下的最优步长是很困难的。从另一方面来讲，我们的目的是在整个可行域内求得最优解，没必要把主要精力放在局部方向上的线搜索。因此，本文算法采用不精确1维搜索来求得步长，只需保证每次迭代时有满意的下降量即可，从而简化计算。常用的不精确1维搜索方法有Armijo搜索、Wolfe搜索以及强Wolfe搜索等，本文选择Wolfe搜索。下面给出Wolfe搜索成立的条件：

设第 $k$ 次迭代中步长为 ${\lambda _k}$ ，则 ${\lambda _k}$ 满足

${f_k} - f\Big({{x}^{(k)}} + {\lambda _k}{{d}^{(k)}}\Big) \ge - \delta {\lambda _k}{{{g}_k}^{\!\!\!\rm{T}}}{{d}^{(k)}}$

(19)

$g{\Big({{x}^{(k)}} + {\lambda _k}{{d}^{(k)}}\Big)^{\rm{T}}} \ge \xi {{g}_k}^{\!\!\!\rm{T}}{{d}^{(k)}}$

(20)

其中， ${f_k}$ 表示 ${{x}^{(k)}}$ 处的函数值， ${{g}_k}$ 表示 ${{x}^{(k)}}$ 处的导数值， $0 < \delta < \xi < 1$ 。

BFGS-SL0算法具体步骤为：

第1步　初始化 ${{x}} = {{{Φ}} ^{\rm{T}}}{{\rm\big{(}}{{Φ}} {{{Φ}} ^{\rm{T}}}{\rm\big{)}}^{ - {\rm{1}}}}{{y}}$ ，即 ${{y}} = {{Φ}} {{x}}$ 的最小l₂范数解，其中 ${{Φ}}$ 为测量矩阵， ${{y}}$ 为测量值；选择参数 $\sigma$ 递减序列 $\left[ {{\sigma _1},{\sigma _2}, ·\!·\!·{\sigma _{{\rm{th}}1}}, ·\!·\!·{\sigma _{{\rm{th}}2}}} \right]$ ，令 ${\sigma _1} =$ $2\max {\rm{(abs(}}{{x}}{\rm{))}}$ ；初始近似矩阵 ${{{H}}_1} = {{I}}$ ，其中 ${{I}}$ 为 $n$ 阶单位矩阵；置 $k = 1$ 。

第2步　用最速下降法求解，对应于每个 ${\sigma _k}$ ，迭代L次。

(1) 计算搜索方向 ${{{d}}^{{\rm{(}}k{\rm{)}}}} = - \nabla f{\rm\Big{(}}{{{x}}^{{\rm{(}}k{\rm{)}}}}{\rm{\Big) = }}{\left[ {\displaystyle\frac{{{x_1}}}{{{\sigma ^2}}}{{\rm{e}}^{ - \frac{{{x^2}\!\!\!_{_1}}}{{2{\sigma ^2}}}}},\right.$ $\left.\displaystyle\frac{{{x_2}}}{{{\sigma ^2}}}{{\rm{e}}^{ - \frac{{{x^2}\!\!\!_{_2}}}{{2{\sigma ^2}}}}}, ·\!·\!· \displaystyle\frac{{{x_n}}}{{{\sigma ^2}}}{{\rm{e}}^{ - \frac{{{x^2}\!\!\!_{_n}}}{{2{\sigma ^2}}}}} \right]^{\rm{T}}$ ；

(2) 更新稀疏解 ${{{x}}^{(k + 1)}} = {{{x}}^{{\rm{(}}k{\rm{)}}}} + \mu {\sigma ^2}{{{d}}^{(k)}}$ ；

(3) 利用梯度投影原理得到 ${{{x}}^{(k + 1)}} = {{{x}}^{(k + 1)}} -$ ${{{Φ}} ^{\rm{T}}}{{\rm\big{(}}{{Φ}} {{{Φ}} ^{\rm{T}}}{\rm\big{)}}^{ - {\rm{1}}}}{\rm\Big{(}}{{Φ}} {{{x}}^{(k + 1)}} - {{y}}{\rm{\Big)}}$ ；

(4) 若 $\sigma > {\sigma _{{\rm{th}}1}}$ ，重复步骤(1)—步骤(3)，否则， ${{x}} = {{{x}}^{{\rm{(}}k + 1{\rm{)}}}}$ 转下一步。

第3步　用拟牛顿法求解，对应于每个 ${\sigma _k}$ ，迭代P次。

(1) 计算搜索方向 ${{{d}}^{{\rm{(}}k{\rm{)}}}} = - {{{H}}_k}\nabla f{\rm\Big{(}}{{{x}}^{{\rm{(}}k{\rm{)}}}}{\rm\Big{)}}$ ；

(2) 更新稀疏解 ${{{x}}^{(k + 1)}} = {{{x}}^{{\rm{(}}k{\rm{)}}}} + \alpha {{{d}}^{(k)}}$ ，其中 $\alpha$ 为迭代步长，通过Wolfe不精确1维搜索求得；

(4) 利用式(18)更新 ${{{H}}_k}$ ；

(5) 若 $\sigma > {\sigma _{{\rm{th}}2}}$ ，重复步骤(1)—步骤(4)，否则，得到最优解 ${{x}} = {{{x}}^{{\rm{(}}k + 1{\rm{)}}}}$ ，结束循环。

4. 计算机仿真

为了验证该算法的有效性，本文基于MATLAB R2012a平台进行了计算机仿真。实验所用测量矩阵均为高斯随机测量矩阵。以下对1维信号重构、重构误差对比、稀疏度对重构性能的影响以及2维图像重构进行仿真与分析。

4.1 1维信号的重构

图1给出了1维信号的重构仿真图。信号长度N=256，测量值个数M=128，稀疏度K=30, $\sigma$ 终值设为 $1 \times {10^{{\rm{ - }}2}}$ 。可以看出，重构信号与原始信号基本吻合，计算得到重构误差为 $5.4112 \times {10^{{\rm{ - }}4}}$ ，可见本文算法能够实现对原始信号的重构。

图 1 1维信号的重构仿真图

下载: 全尺寸图片幻灯片

4.2 重构误差对比

图2给出了本文算法与SL0算法在重构误差上的对照仿真图，基本参数与前述设置相同，进行50次独立重复实验。可以看出，本文算法重构误差远小于SL0算法，验证了本文算法在重构精度上有较大提高。

图 2 重构误差对照仿真图

下载: 全尺寸图片幻灯片

4.3 稀疏度对重构性能的影响

图3给出了稀疏度对重构性能的影响仿真图。信号长度N=256，测量值个数M=128, $\sigma$ 终值设为 $1 \times {10^{{\rm{ - }}2}}$ ，独立重复500次实验，并与SL0算法、NSL0算法、ISL0算法、L0AM算法进行对照。可以看出，当测量值一定时，对于每种算法，稀疏度增加到某个值时重构概率开始降低。相比于其他算法，当稀疏度增加到50时，BFGS-SL0算法依然可以以较高的概率重构原始信号。

图 3 稀疏度对重构性能的影响仿真图

下载: 全尺寸图片幻灯片

4.4 图像重构对照

图4和图5分别给出了不同算法下Lena图像和Cameraman图像的重构仿真图，表1和表2分别给出了不同算法下Lena图像和Cameraman图像的重构参数对照。仿真所用图像大小均为 $256 \times 256$ ，采样率均为0.5, Lena图像和Cameraman图像分别为BMP格式和TIF格式，代表不同格式的图像重构效果。对于Lena图像，由图4可以看出，BFGS-SL0算法的重构图像最清晰。由表1可知，ISL0算法相比于SL0算法重构精度略有提高，却有较慢的重构速度。本文提出的BFGS-SL0算法相比于SL0算法PSNR提高了大约2.5 dB，重构时间较SL0算法和NSL0算法略有增加，却远小于ISL0算法和L0AM算法。图5中，从直观上来看，L0AM算法的恢复图像最不清晰，BFGS-SL0算法最清晰。由表2可以看出，BFGS-SL0算法相比于经典SL0算法PSNR提高了大约3 dB，重构时间略有增加，却仍属于同一数量级。因此，本文算法在图像处理中具有较好的效果。

图 4 Lena图像重构仿真图

下载: 全尺寸图片幻灯片

表 1 Lena图像重构参数对照表

算法	相对误差	峰值信噪比(dB)	重建匹配度	重构时间(s)
SL0	0.070720	28.408407	0.988565	1.520847
NSL0	0.060162	29.754635	0.990416	1.162797
ISL0	0.062446	29.423168	0.989117	35.939030
L0AM	0.079117	27.436772	0.985986	78.190602
BFGS-SL0	0.051846	30.963193	0.991374	5.106042

下载: 导出CSV

| 显示表格

图 5 Cameraman图像重构仿真图

下载: 全尺寸图片幻灯片

表 2 Cameraman图像重构参数对照表

算法	相对误差	峰值信噪比(dB)	重建匹配度	重构时间(s)
SL0	0.074593	25.717452	0.980426	1.362892
NSL0	0.063440	27.123689	0.985850	1.018830
ISL0	0.069222	26.414663	0.983943	35.028154
L0AM	0.082170	25.002774	0.982677	68.704621
BFGS-SL0	0.053996	28.604430	0.990689	8.143261

下载: 导出CSV

| 显示表格

5. 结论

本文针对SL0算法求最优解时存在“锯齿现象”的问题，结合BFGS拟牛顿法，提出了一种改进的压缩感知信号重构算法，即BFGS-SL0算法。该算法首先利用最速下降法对初值要求不高的特点进行迭代，得到信号的某个估计值，然后将此估计值作为拟牛顿法的初值继续迭代，利用BFGS公式更新迭代方向，同时采用不精确1维搜索求取步长，从而减小了计算复杂度。经过计算机仿真，验证了该算法在重构精度、峰值信噪比和重建匹配度等方面均有较大提高。

图 1 1维信号的重构仿真图

下载: 全尺寸图片幻灯片

图 2 重构误差对照仿真图

下载: 全尺寸图片幻灯片

图 3 稀疏度对重构性能的影响仿真图

下载: 全尺寸图片幻灯片

图 4 Lena图像重构仿真图

下载: 全尺寸图片幻灯片

图 5 Cameraman图像重构仿真图

下载: 全尺寸图片幻灯片

表 1 Lena图像重构参数对照表

算法	相对误差	峰值信噪比(dB)	重建匹配度	重构时间(s)
SL0	0.070720	28.408407	0.988565	1.520847
NSL0	0.060162	29.754635	0.990416	1.162797
ISL0	0.062446	29.423168	0.989117	35.939030
L0AM	0.079117	27.436772	0.985986	78.190602
BFGS-SL0	0.051846	30.963193	0.991374	5.106042

下载: 导出CSV

表 2 Cameraman图像重构参数对照表

算法	相对误差	峰值信噪比(dB)	重建匹配度	重构时间(s)
SL0	0.074593	25.717452	0.980426	1.362892
NSL0	0.063440	27.123689	0.985850	1.018830
ISL0	0.069222	26.414663	0.983943	35.028154
L0AM	0.082170	25.002774	0.982677	68.704621
BFGS-SL0	0.053996	28.604430	0.990689	8.143261

下载: 导出CSV

参考文献(22)

CANDES E J, ROMBERG J, and TAO T. Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information[J]. IEEE Transactions on Information Theory, 2006, 52(2): 489–509 doi: 10.1109/TIT.2005.862083

DONOHO D L. Compressed sensing[J]. IEEE Transactions on Information Theory, 2006, 52(4): 1289–1306 doi: 10.1109/TIT.2006.871582

CANDES E J and TAO T. Near-optimal signal recovery from random projections: universal encoding strategies[J]. IEEE Transactions on Information Theory, 2006, 52(12): 5406–5425 doi: 10.1109/TIT.2006.885507

周燕, 曾凡智. 基于二维压缩感知和分层特征的图像检索算法[J]. 电子学报, 2016, 44(2): 453–460 doi: 10.3969/j.issn.0372-2112.2016.02.029

ZHOU Yan and ZENG Fanzhi. An image retrieval algorithm based on two-dimensional compressive sensing and hierarchical feature[J]. Acta Electronica Sinica, 2016, 44(2): 453–460 doi: 10.3969/j.issn.0372-2112.2016.02.029

SHARMA S K, LAGUNAS E, CHATZINOTAS S, et al. Application of compressive sensing in cognitive radio communications: A survey[J]. IEEE Communications Surveys&Tutorials, 2016, 18(3): 1838–1860 doi: 10.1109/COMST.2016.2524443

程银波, 司菁菁, 候肖兰. 适用于无线传感器网络的层次化分布式压缩感知[J]. 电子与信息学报, 2017, 39(3): 539–545 doi: 10.11999/JEIT160439

CHENG Yinbo, SI Jingjing, and HOU Xiaolan. Hierarchical distributed compressed sensing for wireless sensor network[J]. Journal of Electronics&Information Technology, 2017, 39(3): 539–545 doi: 10.11999/JEIT160439

李少东, 杨军, 陈文峰, 等. 基于压缩感知理论的雷达成像技术与应用研究进展[J]. 电子与信息学报, 2016, 38(2): 495–508 doi: 10.11999/JEIT150874

LI Shaodong, YANG Jun, CHEN Wenfeng, et al. Overview of radar imaging technique and application based on compressive sensing theory[J]. Journal of Electronics&Information Technology, 2016, 38(2): 495–508 doi: 10.11999/JEIT150874

王峰, 向新, 易克初, 等. L0范数平滑逼近的稳健求解算法[J]. 电子与信息学报, 2015, 37(10): 2377–2382 doi: 10.11999/JEIT141590

WANG Feng, XIANG Xin, YI Kechu, et al. Robust computational methods for smoothed L0 approximation[J]. Journal of Electronics&Information Technology, 2015, 37(10): 2377–2382 doi: 10.11999/JEIT141590

TAN Mingkui, TSANG I W, and WANG Li. Matching pursuit LASSO Part I: Sparse recovery over big dictionary[J]. IEEE Transactions on Signal Processing, 2015, 63(3): 727–741 doi: 10.1109/TSP.2014.2385036

TROPP J A and GILBERT A C. Signal recovery from random measurements via orthogonal matching pursuit[J]. IEEE Transactions on Information Theory, 2007, 53(12): 4655–4666 doi: 10.1109/TIT.2007.909108

田金鹏, 刘小娟, 郑国莘. 一种变步长稀疏度自适应子空间追踪算法[J]. 自动化学报, 2016, 42(10): 1512–1519 doi: 10.16383/j.aas.2016.c150801

TIAN Jinpeng, LIU Xiaojuan, and ZHENG Guoxin. A variable step size sparse adaptive subspace tracking algorithm[J]. Journal of Automation, 2016, 42(10): 1512–1519 doi: 10.16383/j.aas.2016.c150801

MODHA V and BUTANI R. Compressive sensing in speech from LPC using gradient projection for sparse reconstruction[J]. International Journal of Engineering Research&Applications, 2015, 5(2): 6–8.

董腾. 基于内点法压缩感知重构算法的研究[D]. [博士论文], 河北工业大学, 2014.

DONG Teng. Research on compressed sensing algorithm based on interior point method[D]. [Ph.D. dissertation], Hebei University of Technology, 2014.

MOHIMANI H, BABAIE-ZADEH M, and JUTTEN C. A fast approach for overcomplete sparse decomposition based on smoothed l₀ norm[J]. IEEE Transactions on Signal Processing, 2009, 57(1): 289–301 doi: 10.1109/TSP.2008.2007606

林婉娟, 赵瑞珍, 李浩. 用于压缩感知信号重建的NSL0算法[J]. 新型工业化, 2011, 1(7): 78–84

LIN Wanjuan, ZHAO Ruizhen, and LI Hao. The NSL0 algorithm for compressive sensing signal reconstruction[J]. New industrialization, 2011, 1(7): 78–84

杨良龙, 赵生妹, 郑宝玉, 等. 基于SL0压缩感知信号重建的改进算法[J]. 信号处理, 2012, 28(6): 834–841

YANG Lianglong, ZHAO Shengmei, ZHENG Baoyu, et al. The improved reconstruction algorithm for compressive sensing on SL0[J]. Signal Processing, 2012, 28(6): 834–841

王军华, 黄知涛, 周一宇. 稀疏信号重构的迭代平滑 l₀范数最小化算法[J]. 宇航学报, 2012, 33(5): 642–647 doi: 10.3873/j.issn.1000-1328.2012.05.017

WANG Junhua, HUANG Zhitao, and ZHOU Yiyu. Sparse signal reconstruction based on iterative smoothed l₀ norm minimization[J]. Journal of Astronautics, 2012, 33(5): 642–647 doi: 10.3873/j.issn.1000-1328.2012.05.017

YE X, ZHU W P, ZHANG A, et al. Sparse channel estimation of MIMO-OFDM systems with unconstrained smoothed l₀-norm-regularized least squares compressed sensing[J]. EURASIP Journal on Wireless Communications&Networking, 2013, 2013(1): 282–294 doi: 10.1186/1687-1499-2013-282

MOHAMMADI M R, Fatemizadeh E, and MAHOOR M H. Non-negative sparse decomposition based on constrained smoothed l₀ norm[J]. Signal Processing, 2014, 100: 42–50.

李颖, 王泽, 王军华, 等. 基于 l₀范数近似最小化的稀疏信号重构方法[J]. 计算机工程与应用, 2015, 51(10): 200–204 doi: 10.3778/j.issn.1002-8331.1309-0500

LI Ying, WANG Ze, WANG Junhua, et al. Sparse signal reconstruction based on l₀ norm approximation minimization[J]. Computer Engineering and Applications, 2015, 51(10): 200–204 doi: 10.3778/j.issn.1002-8331.1309-0500

高睿, 赵瑞珍, 胡绍海. 基于压缩感知的变步长自适应匹配追踪重建算法[J]. 光学学报, 2010, 30(6): 1639–1644

GAO Rui, ZHAO Ruizhen, and HU Shaohai. Variable step size adaptive matching pursuit algorithm for image reconstruction based on compressive sensing[J]. Acta Optica Sinica, 2010, 30(6): 1639–1644

陈宝林. 最优化理论与算法[M]. 第2版, 北京: 清华大学出版社, 2005: 306–314.

CHEN Baolin. Optimization Theory and Algorithm[M]. Second Edition, Beijing: Tsinghua University Press, 2005: 306–314.

施引文献

期刊类型引用(10)

1.	赵东波，李辉. 基于改进平滑L0算法的图像重构. 信息技术. 2023(09): 103-107+113 . 百度学术
2.	张小贝，唐辰，涂喜梅，陆晓刚，张琦. 基于自适应分块和联合优化光滑l_0范数的二维压缩感知算法. 电子与信息学报. 2023(12): 4431-4439 . 本站查看
3.	陶亮，刘海鹏，王蒙. 基于压缩感知理论NSL0算法的改进. 电子技术应用. 2021(05): 77-81 . 百度学术
4.	刘洲洲，张倩昀，马新华，彭寒. 基于优化离散差分进化算法的压缩感知信号重构. 吉林大学学报(工学版). 2021(06): 2246-2252 . 百度学术
5.	申滨，吴和彪，崔太平，陈前斌. 基于最优索引广义正交匹配追踪的非正交多址系统多用户检测. 电子与信息学报. 2020(03): 621-628 . 本站查看
6.	周琦宾，吴静. 基于SL0压缩感知的SAR图像重构方法. 传感器与微系统. 2020(03): 72-75+86 . 百度学术
7.	彭丽维，张彼德，孔令瑜，梅婷. 监督自适应核熵成分分析特征提取的电力变压器故障诊断. 高压电器. 2020(06): 249-255+261 . 百度学术
8.	桑遥，尹君，王迪，王皓，景康. 基于增强重引力搜索的高维数据协同聚类算法. 计算机应用与软件. 2020(10): 300-306 . 百度学术
9.	吉爱国，刘伟平，刘志强. 基于近似l_0范数的实数化DOA估计. 计算机应用与软件. 2020(11): 328-333 . 百度学术
10.	于涵，水鹏朗，施赛楠，杨春娇. 广义Pareto分布海杂波模型参数的组合双分位点估计方法. 电子与信息学报. 2019(12): 2836-2843 . 本站查看

其他类型引用(15)

资源附件(0)

访问统计

图(5) / 表(2)

计量

文章访问数: 2087
HTML全文浏览量: 1022
PDF下载量: 268
被引次数: 25

1. 引言
2. SL0算法
3. BFGS-SL0算法
3.1 BFGS拟牛顿法
3.2 BFGS-SL0算法
4. 计算机仿真
4.1 1维信号的重构
4.2 重构误差对比
4.3 稀疏度对重构性能的影响
4.4 图像重构对照
5. 结论

姓名
邮箱
手机号码
标题
留言内容
验证码

留言板

基于BFGS拟牛顿法的压缩感知SL0重构算法

doi: 10.11999/JEIT170813

作者简介:
孙娜：女，1975年生，副教授，研究方向为信号处理与压缩感知

刘继文：男，1990年生，硕士，研究方向为压缩感知

肖东亮：男，1968年生，副教授，研究方向为无线通信与信息安全

通讯作者:
孙娜　 sunnacau@126.com

计量

SL0 Reconstruction Algorithm for Compressive Sensing Based on BFGS Quasi Newton Method

1. 引言

2. SL0算法

3. BFGS-SL0算法

3.1 BFGS拟牛顿法

3.2 BFGS-SL0算法

4. 计算机仿真

4.1 1维信号的重构

4.2 重构误差对比

4.3 稀疏度对重构性能的影响

4.4 图像重构对照

5. 结论

期刊类型引用(10)

其他类型引用(15)

计量

目录

1. 引言

2. SL0算法

3. BFGS-SL0算法

3.1 BFGS拟牛顿法

3.2 BFGS-SL0算法

4. 计算机仿真

4.1 1维信号的重构

4.2 重构误差对比

4.3 稀疏度对重构性能的影响

4.4 图像重构对照

5. 结论

留言板

基于BFGS拟牛顿法的压缩感知SL0重构算法

doi: 10.11999/JEIT170813

作者简介: 孙娜：女，1975年生，副教授，研究方向为信号处理与压缩感知 刘继文：男，1990年生，硕士，研究方向为压缩感知 肖东亮：男，1968年生，副教授，研究方向为无线通信与信息安全

通讯作者: 孙娜 sunnacau@126.com

计量

出版历程

SL0 Reconstruction Algorithm for Compressive Sensing Based on BFGS Quasi Newton Method

1. 引言

2. SL0算法

3. BFGS-SL0算法

3.1 BFGS拟牛顿法

3.2 BFGS-SL0算法

4. 计算机仿真

4.1 1维信号的重构

4.2 重构误差对比

4.3 稀疏度对重构性能的影响

4.4 图像重构对照

5. 结论

期刊类型引用(10)

其他类型引用(15)

计量

出版历程

目录

1. 引言

2. SL0算法

3. BFGS-SL0算法

3.1 BFGS拟牛顿法

3.2 BFGS-SL0算法

4. 计算机仿真

4.1 1维信号的重构

4.2 重构误差对比

4.3 稀疏度对重构性能的影响

4.4 图像重构对照

5. 结论

作者简介:
孙娜：女，1975年生，副教授，研究方向为信号处理与压缩感知

刘继文：男，1990年生，硕士，研究方向为压缩感知

肖东亮：男，1968年生，副教授，研究方向为无线通信与信息安全

通讯作者:
孙娜　 sunnacau@126.com