﻿ 基于反馈神经网络的稀疏信号恢复的优化算法
 计算机应用   2017, Vol. 37 Issue (9): 2590-2594  DOI: 10.11772/j.issn.1001-9081.2017.09.2590 0

### 引用本文

WANG Xingxing, LI Guocheng. Sparse signal reconstruction optimization algorithm based on recurrent neural network[J]. Journal of Computer Applications, 2017, 37(9): 2590-2594. DOI: 10.11772/j.issn.1001-9081.2017.09.2590.

### 文章历史

Sparse signal reconstruction optimization algorithm based on recurrent neural network
WANG Xingxing, LI Guocheng
College of Science, Beijing Information Science and Technology University, Beijing 100192, China
Abstract: Aiming at the problem of sparse signal reconstruction, an optimization algorithm based on Recurrent Neural Network (RNN) was proposed. Firstly, the signal sparseness was represented, and the mathematical model was transformed into an optimization problem. Then, based on the fact that the l0-norm is a non-convex and non-differentiable function, and the optimization problem is NP-hard, under the premise that the measurement matrix A met Restricted Isometry Property (RIP), the equivalent optimization problem was proposed. Finally, the corresponding Hopfield RNN model was established to solve the equivalent optimization problem, so as to reconstruct sparse signals. The experimental results show that under different observation number m, compared the RNN algorithm and the other three algorithms, it is found that the relative error of the RNN algorithm is smaller and the observations number is smaller, and the RNN algorithm can reconstruct the sparse signals efficiently.
Key words: l0 optimization    Recurrent Neural Network (RNN)    Restricted Isometry Property (RIP)    energy function
0 引言

 $\mathit{\boldsymbol{s}} = \sum\limits_{i = 1}^n {{\psi _i}{x_i}} = {\mathit{\boldsymbol{\psi }}^\rm{T}}\mathit{\boldsymbol{x}}$ (1)

Candès等[2]指出若压缩感知矩阵A满足有限等距性(Restricted Isometry Property, RIP)条件，并且x为稀疏度为k的信号，那么可以通过求解下面的l0范数最小化问题便可以精确地恢复x:

 $\left\{ \begin{array}{l} \min {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\left\| \mathit{\boldsymbol{x}} \right\|_0}\\ {\rm{s}}{\rm{.t}}{\rm{.}}{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} \mathit{\boldsymbol{Ax}} = \mathit{\boldsymbol{b}} \end{array} \right.$ (2)

 图 1 压缩感知理论框架 Figure 1 Theoretical framework of compressive sensing

 $\left\{ \begin{array}{l} \min {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\left\| \mathit{\boldsymbol{x}} \right\|_1}\\ {\rm{s}}{\rm{.t}}{\rm{.}}{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} \mathit{\boldsymbol{Ax}} = \mathit{\boldsymbol{b}} \end{array} \right.$ (3)

 ${\kern 1pt} {\kern 1pt} (1 - {\delta _k}{\kern 1pt} )\left\| \mathit{\boldsymbol{x}} \right\|_2^2 \leqslant \left\| {\mathit{\boldsymbol{Ax}}} \right\|_2^2 \leqslant (1 + {\delta _k})\left\| \mathit{\boldsymbol{x}} \right\|_2^2$

δk < 1，则称测量矩阵A满足k阶RIP。特别地，当δ2k < $\sqrt 2$-1 < 1时, l0范数与l1范数是等价的[4]

1 反馈神经网络算法 1.1 反馈神经网络

 $\left\{ \begin{array}{l} \min\ f(\mathit{\boldsymbol{x}})\\ {\rm{s}}{\rm{.t}}{\rm{.}} \ h(\mathit{\boldsymbol{x}}) = 0 \end{array} \right.$ (4)

 $\begin{array}{l} F(\mathit{\boldsymbol{x}}, {M_1}) = {[{(f(\mathit{\boldsymbol{x}})-{M_1})^ + }]^2} = \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\left\{ \begin{array}{l} \frac{1}{2}{(f(\mathit{\boldsymbol{x}}) - {M_1})^2},{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} f(\mathit{\boldsymbol{x}}) \geqslant {M_1}\\ 0,{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} f(\mathit{\boldsymbol{x}}) < {M_1} \end{array} \right. \end{array}$

 $\nabla F(\mathit{\boldsymbol{x}}, {M_1}) = \left\{ \begin{array}{l} (f(\mathit{\boldsymbol{x}}) - {M_1})\nabla f(\mathit{\boldsymbol{x}}),{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} f(\mathit{\boldsymbol{x}}) \geqslant {M_1}\\ 0,{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} f(\mathit{\boldsymbol{x}}) < {M_1} \end{array} \right.$

 $\min \ E(\mathit{\boldsymbol{x}}, {{M}_{1}})=F(\mathit{\boldsymbol{x}}, {{M}_{1}})+\frac{1}{2}h{{(\mathit{\boldsymbol{x}})}^{\rm{T}}}h(\mathit{\boldsymbol{x}})$ (5)

 \left\{ \begin{align} & \frac{\rm{d}\mathit{\boldsymbol{x}}}{\rm{d}\mathit{t}}=-\nabla E(\mathit{\boldsymbol{x}}, {{M}_{1}}) \\ & \mathit{\boldsymbol{x}}({{t}_{0}})={{\mathit{\boldsymbol{x}}}_{0}} \\ \end{align} \right. (6)

 $\sqrt{E(\mathit{\boldsymbol{x}}_{1}^{*}, {{M}_{1}})}\leqslant \sqrt{E({{\mathit{\boldsymbol{x}}}^{*}}, {{M}_{1}})}=\frac{1}{2}(f({{\mathit{\boldsymbol{x}}}^{*}})-{{M}_{1}})$

${{M}_{2}}={{M}_{1}}+2\sqrt{E(\mathit{\boldsymbol{x}}_{1}^{*}, {{M}_{1}})}\leqslant f({{\mathit{\boldsymbol{x}}}^{*}})$，则M2是最优目标函数f(x*)的一个下界。以M2作为优化问题(4) 的一个新下界，即M2f(x*)。

 $E(\mathit{\boldsymbol{x}}, {{M}_{2}})={{[{{(f(\mathit{\boldsymbol{x}})-{{M}_{2}})}^{+}}]}^{2}}+\frac{1}{2}\mathit{h}{{(\mathit{\boldsymbol{x}})}^{\rm{T}}}\mathit{h}(\mathit{\boldsymbol{x}})$ (7)

 $\min \ E(\mathit{\boldsymbol{x}}, {{M}_{2}})$ (8)

 \left\{ \begin{align} & \frac{\rm{d}\mathit{\boldsymbol{x}}}{\rm{d}\mathit{t}}=-\nabla E(\mathit{\boldsymbol{x}}, {{M}_{2}}) \\ & \mathit{\boldsymbol{x}}({{t}_{0}})=\mathit{\boldsymbol{x}}_{1}^{\rm{*}} \\ \end{align} \right.;k=0, 1, \cdots (9)

 ${{M}_{k+1}}={{M}_{k}}+2\sqrt{E(\mathit{\boldsymbol{x}}_{k}^{*}, {{M}_{k}})}$

 $\min \ E(\mathit{\boldsymbol{x}}, {{M}_{k}})$ (10)

 $\min \ E(\mathit{\boldsymbol{x}}, {{M}_{k+1}})$ (11)

 \left\{ \begin{align} & \frac{\rm{d}\mathit{\boldsymbol{x}}}{\rm{d}\mathit{t}}=-\nabla E(\mathit{\boldsymbol{x}}, {{M}_{k+1}}) \\ & \mathit{\boldsymbol{x}}({{t}_{0}})=\mathit{\boldsymbol{x}}_\mathit{k}^{\rm{*}} \\ \end{align} \right.;k=0, 1, \cdots (12)

1.2 稀疏信号的恢复

 ${{\left\| \mathit{\boldsymbol{x}} \right\|}_{1}}\approx f(\mathit{\boldsymbol{x}})=\sum\limits_{i=1}^{n}{\frac{\rm{ln}(\rm{cosh}(\mathit{a}{{\mathit{x}}_{\mathit{i}}}))}{a}}$
 图 2 目标函数(n=1时) Figure 2 Objective function (n=1)
 图 3 激活函数y′=tanh(x) Figure 3 Activation function y′=tanh(x)

 \left\{ \begin{align} & \min \frac{1}{a}\sum\limits_{i=1}^{n}{\ln (\cosh (\mathit{a}{{\mathit{x}}_{\mathit{i}}}))} \\ & \rm{s}\rm{.t}\rm{.}\ \ \ \ \mathit{\boldsymbol{b}}\rm{-}\mathit{\boldsymbol{Ax}}=0 \\ \end{align} \right. (13)

 $F(\mathit{\boldsymbol{x}}, {{M}_{1}})=\frac{1}{2}f{{(\mathit{\boldsymbol{x}})}^{2}}$

 $\nabla E(\mathit{\boldsymbol{x}}, {{M}_{1}})=f(\mathit{\boldsymbol{x}})\nabla f(\mathit{\boldsymbol{x}})+{{(\mathit{\boldsymbol{Ax}}-\mathit{\boldsymbol{b}})}^{\rm{T}}}\mathit{\boldsymbol{A}}$

 \left\{ \begin{align} & \frac{\rm{d}\mathit{\boldsymbol{x}}}{\rm{d}\mathit{t}}=-f(\mathit{\boldsymbol{x}})\nabla f(\mathit{\boldsymbol{x}})-{{(\mathit{\boldsymbol{Ax}}-\mathit{\boldsymbol{b}})}^{\rm{T}}}\mathit{\boldsymbol{A}} \\ & {\mathit{\boldsymbol{x}}}({{t}_{0}})={{\mathit{\boldsymbol{x}}}_{0}} \\ \end{align} \right. (14)
2 稳定性与收敛性分析

1) 先证f(xk*)≤f(x*)。

 \begin{align} & f({{\mathit{\boldsymbol{x}}}^{*}})\geqslant {{M}_{k+1}}={{M}_{k}}+2\sqrt{E(\mathit{\boldsymbol{x}}_{k}^{*}, {{M}_{k}})}\geqslant \\ & \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ {{M}_{k}}+2{{[f(x_{k}^{*})-{{M}_{k}}]}^{+}} \\ \end{align}

① 当f(xk*)≥Mk时，f(x*)≥Mk+f(xk*)-Mkf(xk*)。

② 当f(xk*) < Mk时，f(x*)≥Mk > f(xk*)，所以f(xk*)≤f(x*)。

2) 下证序列{xk*}收敛到问题(13) 的一个可行解。

3 停时条件

4 仿真实验

 ${\kern 1pt} {R_{{\rm{total}}}} = {\left\| {\mathit{\boldsymbol{x}} - \mathit{\boldsymbol{\hat x}}} \right\|_2}/{\left\| \mathit{\boldsymbol{x}} \right\|_2}$

1) 产生k稀疏信号xRn, k个非零元素的位置是随机产生的，满足[1, n]的均匀随机分布。相应的非零元素的大小也是随机产生的。

3) 计算观测向量：b=Ax，其中bRm

 图 4 原始稀疏信号 Figure 4 Original sparse signal
 图 5 观测向量b Figure 5 Observation vector b

2) 产生观测矩阵ARm×n，矩阵的所有元素是随机生成的并且服从高斯分布N(0, 1)，rank(A)=m

 图 6 ${\mathit{\boldsymbol{\hat x}}}$的状态变化曲线 Figure 6 State change curve of optimal solution

 图 7 测量数m与成功恢复的概率关系(n=256) Figure 7 Probability relation between number of measurements and successful recovery (n=256)
 图 8 稀疏度k与成功恢复的概率关系(n=256) Figure 8 Probability relation between sparsity k and successful recovery (n=256)

5 结语

 [1] CANDÈS E J, ROMBERG J K, TAO T. Stable signal recovery from incomplete and inaccurate measurements[J]. Communications on Pure and Applied Mathematics, 2006, 59(8): 1207-1223. DOI:10.1002/(ISSN)1097-0312 [2] CANDÈS E J, ROMBERG J, 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 [3] 尹宏鹏, 刘兆栋, 柴毅, 等. 压缩感知综述[J]. 控制与决策, 2013, 28(10): 1441-1445. (YIN H P, LIU Z D, CHAI Y, et al. Survey of compressed sensing[J]. Control and Decision, 2013, 28(10): 1441-1445.) [4] FOUCART S, LAI M J. Sparsest solutions of underdetermined linear systems via $\ell$q-minimization for 0 < q≤1[J]. Applied and Computational Harmonic Analysis, 2009, 26(3): 395-407. DOI:10.1016/j.acha.2008.09.001 [5] BLUMENSATH T, DAVIES M E. Gradient pursuits[J]. IEEE Transactions on Signal Processing, 2008, 56(6): 2370-2382. DOI:10.1109/TSP.2007.916124 [6] DAI W, MILENKOVIC O. Subspace pursuit for compressive sensing signal reconstruction[J]. IEEE Transactions on Information Theory, 2009, 55(5): 2230-2249. DOI:10.1109/TIT.2009.2016006 [7] MALLAT S G, ZHANG Z F. Matching pursuits with time-frequency dictionaries[J]. IEEE Transactions on Signal Processing, 1993, 41(12): 3397-3415. DOI:10.1109/78.258082 [8] FIGUEIREDO M A T, NOWAK R D, WRIGHT S J. Gradient projection for sparse reconstruction:application to compressed sensing and other inverse problems[J]. IEEE Journal of Selected Topics in Signal Processing, 2007, 1(4): 586-597. DOI:10.1109/JSTSP.2007.910281 [9] CHEN S S, DONOHO D L, SAUNDERS M A. Atomic decomposition by basis pursuit[J]. SIAM Journal on Scientific Computing, 1998, 20(1): 33-61. DOI:10.1137/S1064827596304010 [10] NEEDELL D, TROPP J A. CaSaMP:iterative signal recovery from incomplete and inaccurate samples[J]. Applied and Computational Harmonic Analysis, 2008, 26(3): 301-321. [11] 李珅, 马彩文, 李艳, 等. 压缩感知重构算法综述[J]. 红外与激光工程, 2013, 42(S1): 225-232. (LI S, MA C W, LI Y, et al. Survey on reconstruction algorithm based on compressive sensing[J]. Infrared and Laser Engineering, 2013, 42(S1): 225-232.) [12] BOGACKI P, SHAMPINE L F. A 3(2) pair of Runge-Kutta formulas[J]. Applied Mathematics Letters, 1989, 2(4): 321-325. DOI:10.1016/0893-9659(89)90079-7 [13] 李国成, 宋士吉, 吴澄. 解决非可微凸优化问题的次梯度反馈神经网络[J]. 中国科学(E辑), 2006, 36(8): 811-824. (LI G C, SONG S J, WU C. Sub-gradient feedback neural network for solving non-differentiable convex optimization[J]. SCIENCE CHINA Sev. E Information Sciences, 2006, 36(8): 811-824.) [14] 曾喆昭. 神经网络优化方法及其在信息处理中的应用研究[D]. 长沙: 湖南大学, 2008: 62-73. (ZENG Z Z. Neural network optimization method and its application in information processing[D]. Changsha:Hunan University, 2008:62-73.) http://cdmd.cnki.com.cn/Article/CDMD-10532-2009083750.htm [15] XIA Y, FENG G, WANG J. A novel recurrent neural network for solving nonlinear optimization problems with inequality constraints[J]. IEEE Transactions on Neural Networks, 2008, 19(8): 1340-1353. DOI:10.1109/TNN.2008.2000273 [16] LIU Q, WANG J. A one-layer recurrent neural network with a discontinuous hard-limiting activation function for quadratic programming[J]. IEEE Transactions on Neural Networks, 2008, 19(4): 558-570. DOI:10.1109/TNN.2007.910736 [17] LEUNG C S, SUM J, CONSTANTINIDES A G. Recurrent networks for compressive sampling[J]. Neurocomputing, 2014, 129: 298-305. DOI:10.1016/j.neucom.2013.09.028 [18] LIU Q, WANG J. A one-layer recurrent neural network with a discontinuous activation function for linear programming[J]. Neural Computation, 2008, 20(5): 1366-1383. DOI:10.1162/neco.2007.03-07-488