Research On Key Techniques Of Graph Signal Sampling And Reconstruction

With the explosive growth of information,massive amounts of graph structure data are generated at an unprecedented rate from various signal sources.These data are often characterized by high dimensions and irregular spatial distribution.In order to effectively analyze and process these data,graph signal processing technology emerges as the times require.Sampling is the core way to deal with high-dimensional data problems,and reconstruction is an important tool to solve inverse problems.They play an important role in graph signal processing.Matrix inversion approximation?MIA?graph signal reconstruction algorithm has been proved to have lower complexity than the traditional Least Squares?LS?reconstruction,but it needs the eigenvalue information of the Laplace matrix of graph.Aiming at the eigenvalue information needed by the existing MIA algorithm,this thesis proposes a fast method for calculate the eigenvalue of Laplace operator in the field of graph signal processing.This method has lower complexity than the existing eigenvalue solving methods.Then,the proposed eigenvalue solution method is used to improve the MIA algorithm,and an accelerated-matrix inversion approximation?A-MIA?reconstruction strategy with higher reconstruction speed is obtained.The main contents and innovations of this thesis are as follows:1.Based on the existing theory of graph signal processing,the basic concepts of graph signal,graph frequency domain,cut-off frequency of graph and graph Fourier transform are summarized,and two kinds of representation of graph signal in vertex domain and graph frequency domain are given.Then,some basic properties and theorems of graph signal are summarized,the transformation mechanism of graph signal is analyzed.And the problems to be solved in sampling and reconstruction of graph signal are put forward.Several existing solutions and basic principles are introduced.2.By analyzing and studying the characteristics of cut-off frequencies of graphs,two methods of calculating cut-off frequencies are introduced,one is approximate solution method,which reveals the relationship between cut-off frequencies and the minimum singular value of reduced matrix ??^k?_S^c;the other is exact solution method,which gives the relationship among sample set size,cut-off frequencies and eigenvalues of Laplace matrix.By combining these two methods,we propose a fast method to calculate the eigenvalues of the Laplacian operator in the field of image signal processing.The feasibility of the proposed method is verified by simulation,and compared with several existing eigenvalue calculation methods.The simulation results show that the proposed method is faster than the existing eigenvalue calculation methods.3.Based on the reconstruction theory of the band-limited graph signal,matrix inversion approximation-based graph signal reconstruction?MIA?algorithm is introduced.This algorithm has been proved that it does not need matrix inversion anymore,but it needs the eigenvalue information of Laplace matrix.We use the fast eigenvalue solution method proposed above to obtain the required eigenvalues,and thus propose a new signal reconstruction strategy with lower computational complexity and higher reconstruction accuracy.Finally,the proposed strategy is simulated by using three typical graph structures and topological graphs constructed by handwritten digital sets.The feasibility of the proposed strategy is verified and compared with several existing reconstruction methods.The simulation results show that the proposed method has better performance than the existing graph signal reconstruction methods.