Research On Sampling And Reconstruction For Graph Signals

With the rapid development of information technology,the widespread popularity of smart devices has made the network an important source in modern data processing and analysis.Due to similar relationship representation as the network structure,graph has gradually been an important tool for network data analysis,which draws world-wide attention in the field of graph signal processing.The main core of graph signal processing is modeling network data as graph signals,and initially establishing a theoretical system similar to classical signal processing.This paper mainly studies the sampling and reconstruction problems in graph signal processing technology,including the composition of sampling sets,the reconstruction method of sampled signals,and the dynamic sampling strategy in resource-constrained networks.The main content and contribution of this article can be summarized as follows.1.The structure of the sampling set is studied,and two sampling methods and corresponding reconstruction algorithms are proposed.Firstly,the sampling cluster structure is defined from the perspective of the node domain,and a hierarchical classification method based on node degree information is proposed.Based on this,a sampling set composition method is given.In the process of reconstructing the sampled signal,the intra-cluster assignment and the inter-cluster interpolator operators are defined,which effectively ensures the convergence speed of the reconstruction.It is proved that the proposed reconstruction algorithm can reconstruct the original graph signal without distortion,and the corresponding constraint conditions are given.The proposed algorithm is compared with the existing algorithms.The simulation experiments show that the proposed algorithm can maintain the convergence speed similar to the existing algorithms with a lower sampling rate.Then,the Fourier transform of the graph is further studied.The implicit information of the graph structure is mined from the view of the frequency domain of the graph.The sampling algorithm based on the Laplacian eigenvector matrix is proposed,where sampling control threshold,control parameters in reconstruction accuracy and iterative step number are designed to apply in multiple scenarios.2.The reconstruction of the sampled signal is studied.Firstly,the composition framework of the unsampled signal is constructed.The diffusion method of the reconstruction residuals of the sampled signal is discussed.The local-mean and the global-bias diffusion operator are defined.Based on this,the reconstruction algorithm based on the graph diffusion operator is proposed.The limitations and the corresponding proof of the proposed algorithm are given.Simulations show that the convergence speed of the proposed algorithm is significantly improved compared with the existing reconstruction algorithms.Then,a comprehensive analysis of the known signal set,the local-mean diffusion,the global-bias diffusion and the preliminary acquisition results is presented,which leads to a weighted reconstruction method.Experiments show that the convergence speed of the proposed algorithm can be further improved.Finally,taking Beijing Traffic Congestion Index as an example,the construction method of graph model and the mapping method of graph signal are discussed.Based on this,a reconstruction algorithm for non-strict bandlimited graph signal is proposed.Simulation experiments show that the proposed reconstruction algorithm has higher reconstruction accuracy than the existing algorithm.3.A dynamic sampling strategy is proposed in a resource-constrained networks.Firstly,according to the evaluation mechanism of observation matrix in compressive sensing theory,the graph mutual-coherence coefficient between sampling operator and graph Laplacian eigenvector matrix,together with the relationship between such coefficient and reconstruction error is constructed.Then,utilizing the conclusion mentioned above,the minimum number of nodes in the sampling set is given.Finally,the optimization problem based on the variance of the remaining energy of the node and an energy balance sampling scheduling method are proposed,where sampling nodes are dynamically selected to form the sampling set.Experiments show that the proposed scheduling method performs dynamic rotation of sampled nodes and balances the energy consumption of nodes in the network.