1-2范数中的稀疏重构*1-2范数中的稀疏重构*摘要： 压缩感知(compressed sensing，CS)是一种全新的信号采样技术， 对于稀疏信号，它能够以远小于传统的Nyquist采样定理的采样点来重构信号．在压缩感知中， 采用动态连续系统，对
1-2范数的稀疏信号重构问题进行了研究．提出了一种基于固定时间梯度流的稀疏信号重构算法，证明了该算法在Lyapunov意义上的稳定性并且收敛于问题的最优解．最后通过与现有的投影神经网络算法的对比，体现了该算法的可行性以及在收敛速度上的优势．
关 键 词： 压缩感知； 1-2范数； 固定时间梯度流； 稀疏信号重构
压缩感知也称为压缩采样或稀疏采样，由Candès和Donoho于2006年正式提出[1-2]．此后压缩感知理论得到了飞速的发展，在信号处理[3]、压缩感知[2]、机器学习[4]等方面得到了广泛的应用．压缩感知理论由信号的稀疏表示、设计观测矩阵、设计信号重构算法三部分构成．稀疏信号或可压缩信号通过一个与变换基不相关的观测矩阵将高维信号投影到一个低维空间上，获得一个低维信号，此信号包含恢复信号所需要的重要信息，然后通过求解优化问题从低维的信号中将原信号高概率重构出来．在稀疏信号重构中，从欠定线性系统Ax=b中重构稀疏信号x,即求解方程组Ax=b的最稀疏解，可以通过求解x的0范数的最小化问题获得：
(1)
其中A是观测矩阵，A∈Rm×n(m≪n)，测量向量b∈Rm，‖x‖0表示向量x中非0元素的个数．考虑到问题(1)是一个NP-hard[5]问题，在满足一些条件下，可以用
1范数最小化代替0范数，即求解1范数最小化问题：
(2)
在文献[6]中，为了重构稀疏信号，使得问题(1)与问题(2)等价，则观测矩阵A需满足限制等距性质(restricted isometry property, RIP)，观测矩阵A的RIP参数δs满足下式的最小值：
其中x为稀疏信号，‖x‖2是x的Euclid范数(Euclidean norm)，s为稀疏度，0≤s≤n并且为正整数，δs∈(0,1)，观测矩阵A满足s阶RIP．通过对问题(2)的求解，稀疏信号x可以从低维的线性测量值中恢复出来．在问题(2)中如果b受到噪声的干扰如Gauss噪声，可以放宽问题(2)的限制条件，得到下面的问题:
(3)
其中e≥0．问题(3)是一个二次约束线性规划(quadratically constrained linear program ，QCLP)问题．对于任意的e≥0，求解问题(3)可以近似转化为求解如下问题[7]：
(4)
其中α>0，即求解1-2范数[8]最小化问题．1-2范数的稀疏信号重构在人脸识别[9-10]、图像修复[11]、去噪[12]、块稀疏模型[13]中有着广泛的应用．近些年来， 为了求解问题(4)，很多算法被提出，如基追踪去噪算法[14]、内点算法[15]、梯度投影稀疏重构方法(gradient projection for sparse reconstruction，GPSR)[7]等．然而，这些算法的求解效率很大程度上取决于数据的维度，通常需要大量的迭代，一般数字计算机的数值迭代算法效率较低，当遇到拥有大量数据应用程序时会导致很高的计算量和存储需求．人工神经网络[16]自提出以来，由于其大规模并行分布式计算和收敛速度快等优点，被广泛应用于求解优化问题上．其中，递归神经网络(recurrent neural network，RNN)被大量用于求解信号处理和稀疏逼近等问题[17]．文献[18]提出了一种基于连续时间投影神经网络(projection neural network，PNN)的稀疏信号重构算法．文献[19]提出了一种基于比例梯度投影的神经网络的稀疏信号重构算法．以上的这些稀疏信号重构算法仍有进一步提高收敛速度的空间．
本文在文献[20]的启发下引入了动态连续系统，提出了一种基于固定时间梯度流的稀疏信号重构算法，用于求解1-2范数最小化问题，证明了该算法的稳定性，最后与投影神经网络算法相比，能够更快地收敛于最优值．
问题(4)是一个不可微的凸问题，在文献[21]中，通过将变量x分为正数部分和负数部分来求解，问题(4)能够转化为凸二次规划问题，下面的向量u与-v分别替代正数部分和负数部分：
x=u-v， u>0， v>0，
其中ui=(xi)+，vi=(-xi)+，i=1,2,3,…,n，这里的(·)+表示(xi)+=max{xi,0}．因此
其中1n=(1,…,1)T为n维全1的向量，问题(4)可以等价为
(5)
进一步地，问题(5)可以重写为
(6)
其中
考虑到下面的动态系统：
(7)
其中x∈Rn， f: R×Rn→Rn是一个非线性系统，假设(7)的平衡点为零点．
定义1[22-24] 如果系统(7)全局渐进稳定，且系统的任意解z(t,z0)在某一有限时间达到平衡点，则称系统(7)的平衡点z=0是全局有限时间稳定的，即z(t,z0)=0，∀t≥T(z0)，这里的T:Rn→R+∪{0}为稳定时间函数．
定义2[22] 如果系统(7)是全局有限时间稳定，稳定时间函数T(z0)是有界的，Tmax >0，即对于∀z0∈Rn有T(z0)≤Tmax ，那么系统(7)的平衡点z=0是全局固定时间稳定．
引理1[25] 如果存在一个连续的径向无界函数V: Rn→R+∪{0}， 则有V(z)=0 ⟺ z=0．系统(7)的任意解z(t)满足不等式：
(8)
其中a,b,p,q>0，kp<1，kq>1．全局固定时间如下：
(9)
不等式约束优化问题(6)可以通过内点法[15]转化为无约束的优化问题[25]：
(10)
参数θ>0，根据内点法可知参数θ→0．
引理2 目标函数(10)与问题(6)逼近误差的上界为θ．
证明 对于任意的θ>0，目标函数都是凸的，问题(6)的Lagrange函数为
取Lagrange函数最优解:
对于θ>0，函数(10)取
为最优解，可以得知当θ→0时
收敛于z*．
则
给出
因此有
(11)
从式(11)中可以得出，取最优点时，目标函数(10)与问题(6)的逼近误差为θ．
已知ATA是一个半正定且对称的矩阵，而
也为半正定，则B为半正定．
所以存在一个r>0，使得B+θd≥rI成立，
则目标函数为严格凸函数．由此可知
F(z* )=Bz*T+c-θ/z* =0，z* 为目标函数F(z)唯一的最优点．
有限时间收敛取决于初始条件，固定时间收敛与初值条件无关，接下来提出一种基于固定时间梯度流的稳定算法：
(12)
其中
c1，c2>0，l1>1，0<l2<1．
引理3 算法(12)的平衡点是问题(10)的最优点．
证明 对于算法(12)的平衡点即
满足
则BzT+c-θ/z=0，对问题(10)求一阶导得到F(z)=Bz+c-θ/z，因此问题(10)的F(z* )=0 ，则
这就保证了算法(12)的平衡点等价于问题(10)的最优点z*．
定理1 当目标函数F(z)是严格凸函数，存在一个r>0，B+θd≥rI，对于任意的z(0)在固定时间T1<∞，算法(12)的轨迹收敛于最优点z*．
证明 选取Lyapunov函数V(z)=‖BzT+c-θ/z‖2/2并对函数的时间求导得
令α1=2-(l1-1)/l1和α2=2-(l2-1)/l2，因为l1>1，可得1<α1<2，同样地，0<l2<1，可得α2>2．将B+θd≥rI代入上述等式，可以得到如下不等式:
-c1r·2α1/2Vα1/2(z)-c2r·2α2/2Vα2/2(z)，
这里的α1/2<1，α2/2>1．因此,对于所有的t≥T1，V(z(t))=0，这里
t=
(c1r·2α1/2Vα1/2+c2r·2α2/2Vα2/2)-1dV=
(c1r·2α1/2Vα1/2+c2r·2α2/2Vα2/2)-1dV+
(c1r·2α1/2Vα1/2+c2r·2α2/2Vα2/2)-1dV≤
(c1r·2α1/2Vα1/2)-1dV+(c2r·2α2/2Vα2/2)-1dV=
所以
接下来，将本文算法与投影神经网络算法[19]作对比，仿真过程如下．原始的稀疏信号x∈Rn，n=128，稀疏度s=5位置是任意产生的，稀疏信号的非零项从正态Gauss分布(normal Gaussian distribution)中提取．然后观测向量b∈Rm，m=64，这里的b=Ax，观测矩阵A服从正态Gauss分布，A∈Rm×n(将A中的每列元素都单位标准化)．相对误差的计算方式为
代表算法重构的信号．依据文献[14]，参数α的选取如下：
其中σ>0，本实验中选取σ=0.005，惩罚因子θ=0.000 1，对全局收敛性进行分析,分别绘制了信号重构图、相对误差图、信号收敛图，如图1～3所示．
图1 算法重构信号的对比
Fig. 1 Comparison of algorithm reconstruction signals
在初始条件相同的情况下，图1把本文算法和投影神经网络算法进行比较．结果表明，本文算法与投影神经网络算法具有相同的稀疏解，有5个非零分量，对应于原始稀疏信号x中的非零分量．
在初始条件相同的情况下，图2对比了本文算法与投影神经网络算法重构信号的误差．结果表明，本文算法与投影神经网络算法收敛后的相对误差相同．
图2 算法重构的重构误差对比 图3 算法重构的收敛图对比
Fig. 2 Comparison of algorithm reconstruction errors Fig. 3 Comparison of the convergent graphs reconstructed by the algorithm
图3给出了本文算法与投影神经网络算法解的收敛图对比．相对于投影神经网络算法，本文算法收敛更快，能够在较短的时间内达到收敛．
本文对于1-2范数最小化的稀疏信号重构问题，提出了一种基于固定时间梯度流信号重构的算法，给出了具体过程，通过内点法把问题(6)转化为无约束优化问题(10)，用分块矩阵的半正定性证明了问题(10)即目标函数F(z)为严格凸函数． 证明了问题(12)的平衡点是问题(10)的最优点以及该算法在Lyapunov函数上的稳定性．最后通过实验与投影神经网络算法相比较，得出本文提出算法的收敛速度更快．
[1] CAND
S E J. Compressive sampling[J]. Proceedings of International Congress of Mathematicians, 2006, 17(2): 1433-1452.
[2] DONOHO D. Compressed sensing[J]. IEEE Transactions on Information Theory, 2006, 52(4): 1289-1306.
[3] COMBETTES P L. Signal recovery by proximal forward-backward splitting[J]. Multiscale Modeling & Simulation, 2005, 4(4): 1168-1200.
[4] ZHU J, ROSSET S, HASTIE T. 1-norm support vector machines[C]//Advances in Neural Information Processing Systems. Vancouver, Canada: MIT Press, 2003: 49-56.
[5] NATARAJAN B K. Sparse approximation solutions to linear systems[J]. SIAM Journal on Computing, 1995, 24(2): 227-234.
[6] YIN P, LOU Y, HE Q, et al. Minimization of 1-2 for compressed sensing[J]. SIAM Journal on Scientific Computing, 2015, 37(1): 536-563.
[7] 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.
[8] CANDES E, TAO T. Decoding by linear programming[J]. IEEE Transactions on Information Theory, 2005, 51(12): 4203-4215.
[9] YANG A, GANESH A, SASTRY S, et al. Fast 1-minimization algorithms and an application in robust face recognition[C]//Proceedings of the 17th IEEE International Conference on Image Processing (ICIP). Hong Kong, China, 2010.
[10] ANDRES A M, PADOVANI S, TEPPER M, et al. Face recognition on partially occluded images using compressed sensing[J]. Pattern Recognition Letters, 2014, 36: 235-242.
[11] MALLAT S. A Wavelet Tour of Signal Processing: the Sparse Way[M]. Burlington: Academic Press, 2009.
[12] BRUCKSTEIN A M, DONOHO D L, ELAD M. From sparse solutions of systems of equations to sparse modeling of signals and images[J]. SIAM Review, 2009, 51: 34-81.
[13] 陈鹏清, 黄尉. 基于l1-l2范数的块稀疏信号重构[J]. 应用数学和力学, 2017, 38(8): 932-942.(CHEN Pengqing, HUANG Wei. Block-sparse signal recovery based on l1-l2 norm minimization[J]. Applied Mathematice and Mechanics, 2017, 38(8): 932-942.(in Chinese))
[14] CHEN S S, DONOHO D L, SAUNDERS M A. Atomic decomposition by basis pursuit[J]. SIAM Review, 2001, 43(1): 129-159.
[15] KIM S J, KOH K, LUSTIG M, et al. An interior-point method for large-scale 1-regularized least squares[J]. IEEE Journal on Selected Topics in Signal Processing, 2007, 51: 606-617.
[16] TANK D W, HOPFIELD J J. Simple neural optimization network: an A/D converter, signal decision circuit and a linear programming circuit[J]. IEEE Transactions on Circuits and Systems, 1986, 33(5): 533-541.
[17] BALAVOINE A, ROMBERG J, ROZELL C J. Convergence and rate analysis of neural networks for sparse approximation[J]. IEEE Transactions on Neural Networks and Learning Systems, 2012, 23(9): 1377-1389.
[18] LIU Q, WANG J. L1-minimization algorithms for sparse signal reconstruction based on a projection neural network[J]. IEEE Transactions on Neural Networks and Learning Systems, 2016, 27(3): 698-707.
[19] LIU Y W, HU J F. A neural network for 1-2 minimization based on scaled gradient projection: application to compressed sensing[J]. Neurocomputing, 2016, 173(3): 988-993.
[20] GARG K, PANAGOU D. A new scheme of gradient flow and saddle-point dynamics with fixed-time convergence guarantees[R/OL]. [2019-07-02]. https:/arxiv.org/abs/1808.10474v1.
[21] FUCHS J J. Multipath time-delay detection and estimation[J]. IEEE Transactions on Signal Processing, 1999, 47(1): 237-243.
[22] POLYAKOV A. Nonlinear feedback design for fixed-time stabilization of linear control systems[J]. IEEE Transactions on Automatic Control, 2012, 57(8): 2106-2110.
[23] BHAT S P, BERNSTEIN D S. Finite-time stability of continuous autonomous systems[J]. SIAM Journal of Control and Optimization, 2000, 38(3): 751-766.
[24] ORLOV Y. Finite time stability and robust control synthesis of uncertain switched systems[J]. SIAM Journal of Control and Optimization, 2005, 43(4): 1253-1271.
[25] LOPEZ-RAMIREZ F, EFIMOV D, POLYAKOV A, et al. On necessary and sufficient conditions for fixed-time stability of continuous autonomous systems[C]//17th European Control Conference (ECC). Cyprus, 2018.
[26] LI C, YU X, HUANG T, et al. Distributed optimal consensus over resource allocation network and its application to dynamical economic dispatch[J]. IEEE Transactions on Neural Networks and Learning Systems, 2018, 29(6): 2407-2417.
1-2 NormAbstract: The compressed sensing (CS) is a new signal sampling technology, which can reconstruct signals at sampling points far smaller than those in the traditional Nyquist sampling theorem for sparse signals. For the compressed sensing, a dynamic continuous system was used to study the sparse signal reconstruction of the 1-2 norm. A sparse signal reconstruction algorithm based on the fixed time gradient flow was proposed, and was proved to be stable in the sense of Lyapunov and to converge to the optimal solution of the problem. Finally, the feasibility and advantages in the convergence speed of this algorithm were demonstrated through comparison between the proposed algorithm and existing projection neural network algorithms.
Key words: compressed sensing; 1-2 norm; fixed-time gradient flow; sparse signal reconstruction
引用本文/Cite this paper:胡登洲, 何兴. 固定时间梯度流在1-2范数中的稀疏重构[J]. 应用数学和力学, 2019, 40(11): 1270-1277.HU Dengzhou, HE Xing. Sparse reconstruction of fixed-time gradient flow in the 1-2 norm[J]. Applied Mathematics and Mechanics, 2019, 40(11): 1270-1277.