汪星星，李國(guó)成

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

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

汪星星*，李國(guó)成

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

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

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

0 引言

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

(1)

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

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

(2)

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

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

圖1 壓縮感知理論框架

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

(3)

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

其中x為k階稀疏信號(hào)。

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

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

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

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

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

(4)

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

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

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

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

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

(5)

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

(6)

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

(7)

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

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 稀疏信號(hào)的恢復(fù)

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

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

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

(13)

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

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

那么對(duì)于凸優(yōu)化問(wèn)題：minE(x,M1)

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

(14)

圖2 目標(biāo)函數(shù)(n=1時(shí))

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

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

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

證畢。

3 停時(shí)條件

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

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

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

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

4 仿真實(shí)驗(yàn)

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

3)計(jì)算觀測(cè)向量：b=Ax，其中b∈Rm。

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

圖4 原始稀疏信號(hào)

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

圖5 觀測(cè)向量b

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

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

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

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

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

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

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

5 結(jié)語(yǔ)

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

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] 李國(guó)成,宋士吉,吳澄.解決非可微凸優(yōu)化問(wèn)題的次梯度反饋神經(jīng)網(wǎng)絡(luò)[J].中國(guó)科學(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].長(zhǎng)沙：湖南大學(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。

國(guó)家自然科學(xué)基金資助項(xiàng)目(61473325)。

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

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.