内投影神经网络对l₁-αl₂极小化问题的稀疏信号恢复

An Inertial Projection Neural Network for Sparse Signal Recovery via l₁-αl₂Minimization

摘要: 本文旨在开发一种新算法，从少量测量数据中恢复稀疏信号，这是压缩传感领域的一个基本问题。目前，压缩感知倾向于非相干系统，其中任何两个测量值的相关性都尽可能小。然而，在现实中，许多问题是相干的，传统的方法，如l₁最小化，处理效果不佳。我们提出了一种新的基于惯性投影神经网络的压缩传感l₁-αl₂极小化问题。针对高相干测量矩阵的稀疏信号恢复，提出了l₁极小化问题，不同于传统的使用标准凸松弛的l₁-αl₂极小化问题。本文详细介绍了如何将惯性投影神经网络应用到压缩传感技术中。此外，还进行了数值实验，证明了稀疏信号恢复算法的有效性和显著的性能。

Abstract: This paper aims to develop a new algorithm for recovering a sparse vector from a small number of measurements, which is a fundamental problem in the field of compressive sensing (CS). Currently, CS favors incoherent systems, in which any two measurements are as little correlated as possible. In reality, however, many problems are coherent, conventional methods such as l₁ minimization, do not work well. We propose a l₁-αl₂ minimization problem for compressed sensing using inertial projection neural network. The l₁-αl₂ minimization problem is presented for sparse signal recovery from highly coherent measurement matrices, differing from conventional l₁ mini-mization which uses standard convex relaxation. We describe in details how to incorporate inertial projection neural network into compressed sensing. Furthermore, numerical experiments are conducted to support the effectiveness and remarkable performance of the algorithm for sparse signal recovery.

1. 引言

随着大型数据集越来越可用和重要，科学技术的最新发展已经引起了数据处理的革命。为了满足“大数据”时代的需要，压缩传感(CS) [1] 领域正在迅速发展。CS的过程包括编码和解码。编码过程涉及一组(线性)测量值 $b=Ax$ ，其中A是一个大小为 $m\times n$ 的矩阵。如果 $m<n$ ，我们称为 $x\in R^n$ 能被压缩。译码的过程是从b中恢复x，另外假设x是稀疏的。它可以表示为一个优化问题，

${\min }_x{\Vert x\Vert }_0\text{s}\text{.t}\text{.}b=Ax$ (1.1)

其中 ${\Vert \cdot \Vert }_0$ 表示 $l_0$ 范数。因为 $l_0$ 等于非零元素的数目，将 $l_0$ 范数最小化，等于求出最稀疏的解。在CS中最大的障碍之一是解决解码问题式(1.1)，因为 $$ 范数极小化问题的求解在数学上是一个NP [2] 难问题，即在多项式时间内无法有效求解。为了克服上述困难，一种流行的方法是用凸形代替，即 $l_0$ 范数极小化

${\min }_x{\Vert x\Vert }_1\text{s}\text{.t}\text{.}b=Ax$ (1.2)

其中 ${\Vert x\Vert }_1={\displaystyle {\sum }_{i=1}^n\left|x_i\right|}$ 。(1.2)是一个凸优化问题，同时，它可以通过梯度投影法 [3] ，同源性方法 [4] 等来求解。最近，将非凸度量作为 $l_1$ 的替代方法的应用不断增加。特别是 [5] [6] 中 $p\in \left(0,1\right)$ 的非凸度量p可以看作是近似 $l_0$ 随着 $p\to 0$ 的连续策略。优化策略包括迭代重加权 [7] 和半阈值 [6] 。其他非凸 $l_1$ 变形包括 $l_{1-2}$ [8] ，

${\min }_x{\Vert x\Vert }_1-{\Vert x\Vert }_2\text{s}\text{.t}\text{.}b=Ax$ (1.3)

结果表明，当测量矩阵A高度相干时， $l_{1-2}$ 极小化一致优于经典的 $l_1$ 和 $l_q$ 极小化，在 [8] 中理论上，给出了一个RIP类型的充分条件，以确保 $l_{1-2}$ 能精确地恢复稀疏信号。

众所周知，神经网络在优化问题和许多应用中得到了广泛的应用。但是，可能会遇到高相干性的测量矩阵，开发出更好、高效的优化方法是有必要的。本文通过推广 $l_{1-2}$ 形式，考虑 $l_1-\alpha l_2\left(0<\alpha \le 1\right)$ 度量，

${\min }_x{\Vert x\Vert }_1-\alpha {\Vert x\Vert }_2\text{s}\text{.t}\text{.}b=Ax$ (1.4)

显然，这是一个非凸优化问题。应用变量替换以及投影算子 [9] 的知识，我们提出了一种新的无约束 $l_1-\alpha l_2$ 极小化问题的神经网络模型。用这种方法不仅能真正解决问题同时也避免了次梯度项的困难。

2. 问题介绍

通过拉格朗日乘子，我们将问题转换为无约束优化问题

${\min }_{u,v\in R^n}\frac{1}{2}{\Vert Ax-b\Vert }_2^2+\tau \left({\Vert x\Vert }_1-\alpha {\Vert x\Vert }_2\right)$ (2.1)

毫无疑问是不可微的，我们首先将目标函数进行转换，而不是直接寻找将非凸目标函数极小化的方法。假设在问题中，用 $x=u-v$ 来代替未知变量x，其中 $u,v\in R^n$ 分别为x中所有的正的和负的元素，也就是说 $u_i={\left(x\text{\_}i\right)}_{+}$ ， $u_i={\left(-x\text{\_}i\right)}_{+}$ ， ${\left(x\text{\_}i\right)}_{+}=\max \left\{x_i,0\right\}$ ， $i=1,\cdots ,n$ 。有了这样的替换，很容易有

${\Vert x\Vert }_1=I_n^{\text{T}}\left(u+v\right)=I_n^{\text{T}}u+I_n^{\text{T}}v$

${\Vert x\Vert }_2=\Vert u-v\Vert$

$Ax=A\left(u-v\right)$

其中 $I_n^{\text{T}}={\left(1,\cdots ,1\right)}^{\text{T}}$ 。因此，问题可以改写为

${\min }_{u,v\in R^n}\frac{1}{2}{\Vert A\left(u-v\right)-b\Vert }_2^2-\tau {\Vert u-v\Vert }_2+\tau I_n^{\text{T}}u+I_n^{\text{T}}v$

Subject to $u\ge 0,v\ge 0$ (2.2)

这里 $\tau >0$ 是一个正则化参数。这个问题相当于下面的非凸问题

$\min f\left(z\right)=\frac{1}{2}{z}^{\text{T}}Bz-\tau {\left(z^{\text{T}}z\right)}^{\frac{1}{2}}+c^{\text{T}}$

Subject to $z\in S=\left\{z\in R^n|z\ge 0\right\}$ (2.3)

其中目标函数 $f\left(z\right)$ 是一个非凸连续微分，并且

$z=(uv)$

$B=\left(\begin{array}{c}{A}^{\text{T}}A-A^{\text{T}}A\\ -A^{\text{T}}A{A}^{\text{T}}A\end{array}\right)$

$c=\tau I_{2n}+\left(\begin{array}{c}-A^{\text{T}}b\\ A^{\text{T}}b\end{array}\right)$

3. 神经网络模型

本节介绍了求解CS中 $l_1-\alpha l_2$ 极小化问题的IPNN方法。基于比例梯度投影，建立了求解非凸问题的神经网络模型。令 $z^{*}\in S$ 作为一个最优解，因为 $f\left(z\right)$ 二次可微，则对所有的 $t\in \left[0,1\right]$ 和 $z\in S$ ，有 $z^{*}+t\left(z-z^{*}\right)\in S$ 。因此函数 $q\left(t\right)=f\left(z^{*}+t\left(z-z^{*}\right)\right)$ 在 $\left(0,1\right)$ 上可微，因为 $q\left(t\right)$ 在 $t=0$ 处达到最小值，因此 $q^{\prime }\left(t\right)\ge 0$ 。则有

$q^{\prime }\left(0\right)=\nabla f{\left(z\right)}^{\text{T}}\left(z-z^{*}\right)\ge 0,\forall z\in S$ (3.1)

找到一个最优值是相当于求解变分不等式，它可以被视为一个在科学和工程领域的一个自然的平衡问题.因此我们的下一个任务是寻求一个适当的方法。由于，我们有以下的惯性投影神经网络IPNN模型

$\{\begin{array}{l}\stackrel{\dot{}}{z}=w\\ \stackrel{\dot{}}{w}=-\lambda w+{\left[z-Bz+\tau \frac{z}{\Vert z\Vert }-c\right]}^{+}-z\\ z\left(t_0\right)=z_0\in S\end{array}$ (3.2)

其中 $S=\left\{z\in R^n|z\ge 0\right\}$ ， ${(\cdot )}^{+}$ 是投影算子：

${\left(z_i\right)}^{+}=\{\begin{array}{l}{z}_i,z_i\ge 0.\\ 0,z_i<0.\end{array}$

该模型属于一个存在于神经动力学优化模型中的双层结构，克服了一些缺点并且由于内点项 $\stackrel{\dot{}}{w}$ 的存在加速了收敛过程。

4. 算法

在这个部分中，优化算法的原则总结在算法1中。该算法基于IPNN模型，提出了重构稀疏信号求解无约束 $l_1-\alpha l_2$ 最小化问题的迭代步骤。由于问题的非凸性，该算法一般不能保证收敛到全局最小，因此一个好的初始化对该算法的性能是至关重要的。一个很好的启发是利用求解无约束的 $l_1$ 最小化问题的解来作为这个算法的初始值。我们使用 $x_0={\left(A^{\text{T}}A\right)}^{-1}{A}^{\text{T}}b$ 来将算法初始化，其中 ${\left(A^{\text{T}}A\right)}^{-1}{A}^{\text{T}}b$ 是A的伪逆，则很容易计算 $z_0$ 通过 $x_0$ 。

5. 数值仿真

在本节进行数值实验来证明我们提出的算法IPNN $l_1-\alpha l_2$ 的有效性和信号重构能力。所有的实验均在MATLAB上实现，采用的常微分方程求解器是ode15s。从 [8] 中测试了稀疏向量的精确重构在矩阵A较弱的条件下，可以保证问题的最小值的稀疏度。为了验证在A是一个高相干矩阵的情况下的稀疏向量精确重构，我们通过创建一个随机采样部分DCT矩阵 $A^{m\times n}$ 来产生传感矩阵，其中矩阵 $A_i=\left(\cos \left(2i-1\right)\text{π}\zeta /F\right)/\sqrt{m}$ 。矩阵A的相干性随着正整数F的增加而增加。 $\zeta \in R^n$ 的元素在[0,1]上独立同分布。接下来，我们将研究F与相干性之间的关系，其中相干性定义为 $\mu \left(A\right)={\max }_{i\ne j}\frac{\left|A_i^{\text{T}}{A}_j\right|}{{\Vert A_i\Vert }_2{\Vert A_j\Vert }_2}$ 。

例1：考虑无约束 $l_1-\alpha l_2$ 极小化问题

${\min }_{u,v\in R^n}\frac{1}{2}{\Vert Ax-b\Vert }_2^2+\tau \left({\Vert x\Vert }_1-\alpha {\Vert x\Vert }_2\right)$ (5.1)

首先给出了无噪声情况下问题的稀疏信号重构。测试长度为n的稀疏信号 $\bar{x}$ 由标准正态分布生成。由A和 $\bar{x}$ ，可由 $b=A\bar{x}$ 计算得到b。令 $m=64$ ， $n=256$ ， $F=14$ ， $\tau ={10}^{-2}$ 。IPNN $l_1-\alpha l_2$ 算法的效果可以从图中看出。

Figure 1. Coherence

图1. 相干性

图1绘制了产生的矩阵 $A^{m\times n}$ 的相干性结果。很容易看出， $\mu \left(A\right)$ 随着F增加趋向于变大，即A的相干性随着F增大而增大。为了方便起见，在不引起混淆的情况下，我们将使用F来表示相干性。因此，在随后的实验中，我们设置F = 14足以保证高相干性测量矩阵。

Figure 2. ${\Vert x\Vert }_1-\alpha {\Vert x\Vert }_2$ contour line plot

图2. ${\Vert x\Vert }_1-\alpha {\Vert x\Vert }_2$ 等值线图

图2展示了当 $\alpha$ 取不同值时的 ${\Vert x\Vert }_1-\alpha {\Vert x\Vert }_2$ 等值线图。

Figure 3. Solutions

图3. 解

图3展示了神经网络的解渐近稳定且收敛于局部最优解 $x^{*}$ 。

Figure 4. The original signal and reconstructed signal via IPNN $l_1-\alpha l_2$ , $\alpha =0.6$

图4. IPNN $l_1-\alpha l_2$ ( $\alpha =0.6$ )算法下得原始信号与重构信号

从图4可以直观观察重构结果，显示原始信号和重构信号基本上重合。因此，在无噪声情况下，我们提出的算法IPNN $l_1-\alpha l_2$ 可以有效重构稀疏信号。

图5展示了50个实验值的平均相对误差， $l_1-\alpha l_2$ ( $\alpha =0.6$ )与 $l_1-l_2$ 相比，收敛速度更快，且相对误差更小。

例2：在这一部分中，我们考虑了噪声情况下问题(5.1)的鲁棒恢复。我们将白高斯噪声加到干净的数据 $A\bar{x}$ 中，然后得到测量值 $b=awgn\left(Ax;snr\right)$ ，其中snr对应于以dB测量的信噪比(snr)值。我们

Figure 5. Relative error

图5. 相对误差

设置初始值 $x_0={\left(A^{\text{T}}A\right)}^{-1}{A}^{\text{T}}b$ 。重构信号 $x^{*}$ 通过算法IPNN $l_1-\alpha l_2$ 获得，我们计算重构的信噪比通过 $10{\log }_{10}{\Vert \bar{x}\Vert }_2^2/{\Vert x^{*}-\bar{x}\Vert }_2^2$ 。

IPNN是一种通过 $l_{1-2}$ [10] 极小化实现稀疏信号恢复的惯性投影神经网络算法。DCA- $l_{1-2}$ [8] 是求解 $l_{1-2}$ 极小化问题的典型优化方法。通过嵌入 $l_p$ ( $p\ge 0$ )范数噪声约束在最近出现的 $l_{1-2}$ 方法中，采用了IR $l_1-l_2/l_p$ [11] 方法从高相干测量矩阵中恢复一般噪声信号。在下面的实验中，我们设定 $p=2$ 。优化算法比如ADMM-lasso [12] 是解决稀疏问题的重要和流行的经典算法。通过噪声的改变，我们在随机过采样部分DCT矩阵和常用随机高斯矩阵上比较了IPNN $l_1-\alpha l_2$ ( $\alpha =0.6$ )，IPNN，IR $l_1-l_2/l_2$ ，DCA- $l_{1-2}$ ，ADMM-lasso。对于随机过采样的部分DCT矩阵，我们设 $m=100$ ， $n=2000$ 。对于高斯矩阵，我们假设 $m=256$ ， $n=1024$ 。每个记录值是50次随机实现的平均值。

Table 1. Randomly over-sampled partial DCT matrix

表1. 随机过采样部分DCT矩阵

表1显示了使用过采样DCT矩阵得到的结果。相比之下，在中等噪声下，我们的IPNN $l_1-\alpha l_2$ 表现更佳。

Table 2. Random Gaussian matrix

表2. 随机高斯矩阵

表2显示了高斯测量下的结果。我们的IPNN $l_1-\alpha l_2$ 也明显优于其他算法。

6. 结论

本文介绍了用IPNN $l_1-\alpha l_2$ 方法通过 $l_1-\alpha l_2$ 极小化来实现稀疏信号的恢复。为了验证我们方法的有效性和鲁棒性，进行几组对比实验包括噪声和无噪声，以及高斯随机矩阵和高相干矩阵。结果表明，该方法在信号恢复方面优于其它最先进的方法。稀疏信号重构问题其应用广泛而成为一个热点问题，针对稀疏信号重构等相关问题，需要寻找更加实用有效的方法来解决这些非凸问题，结合神经网络，压缩感知将会迎来美好的明天。

基金项目

中央高校基本科研业务费资助项目(No. XDJK2018C076)。