基于反饋神經網絡的稀疏信號恢復的優化算法

汪星星，李國成

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

基于反饋神經網絡的稀疏信號恢復的優化算法

汪星星*，李國成

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

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

l0最優化；反饋神經網絡；有限等距性；能量函數

0 引言

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

(1)

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

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

(2)

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

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

圖1 壓縮感知理論框架

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

(3)

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

其中x為k階稀疏信號。

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

1 反饋神經網絡算法

1.1 反饋神經網絡

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

不論是l0范數最小化還是l1范數最小化問題都可以歸結為帶約束的優化問題。其中一類通過設計一系列反饋神經網絡求解帶約束的優化問題的方法統稱為神經動力學優化方法。以下是一個非線性等式約束優化問題：

(4)

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

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

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

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

考慮凸優化問題：

(5)

根據梯度下降法，可以建立求解問題(5)的神經網絡：

(6)

類似地，再次作能量函數：

(7)

得到相應問題(7)的子凸優化問題：

minE(x,M2)

(8)

(9)

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

minE(x,Mk)

(10)

minE(x,Mk+1)

(11)

相應的神經子網絡模型：

(12)

1.2 稀疏信號的恢復

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

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

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

(13)

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

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

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

根據梯度下降法，建立神經動力學方程：

(14)

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

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

2 穩定性與收斂性分析

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

證畢。

3 停時條件

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

步驟1 初始化。設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 狀態更新：x(t+Δt)=x(t)-Δt·u(t)。

4 仿真實驗

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

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

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

圖4 原始稀疏信號

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

圖5 觀測向量b

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

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

圖的狀態變化曲線

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

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

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

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

5 結語

本文基于目標函數的性質，設計快速重構稀疏信號的反饋神經網絡算法，通過討論能量函數的梯度，證明該RNN模型最優解的存在性與原問題的近似等價性，討論了網絡的穩定性，并且通過實驗驗證了算法的有效性；但是該算法也有不足之處，反復實驗之下，發現最佳的迭代次數會導致運算量增加，從而稀疏信號重構時間加長，因而該網絡需要進一步改進。

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] 李珅,馬彩文,李艷,等.壓縮感知重構算法綜述[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] 李國成,宋士吉,吳澄.解決非可微凸優化問題的次梯度反饋神經網絡[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.)

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

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

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

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.