一類復值l1范數最小化問題的復值投影神經網絡算法

張宋傳，陸求賜

（1.武夷學院 數學與計算機學院，福建 武夷山 354300；2.武夷學院 人文與教師教育學院，福建 武夷山 354300）

考慮一類復值l1范數最小化問題：

其中，A∈Cm×n（m=n）,b∈Cm，‖·‖1表示l1范數，使用l1范數最小化旨在提升欠定的線性系統Az=b解的稀疏性。該問題在工程領域較為普遍，以壓縮感知領域為例，問題（1）是其一類主要問題[1-2]，優化變量z表示未知的稀疏復值信號或圖像，或者是原信號在一定稀疏基下的稀疏向量，A=ΦΨ是感知矩陣，其中Φ表示觀測矩陣，Ψ表示稀疏基矩陣，b是觀測向量，在滿足一定條件下，可以通過解問題(1)獲得原信號的準確估計值。

當問題（1）退化為實值時，該問題等價于一個線性規劃問題，通過凸優化方法可獲得精確解。此外，一些快速有效的算法也相繼提出，例如神經動力學算法[1]、迫近方法[3]以及Bregman方法[4]等。這其中，只有一小部分算法可以直接用于問題（1），即復值情形的求解，如正交匹配追蹤算法(OMP)[5]，譜投影梯度算法SPGL1[6]，還有一些算法需要采用一些實數化策略，例如，將問題（1）中復數拆分為實部和虛部，將原問題轉化為實值問題[7]求解。

遞歸神經網絡算法是一種新型的優化算法，以其內在動力學和并行計算的特征，在過去數十年，被廣泛的研究，旨在解決科學及工程領域領域中的出現的大規模實時優化問題[8-9]。文獻[1]基于投影算子和投影矩陣，提出了一單層的連續時間投影神經網絡算法求解問題（1）的實值情形，并在理論上證明了該網絡的穩定性和全局收斂性，基于前向歐拉離散化方法，進一步給出了數值模擬時該網絡的離散化算法PNNSR，PNNSR算法不僅保持了連續時間算法的穩定性和全局收斂性，還具有大步長的特性。

但PNNSR算法不能直接用于問題（1）的求解。本文通過定義新的投影函數，提出了一種連續時間的復值投影神經網絡模型及其離散化算法（CPNNSR），并在理論上給出了新模型及其離散化算法的穩定性和全局收斂性。新模型及其離散化算法能完全在復域上求解問題（1），同時保留了原有實值算法模型復雜度低，收斂速度快的優點。數值實驗進一步表明新模型的離散化算法能有效地求解基于范數最小化的復值稀疏信號的重構問題。

本文中，用Cm×n與Rm×n分別表示m×n復矩陣集與實矩陣集，分別表示矩陣或向量的轉置，共軛及共軛轉置，Re(·)Im(·)分別表示復值對象的實部和虛部。我們始終假設可行集｛z∈Cn：A z=b｝非空，且A是行滿秩的，則AAH可逆。

1 預備知識

微分是研究復值優化問題的重要理論工具之一[10]，微分也稱Wirtinger微分[11]，或者Brandwood的微分[12]，習慣上，我們把傳統的復變函數微分理論稱為C-微分，二者統稱CR微分[10]。

定義1.1[10]設函數g(z)：Cn→C，g(z)關于z與z的R導數與導數分別定義為：

定義1.2[10]設函數g(z)：D?Cn→C，設u是D的一個內點，如果存在u的一個球鄰域B(u)，B(u)中任一點的R導數與導數都存在，并且R導數與導數在u上連續，則稱函數g(z)在u上是R可微的；如果D是Cn中的開子集，函數g(z)在D上任一點上都R可微，則稱g(z)在D上是R可微的。

定義1.3[10]設g(z)：D?Cn→R是R可微的，g(z)的復梯度定義為：。

定義1.4[13]對于任何凸函數g(z)：Cn→R，函數g關于z的次微分定義為：

其中，p稱為g在z上的次梯度，記?▽g(z)，g在z處的次梯度集即g在z處的次微分。當g可微時，p的唯一可能選擇是▽g(z)，次梯度即為梯度。

2 新模型及其離散化算法CPNNSR

本文提出的求解問題（1）的復值連續時間投影神經網絡模型的動力學方程描述如下：

其中，z∈Cn是狀態向量，u∈Cn是輸出向量，投影矩陣P=AH(AAH)-1A，易知P2=P,q=AH(AAH)-1b,I是n階單位陣，參數ε＞0，投影函數φ（z）：Cn→Ω?Cn定義如下：

通過前向歐拉離散化方法，得到上述連續時間復值投影神經網絡模型的離散化算法：

其中，λk是步長，實際應用中，步長λk恒置為1。算法(4)進一步優化為：

本文提出的連續時間的復值投影神經網絡模型及其離散化算法（CPNNSR）在結構上類似于文獻[1]的實值網絡模型及其離散化算法，最大不同在于投影函數的定義。提出復值網絡模型及其離散化算法，通過引入新的投影函數，能完全在復域上求解問題（1），同時又保留了原有實值算法模型復雜度低，收斂速度快的優點。關于新模型及離散化算法的穩定性和收斂性結果將在下一節中給出。

3 主要結果

由于問題(1)的目標函數是可分離的，有：

定理3.1u*∈Cn是l1范數最小化問題(1)的最優解，當且僅當系統(2)存在一個的平衡點z*∈Cn時，使得u*=z*-g（z*）。

證明：眾所周知，u*∈Cn是問題(1)的最優解當且僅當存在γ*∈?（‖u*‖1）和ω∈Cm，使得

由引理3.2,γ*＝φ（γ*+u*），令z*=γ*+u*,則γ*=φ（z*），u*＝z*-φ（z*）。

(5)式兩邊同時乘以（AAH）-1A，得：

將(7)式代入(5)式，即得：

(6)式兩邊同時乘以（AAH）-1,有Pu*=q,即：P（z*-φ（z*））＝q。結合(8)式，可得

故z*是系統(2)的平衡點。

另一方面，如果z*是系統(2)的一個平衡點，u*＝z*-φ（z*），則有：

成立。上式兩邊同乘投影矩陣P，由投影矩陣性質，有P2=P，Pq=q,得：

（I-P）φ（z*）=0，

進而

（9）式兩邊同時左乘A，有Au*=b。?u∈｛z∈Cn：Az=b｝，由(10)式，我們有

因為Pu=Pu*=q，進而有

設γ*=φ（z*），因為u*＝z*-φ（z*），有γ*=φ（γ*+u*）,故γ*∈?（‖u*‖1）。由定義1.4，‖u‖1-‖u*‖1≥Re（（u-u*）Hγ*），由(11)式得，‖u‖1≥‖u*‖1，即u*是問題（1）的最優解，證畢。

最后，給出連續時間復值投影神經網絡模型（2）及其離散化算法（4）的穩定性與收斂性結果，其證明與文獻[1]類似，出于篇幅考慮，此處略。

定理3.2對任一初始值z0∈Cn，連續時間復值投影神經網絡模型（2）中的輸出向量u（t）是李雅普諾夫意義下穩定的，并且全局收斂到問題（1）的最優解。

定理3.3對任一初始值z0∈Cn，當0＜λk＜2時，算法（4）中的輸出向量序列{uk}是李雅普諾夫意義下穩定的，并且全局收斂到問題（1）的最優解。

4 數值實驗

為了證實算法的性能，本節將運用CPNNSR算法求解基于l1范數最小化的復值稀疏信號的重構問題。實驗是在3.40 GHz處理器與8 GB隨機存取存儲器，Windows 10操作系統下的Matlab R2013b軟件上運行的。

圖1 各分量的模Fig.1 Modulus of each components

圖2 收斂過程Fig.2 Convergence process