Research On The Theory Of Sampling And Reconstruction For Graph Signals

With the rapid development of information technology,people has stepped into the era of big data and generated much processing demand for signals from different scenes,such as data from information,sensor and social networks.In these problems,what need to be processed are always high-dimensional signals with more complex network structure compared with the traditional time or spatial domain signal,bringing challenges for the traditional signal processing methods.To process this kind of signals,a new form of signal--graph signal--is presented,whose defination is based on weighted graphs: the topological structure of the data is abstracted as a weighted graph,and the signal values are mapped to the vertices of the graph,then forming graph signal.Graph signal processing mainly studies the concepts and methods of representation,analysis and transformation of graph signals,which reveals the interaction and relation inside datas and entends the traditional digital signal processing theory to the irregular graph signal through weighted graphs.Graph signal processing has been widely used in fields like biomedical,computer vision,machine learning,image processing and so on.Classical sampling theory is a vital part in traditional digit al signal processing.Similarly,the sampling and reconstruction theory of graph signals also plays an important role in graph signal processing.However,the latter is much more complex than the former.Because the underlying structure of the graph signal is a random graph whose vertex order can be randomly arranged,and the sampled values cannot be obtained evenly according to the ordinal number;furthermore,there is no clear definition of the spectral aliasing effect for graph signals.Therefore,it is necessary to study deeper about the sampling and reconstruction theory for graph signals.This thesis is mainly focused on the related problems of the sampling and reconstruction for graph signals.On the basis of the existing theory of graph signal processing,first the concept of graph signal and the basic properties and theorems of the graph Fourier transform are discussed,and the physical meaning of the graph signal frequency is given,introducing the basic operations,properties and processing tools of the graph signal,and by contrasting it with the classical signal processing theory,we reveal the irregularities of the graph signal.Second,discrete time signal is modeled as a kind of graph signal,and the traditional DFT is proved to be a simple exception of the graph Fourier transform,and we re-understand the classic Shannon sampling theorem form the perspective of signal space,and then the sampling theory of the discrete-time signal is drived,which is taken as the starting point for the sampling of graph signal.Finally,following the idea of the DFT sampling,based on the finite-dimensional discrete signal processing theory,the interpolation space are built,the relation between interpolation and sampling spaces are derived,the mechanism and theorem of the sampling and reconstruction of the graph signal are revealed,and the corresponding numerical analysis and simulation verification are given as well.