1、第4 3卷 第2期桂 林 电 子 科 技 大 学 学 报V o l.4 3,N o.2 2 0 2 3年4月J o u r n a l o f G u i l i n U n i v e r s i t y o f E l e c t r o n i c T e c h n o l o g yA p r.2 0 2 3收稿日期:2 0 2 1-0 4-1 2基金项目:国家自然科学基金(6 1 7 6 1 0 1 1);桂林电子科技大学研究生科研创新计划(2 0 2 0 Y C S X 0 1 8)通信作者:蒋俊正(1 9 8 3-),男,教授,博士,研究方向为图信号处理理论与算法、分布式信号处
2、理理论与算法。E-m a i l:j z j i a n g g u e t.e d u.c n引文格式:池源,蒋俊正.一种空时信号的分布式在线重构算法J.桂林电子科技大学学报,2 0 2 3,4 3(2):1 2 8-1 3 4.一种空时信号的分布式在线重构算法池 源,蒋俊正(桂林电子科技大学 信息与通信学院,广西 桂林 5 4 1 0 0 4)摘 要:空时信号的在线重构问题可归结为对差分平滑的时变图信号的恢复问题。对于该凸优化问题,现有的基于梯度下降法的分布式重构算法在优化问题的海森矩阵条件数较大时收敛速度极慢,在单个观测区间内算法最大迭代次数受限时重构误差较大。针对该问题,提出了一种基于
3、近似牛顿法的分布式在线重构算法。首先通过子图划分将原优化问题分解为一系列子图上的局部优化问题,并求出该局部问题的解,然后对子图间的局部解作融合平均计算,得到近似的全局最优解,再依据近似解与实际最优解之间的差距,证明以此方式求得的子图划分与融合矩阵具有稀疏性,且可作为原优化问题的海森逆近似矩阵,最后将该近似矩阵替换至经典的牛顿法迭代公式,并利用该近似矩阵的结构化稀疏性实现分布式运算。仿真结果表明,与现有算法相比,该算法收敛速度更快,重构误差更小,所需通信量更少。关键词:空时信号;在线重构;分布式算法;近似牛顿法;子图划分中图分类号:T N 9 1 1.7 2 文献标志码:A 文章编号:1 6 7
4、 3-8 0 8 X(2 0 2 3)0 2-0 1 2 8-0 7A d i s t r i b u t e d a l g o r i t h m f o r o n l i n e r e c o n s t r u c t i o n o f s p a t i o-t e m p o r a l s i g n a l sC H I Y u a n,J I A N G J u n z h e n g(S c h o o l o f I n f o r m a t i o n a n d C o mm u n i c a t i o n,G u i l i n U n i v e r
5、s i t y o f E l e c t r o n i c T e c h n o l o g y,G u i l i n 5 4 1 0 0 4,C h i n a)A b s t r a c t:T h e r e c o n s t r u c t i o n p r o b l e m o f s p a t i o-t e m p o r a l s i g n a l s c a n b e c a s t a s r e c o v e r i n g d i f f e r e n t i a l s m o o t h t i m e-v a r y i n g g r
6、a p h s i g n a l s.F o r t h e o p t i m i z a t i o n p r o b l e m,t h e e x i s t i n g d i s t r i b u t e d a l g o r i t h m b a s e d o n g r a d i e n t d e s c e n t m e t h o d s h o w s s l o w c o n v e r g e n c e w h e n t h e c o n d i t i o n n u m b e r o f t h e H e s s i a n m a
7、t r i x o f t h e p r o b l e m i s l a r g e w h i c h l e a d s t o a l a r g e r e c o n s t r u c-t i o n e r r o r w h e n t h e m a x i m u m i t e r a t i o n n u m b e r i s l i m i t e d i n a n o b s e r v a t i o n i n t e r v a l.T h e r e f o r e,a n o n l i n e d i s t r i b u t e d r
8、e c o n-s t r u c t i o n a l g o r i t h m b a s e d o n a p p r o x i m a t e N e w t o n s m e t h o d i s p r o p o s e d i n t h e p a p e r,w h o s e p r i n c i p l e i s t o d e c o m p o s e t h e o r i g i n a l o p t i m i z a t i o n p r o b l e m i n t o a s e r i e s o f l o c a l p r
9、o b l e m s o n s u b g r a p h s t h r o u g h s u b g r a p h d e c o m p o s i t i o n a n d f i n d t h e s e s o l u t i o n s,a n d t h e n o b t a i n t h e a p p r o x i m a t e g l o b a l o p t i m a l s o l u t i o n v i a f u s i o n a v e r a g e o f l o c a l s o l u t i o n s b e t w
10、e e n e a c h s u b-g r a p h.A c c o r d i n g t o t h e g a p b e t w e e n t h e a p p r o x i m a t e s o l u t i o n a n d t h e a c t u a l o n e,i t c a n b e p r o v e d t h a t t h e d e c o m p o s t i o n a n d f u s i o n m a t r i x o b t a i n e d i n t h i s w a y i s s p a r s e a n
11、d c a n b e r e g a r d e d a s t h e a p p r o x i m a t e H e s s i a n i n v e r s e.H e n c e,t h e a l g o-r i t h m r e p l a c e s t h e a p p r o x i m a t e m a t r i x i n t o t h e c l a s s i c a l N e w t o n i t e r a t i v e f o r m u l a w h i c h c a n b e i m p l e m e n t e d i n
12、a d i s t r i b u t e d m a n n e r d u e t o t h e s t r u c t u r a l s p a r s i t y o f t h e a p p r o x i m a t e m a t r i x.S i m u l a t i o n r e s u l t s s h o w t h a t t h e p r o p o s e d a l g o r i t h m h a s f a s t e r c o n v e r g e n c e r a t e a n d s m a l l e r r e c o n
13、s t r u c t i o n e r r o r,a n d r e q u i r e s l e s s c o mm u n i c a t i o n c o s t c o m p a r e d w i t h t h e e x i s t i n g a l g o r i t h m.K e y w o r d s:s p a t i o-t e m p o r a l s i g n a l s;o n l i n e r e c o n s t r u c t i o n;d i s t r i b u t e d a l g o r i t h m;a p p r
14、 o x i m a t e N e w t o n s m e t h o d;s u b g r a p h d e c o m p o s i t i o n 当今信息时代,人类社会无处不充斥着海量的空时信号。随着科学技术的进步,这些信号逐渐向规模更大、纬度更高、结构更复杂的趋势发展,如无线传感器网络中的温度或湿度数据、社交媒体中的个人爱好信息、交通网络中的车流量数据和生物神经元网络中的生物电信号等1-2。现实世界的空时信号因能量受限、环境污染、机器故障、噪声干扰等因素影响,可能是缺失或不可靠的。以无线传感器网络中的监测工DOI:10.16725/45-1351/tn.2023.02.0
15、04第2期池 源等:一种空时信号的分布式在线重构算法作为例,由于电量、内存和处理能力有限,传感器节点无法做到对数据时刻观测,因此整个网络的观测数据可能是不完整的3-4。此外,传感器节点还可能受硬件老化、噪声干扰或剧烈环境变化等因素影响而导致其监测数据异常5,此时该节点的可靠信号值是缺失的。在空时信号存在数据缺失时,为了保证后续信号处理工作的正常进行,需利用空时信号的关联特性对信号进行重构6-7。图信号处理理论将传统信号处理邻域中的傅里叶变换、滤波、调制、卷积等概念推广到非规则的图上,是研究非规则域信号的有力工具8-9。空时信号在空间域与时间域上的关联性一般可由时变图信号的差分平滑性来描述1 0
16、-1 1。图信号的差分平滑性是指该信号及其变化量在图上相邻顶点间相近的特性。例如,在温度传感器网络中,地理距离越靠近的节点,其测得的温度值及其变化趋势一般也越相近。利用差分平滑的时变图信号在线重构模型可以对缺失的空时信号进行重构,且该模型具有计算复杂度低、重构时延小、可分布式求解的优点1 0。然而,现有的求解该模型的分布式算法均基于梯度下降法1 0,其收敛速度相对缓慢,且易受优化问题的条件数影响1 2-1 3。对于分布式算法,过慢的收敛速度会导致分布式系统内节点通信量大增1 4-1 5,从而缩短系统使用寿命,因此需要设计一种新的收敛速度更快且更稳定的分布式算法。针对现有算法1 0收敛速度相对慢的问题,提出了一种基于近似牛顿法的空时信号分布式在线重构算法。通过子图划分求出图信号重构优化问题的局部解,再进行子图融合,得到近似的全局最优解,并证明了以此方式求得的子图划分与融合矩阵具有稀疏性,可作为原优化问题的海森逆近似,最后将近似矩阵代替至牛顿法迭代公式,从而得到分布式近似牛顿法。1 空时信号在线重构模型1.1 图信号处理基础知识任意空间分布的N节点网络可建模为一个图。图G是由一组顶点与连接
