Sampling And Reconstruction For Graph Signals

With the rapid development of information technology,networks become important sources of data.As mathematical representations of data on networks,graph signals attract increasing attentions in recent years and become one of the hot research fields of signal processing.Sampling is one of the fundamental problems of signal processing,while the research on the problem of sampling graph signals is still in the development stage.In this thesis,we focus on the problem of sampling and reconstruction for graph signals,including iterative reconstruction algorithms for bandlimited graph signals,distributed tracking algorithms for time-varying graph signals,and the extension of graph signal sampling.Besides,the balance measure for directed graphs is also studied.The main contribution of this thesis is as follows.1.Based on the concept of local sets,two iterative algorithms are proposed to reconstruct bandlimited graph signals from sampled data.The proposed algorithms are proved to reconstruct the original graph signals uniquely and precisely if the cutoff frequency of the original signals satisfies certain conditions.Frame theory is used in graph signal processing and the correspondence between graph signal sampling and time-domain irregular sampling is established.Experiments show that the proposed algorithms converge much faster than existing ones.2.A distributed algorithm is proposed to track time-varying graph signals from sampled data.The condition for parameters including stepsize is given to guarantee the convergence of tracking.This work extends the problem of graph signal sampling to the time-varying and distributed scenarios.Experiments show that the proposed distributed algorithm can track slowly varying graph signals.3.A generalized sampling scheme based on local measurement is proposed.A iterative algorithm is proposed to reconstruct the original graph signals using the local measurements.The convergence of the algorithm is theoretical proved,and the performance under noise disturbance is given.This work generalizes the sampling and reconstruction scheme for graph signals.Experiments show that the generalized sampling scheme is more robust against noise.4.Measure for directed graphs is studied.Edge balance ratio and positivity are proposed to measure the balance property of directed edges and the whole graph,re- spectively.A theoretical distribution of edge balance ratio is given for power law directed graphs.Experiments on real-world massive datasets including Twitter and Sina Weibo are conducted,which provide the balance feature of real-world social networks.