基于反饋神經(jīng)網(wǎng)絡(luò)的稀疏信號恢復(fù)的優(yōu)化算法

汪星星，李國成

(北京信息科技大學(xué) 理學(xué)院，北京 100192)(*通信作者電子郵箱wangxx501@163.com)

基于反饋神經(jīng)網(wǎng)絡(luò)的稀疏信號恢復(fù)的優(yōu)化算法

汪星星*，李國成

(北京信息科技大學(xué) 理學(xué)院，北京 100192)(*通信作者電子郵箱wangxx501@163.com)

針對稀疏信號的重構(gòu)問題，提出了一種基于反饋神經(jīng)網(wǎng)絡(luò)(RNN)的優(yōu)化算法。首先，需要對信號進行稀疏表示，將數(shù)學(xué)模型化為優(yōu)化問題；接著，基于l0范數(shù)是非凸且不可微的函數(shù)，并且該優(yōu)化問題是NP難的，因此在測量矩陣A滿足有限等距性質(zhì)(RIP)的前提下，提出等價優(yōu)化問題；最后，通過建立相應(yīng)的Hopfield反饋神經(jīng)網(wǎng)絡(luò)模型來解決等價的優(yōu)化問題，從而實現(xiàn)稀疏信號的重構(gòu)。實驗結(jié)果表明，在不同觀測次數(shù)m下，對比RNN算法和其他三種算法的相對誤差，發(fā)現(xiàn)RNN算法相對誤差小，且需要的觀測數(shù)也少，能夠高效地重構(gòu)稀疏信號。

l0最優(yōu)化；反饋神經(jīng)網(wǎng)絡(luò)；有限等距性；能量函數(shù)

0 引言

壓縮感知理論近年來在各研究領(lǐng)域都得到了廣泛的應(yīng)用，例如醫(yī)學(xué)成像、CT斷層掃描、機器學(xué)習(xí)等。2006年Candès等[1]指出：當信號具有稀疏特性時，可以通過遠小于信號長度的少量觀測值來精確地重構(gòu)稀疏信號。但是一般的自然信號s本身并不是稀疏的，需要在某種稀疏基上進行稀疏表示。不妨給定有限長離散信號s，信號稀疏度為k(即含有k個非零值)，則s可以表示成一組正交基的線性組合：

(1)

其中ψ=[ψ1,ψ2,…,ψn]是一組正交基。

Candès等[2]指出若壓縮感知矩陣A滿足有限等距性(Restricted Isometry Property, RIP)條件，并且x為稀疏度為k的信號，那么可以通過求解下面的l0范數(shù)最小化問題便可以精確地恢復(fù)x:

(2)

其中：‖x‖0指的是非零元素的個數(shù)，A是傳感矩陣。

壓縮感知主要包括信號的稀疏表示、觀測矩陣的設(shè)計以及稀疏信號恢復(fù)三個方面[3]，主要是通過非線性的重構(gòu)算法(最優(yōu)化方法)來恢復(fù)信號。

圖1 壓縮感知理論框架

由于Ax=b是欠定的，‖·‖0是非凸不可微函數(shù)，并且問題(2)是NP難的，因此通常采用l1范數(shù)來替代l0范數(shù)，那么重構(gòu)稀疏信號的問題即變成了求解優(yōu)化問題(3)：

(3)

定義1 定義測量矩陣A的RIP參數(shù)δk滿足下式的最小值δ：

其中x為k階稀疏信號。

一般有兩大類算法對問題(3)進行近似求解，即貪婪追蹤法和凸松弛法， 文獻[5-9]提出利用匹配追蹤算法(Matching Pursuit, MP)和正交追蹤算法(Orthogonal Matching Pursuit, OMP)來求解l0最小范數(shù)問題，大大地提高了計算速度，且易于實現(xiàn)，但是恢復(fù)能力不強。由于傳統(tǒng)貪婪算法在抗噪方面不是很強，文獻[10]提出了具有較強魯棒性的壓縮采樣匹配追蹤(Compressive Sampling Matching Pursuit, CoSaMP)，但由于CoSaMP算法需要已知信號的稀疏度k，而實際應(yīng)用中信號的稀疏度k往往是未知的。因此CoSaMP算法在解決稀疏信號重構(gòu)問題上存在一些問題。MP算法來源于貪婪追蹤算法，特點是計算復(fù)雜度低，但需要較多的觀測值，重構(gòu)精度低；而OMP算法和CoSaMP算法具有良好的穩(wěn)定性和理論保證，但僅針對大規(guī)模的問題恢復(fù)率較高。凸松弛算法，這類方法通過將非凸問題轉(zhuǎn)化為凸問題求解找到信號的逼近，其中最常用的方法就是基追蹤(Basis Pursuit, BP)[11]，該方法提出利用l1范數(shù)替代l0范數(shù)來解決最優(yōu)化問題。這兩大類算法在較高的稀疏度下或在較低的觀測度下，都很難對高斯信號進行高效重構(gòu)。

1 反饋神經(jīng)網(wǎng)絡(luò)算法

1.1 反饋神經(jīng)網(wǎng)絡(luò)

鑒于上述算法所存在的弊端，本文采用神經(jīng)網(wǎng)絡(luò)算法來解決壓縮感知理論中的信號恢復(fù)問題。主要從以下幾個方面展開工作：第一部分是建立非線性等式約束優(yōu)化問題相應(yīng)的反饋神經(jīng)網(wǎng)絡(luò)(Recurrent Neural Network, RNN)，為便于研究，接著選取合適的凸函數(shù)f(x)來逼近‖x‖1,隨后根據(jù)梯度下降思想建立神經(jīng)動力學(xué)方程；第二部分探討所建立的反饋神經(jīng)網(wǎng)絡(luò)的穩(wěn)定性、收斂性和收斂速度與步長的關(guān)系等因素；第三部分給出網(wǎng)絡(luò)的停時條件以及算法具體步驟；第四部分是隨機生成離散信號，利用神經(jīng)網(wǎng)絡(luò)重構(gòu)離散信號，并且與已有的重構(gòu)算法進行對比，從而說明反饋神經(jīng)網(wǎng)絡(luò)算法的有效性和準確性。

不論是l0范數(shù)最小化還是l1范數(shù)最小化問題都可以歸結(jié)為帶約束的優(yōu)化問題。其中一類通過設(shè)計一系列反饋神經(jīng)網(wǎng)絡(luò)求解帶約束的優(yōu)化問題的方法統(tǒng)稱為神經(jīng)動力學(xué)優(yōu)化方法。以下是一個非線性等式約束優(yōu)化問題：

(4)

其中：x∈Rn，f:Rn→R是目標函數(shù)，h:Rn→Rm(m

假設(shè)x*是問題(4)的一個最優(yōu)解，M1是目標函數(shù)f(x)的一個下界，即M1≤f(x*)。函數(shù)[5]：

F(x,M1)=[(f(x)-M1)+]2=

由于F(x,M1)是連續(xù)可微的非減凸函數(shù)，并且:

考慮凸優(yōu)化問題：

(5)

根據(jù)梯度下降法，可以建立求解問題(5)的神經(jīng)網(wǎng)絡(luò)：

(6)

類似地，再次作能量函數(shù)：

(7)

得到相應(yīng)問題(7)的子凸優(yōu)化問題：

minE(x,M2)

(8)

(9)

基于逐步迭代連續(xù)近似的思想，令：

minE(x,Mk)

(10)

minE(x,Mk+1)

(11)

相應(yīng)的神經(jīng)子網(wǎng)絡(luò)模型：

(12)

1.2 稀疏信號的恢復(fù)

結(jié)合式(3)和式(4)，考慮建立反饋神經(jīng)網(wǎng)絡(luò)來解決問題(3)，由于算子‖·‖1在xi=0處不可微，因此不妨考慮凸函數(shù)f(xi)=ln(cosh(axi))/a(其中a>1)來近似逼近‖x‖1，從圖2可以看出a越大，該近似效果越精確：

對于函數(shù)y=ln(cosh(ax))/a，有y′=tanh(ax)，并且雙曲正切函數(shù)是嚴格單調(diào)增函數(shù)。

值得注意的是，雙曲正切函數(shù)在神經(jīng)網(wǎng)絡(luò)中經(jīng)常被當作激活函數(shù)使用。此時問題(3)變成了：

(13)

易知E(x,M1)≥0是凸函數(shù)，則：

▽E(x,M1)=f(x)▽f(x)+(Ax-b)TA

那么對于凸優(yōu)化問題：minE(x,M1)

根據(jù)梯度下降法，建立神經(jīng)動力學(xué)方程：

(14)

圖2 目標函數(shù)(n=1時)

圖3 激活函數(shù)y′=tanh(x)

2 穩(wěn)定性與收斂性分析

為了探討RNN的穩(wěn)定性與收斂性能，下面給出兩個定理并證明：

證畢。

3 停時條件

重構(gòu)稀疏信號x的主要思想是通過建立反饋神經(jīng)網(wǎng)絡(luò)模型，再由龍格-庫塔方法，利用Matlab平臺逐步迭代尋找問題(3)的最優(yōu)解和最優(yōu)值，直到滿足停時條件。下面給出RNN算法的具體步驟。

步驟1 初始化。設(shè)t=0，取初始點x(t0)=x0∈Rn，給定步長Δ>0和ε∈[10-15,10-5]，k:=1,M1≤f(x*)。

步驟2 計算梯度：u(t)=(f(x)-Mk)▽f(x)+(Ax-b)TA。

步驟3 狀態(tài)更新：x(t+Δt)=x(t)-Δt·u(t)。

4 仿真實驗

1)產(chǎn)生k稀疏信號x∈Rn,k個非零元素的位置是隨機產(chǎn)生的，滿足[1,n]的均勻隨機分布。相應(yīng)的非零元素的大小也是隨機產(chǎn)生的。

3)計算觀測向量：b=Ax，其中b∈Rm。

由文獻[2]知，當矩陣A滿足RIP條件時，精確恢復(fù)信號x所需的觀測量的數(shù)量m滿足：m≥Cklog(n/k)即可，其中C是常數(shù)，即m只與問題的規(guī)模參數(shù)組合(n,k)有關(guān)。取實驗參數(shù)為：測量矩陣大小m=64，n=256，原始信號稀疏度k=10。根據(jù)上述數(shù)據(jù)的生成方法，可以產(chǎn)生如圖4和圖5所示的原始稀疏信號和觀測向量。

圖4 原始稀疏信號

2)產(chǎn)生觀測矩陣A∈Rm×n，矩陣的所有元素是隨機生成的并且服從高斯分布N(0,1)，rank(A)=m。

圖5 觀測向量b

由圖6可知，在b與A給定的情況下，x在神經(jīng)網(wǎng)絡(luò)(14)的不斷反饋之下，最終重構(gòu)并且非零元素均收斂到既定位置上的元素。為了檢驗不同稀疏度下和觀測次數(shù)m與正確重構(gòu)概率的關(guān)系，不妨取稀疏度k=[4,12,20,28,36]。

每一組(k,m,n)，執(zhí)行200次隨機實驗，由圖7可知，對于不同稀疏度k，當觀測點數(shù)m大于等于110時，RNN方法能正確恢復(fù)稀疏信號的概率極高。 而由圖8可知，對于不同觀測點數(shù)的m，當稀疏度k小于等于20時，RNN方法能正確恢復(fù)稀疏信號的概率極高。

圖的狀態(tài)變化曲線

圖7 測量數(shù)m與成功恢復(fù)的概率關(guān)系(n=256)

圖8 稀疏度k與成功恢復(fù)的概率關(guān)系(n=256)

由表1知，模型(8)只需要較少的觀測次數(shù)就可以正確地恢復(fù)稀疏信號，也可以看出，當m大于100時，其他算法也獲得較低的恢復(fù)誤差，說明當觀察次數(shù)m足夠大時，通常適用的算法同樣也能獲得較精確的恢復(fù)效果。

表1 幾種算法在不同觀測次數(shù)下的相對誤差

5 結(jié)語

本文基于目標函數(shù)的性質(zhì)，設(shè)計快速重構(gòu)稀疏信號的反饋神經(jīng)網(wǎng)絡(luò)算法，通過討論能量函數(shù)的梯度，證明該RNN模型最優(yōu)解的存在性與原問題的近似等價性，討論了網(wǎng)絡(luò)的穩(wěn)定性，并且通過實驗驗證了算法的有效性；但是該算法也有不足之處，反復(fù)實驗之下，發(fā)現(xiàn)最佳的迭代次數(shù)會導(dǎo)致運算量增加，從而稀疏信號重構(gòu)時間加長，因而該網(wǎng)絡(luò)需要進一步改進。

References)

[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 viaq-minimization for 0

[5] BLUMENSATH T, DAVIES M E. Gradient pursuits [J]. IEEE Transactions on Signal Processing, 2008, 56(6): 2370-2382.

[6] DAI W, MILENKOVIC O. Subspace pursuit for compressive sensing signal reconstruction [J]. IEEE Transactions on Information Theory, 2009, 55(5): 2230-2249.

[7] MALLAT S G, ZHANG Z F. Matching pursuits with time-frequency dictionaries [J]. IEEE Transactions on Signal Processing, 1993, 41(12): 3397-3415.

[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.

[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.

[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] 李珅,馬彩文,李艷,等.壓縮感知重構(gòu)算法綜述[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.

[13] 李國成,宋士吉,吳澄.解決非可微凸優(yōu)化問題的次梯度反饋神經(jīng)網(wǎng)絡(luò)[J].中國科學(xué)(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] 曾喆昭.神經(jīng)網(wǎng)絡(luò)優(yōu)化方法及其在信息處理中的應(yīng)用研究 [D].長沙：湖南大學(xué),2008:62-73.(ZENG Z Z. Neural network optimization method and its application in information processing [D]. Changsha: Hunan University, 2008: 62-73.)

[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.

[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.

[17] LEUNG C S, SUM J, CONSTANTINIDES A G. Recurrent networks for compressive sampling [J]. Neurocomputing, 2014, 129: 298-305.

[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.

Sparsesignalreconstructionoptimizationalgorithmbasedonrecurrentneuralnetwork

WANG Xingxing*，LI Guocheng

(CollegeofScience,BeijingInformationScienceandTechnologyUniversity,Beijing100192,China)

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 thel0-norm is a non-convex and non-differentiable function, and the optimization problem is NP-hard, under the premise that the measurement matrixAmet 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 numberm, 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.

l0optimization; Recurrent Neural Network (RNN); Restricted Isometry Property (RIP); energy function

2017- 03- 23;

2017- 05- 31。

國家自然科學(xué)基金資助項目(61473325)。

汪星星(1991—)，女，湖北黃岡人，碩士研究生，主要研究方向：神經(jīng)網(wǎng)絡(luò)優(yōu)化計算； 李國成(1964—)，男，河北承德人，教授，博士，主要研究方向：神經(jīng)網(wǎng)絡(luò)優(yōu)化計算。

1001- 9081(2017)09- 2590- 05

10.11772/j.issn.1001- 9081.2017.09.2590

TP18

A

This work is partially supported by the National Natural Science Foundation of China (61473325).

WANGXingxing, born in 1991, M. S. candidate. Her research interest include neural network optimization calculation.

LIGuocheng, born in 1964, Ph.D., professor. His research interests include neural network optimization calculation.