Distributed Online Reconstruction Algorithms For Spatiotemporal Signals Based On Graph Signal Processing

In today's information age,many spatio-temporal signals show the characteristics of large scale,high dimensionality and irregular structure,such as temperature data in wireless sensor networks,traffic data in traffic networks and bioelectrical data in bio-neuron networks.Since classical signal processing can not process such signals efficiently and quickly,researchers put forward graph signal processing theory.Similar to classical signal processing,the proposed theory is a powerful tool for processing signals in irregular domains defining concepts of graph Fourier transform,filtering and modulation.Spatio-temporal signals in the real world can be regarded as time-varying graph signals.Due to factors such as energy limitation,noise pollution,and machine failure,etc,the actual observed spatio-temporal signal may be incomplete.Therefore,it is necessary to study how to reconstruct the original signal based on its correlation characteristics and the known data.Owing to the large scale and smoothness in the spatio-temporal domain of spatio-temporal signals in many actual networks like wireless sensor networks,the reconstruction model of differential smooth graph signals has attracted attention.However,the exsiting algorithms for solving such problems still have certain problems.The batch reconstruction method has the long reconstruction time delay and cannot be implemented in a distributed manner.Compared with the distributed manner,centralized counterpart has poor scalability and robustness,requiring that the system has a central node.While the online reconstruction method has a low computation amount and allows a distributed implementation,it shows slow and unstable convergence,which may cause large communication cost.Therefore,it is necessary to design a new distributed algorithm with faster and more stable convergence.(1)When solving the online reconstruction model of differential smooth time-varying graph signals,in view of the relatively slow convergence rate and large communication cost of the existing method,a distributed online reconstruction algorithm based on subgraph decomposition is proposed.In this algorithm,the local solution of the graph signal reconstruction optimization problem is found via subgraph decomposition and local optimization,then the approximate global optimal solution is obtained via subgraph fusion.It can be proved that the matrix obtained in this way has local characteristics and can approximately replace the actual Hessian inverse.The simulation shows that the proposed algorithm has fast and stable convergence rate which meets the requirements for the online algorithm.However,it requires each vertex on the graph to compute a small matrix inversion,which leads to a relatively large calculation amount.(2)Considering the relatively large calculation amount in the first proposed algorithm,a distributed online reconstruction algorithm based on truncated Taylor series is proposed.Using the local characteristics of the Hessian matrix,this algorithm decomposes the Hessian inverse,expands it to the Taylor series and then truncates the Taylor series to get the Hessian inverse approximation which completely avoids large matrix inversion and therefore leads to the small computation cost.The simulation results show that the convergence rate of this algorithm is also relatively stable but slightly slower than the first algorithm,however its calculation cost is significantly reduced.