Research On The Algorithm Of Sampling And Reconstruction For Graph Signals

Graphs are generalized data representation that can be used to describe the geometric structure of data domains in many applications,including energy,transportation,social,sensor,and neuronal networks.The weight associated with each edge in the graph usually represents the similarity between the two vertices it connects.The connectivity and edge weights can be determined by the physical properties of the current problem,and can also be inferred by the data.For instance,the edge weight can be inversely proportional to their physical distance between nodes in the network.The data on these graphs may be visualized as a finite set of samples,with one sample at each vertex in the graph.In general,we refer to these samples as a graph signal.Sampling and reconstruction of time-domain signals is the fundamental issues of traditional signal processing.Meanwhile,sampling and reconstruction of graph signals is one significant component of graph signal processing.Since the irregularity of graph signal structure,its sampling process is more complicated accordingly.Specifically,the underlying structure of the graph signal is a random-weighted graph,which may induce the random arrangement of the graph node signals.On consideration of mentioned randomness,the methodology adopted by traditional time domain signal sampling,i.e.,uniformly acquires the sampling value according to the node number,cannot achieve ideal performance.Moreover,it is tough to clearly define the spectrum aliasing effect in the graph signal transform domain.Therefore,it is immensely necessary to investigate the sampling and reconstruction theory of graph signals.This thesis focuses on the graph signal sampling and reconstruction.The main work is as follows:(1)The restoration problem of sparse graph signal is studied.Firstly,the recovery problem of compressed signal can be transformed into an optimization problem for solving frequency coefficients of graph signals.Secondly,considering sampling always carries with noise,this paper makes distribution assumptions on the error and graph frequency domain coefficients,and then adopts Bayesian analysis to transform the optimization problem of solving frequency domain coefficients into solving the maximum posterior probability of error and frequency domain coefficients.Finally,the correlation vector machine algorithm is exploited to achieve the parameters,and the normalized mean square error is used to measure the reconstruction effect.Compared with other restoration algorithms,the experimental results validate the superiority of Bayesian compressed sensing algorithm in the restoration of graph signals.(2)The improvement of the optimal sampling operator selection algorithm for band-limited graph signals is realized.Considering sampling always carries with noise,different samples selected based on perfect recovery theory have different robustness to noise.Therefore,there must be an optimal sampling operator which could minimize the deviation of the recovered signal.A greedy algorithm is usually adopted to acquire this kind of optimal sampling operator,and then the minimum eigenvalue of the target matrix is determined by feature decomposition.Consequently,the minimum eigenvalue is maximized to obtain the sampling coordinates.However,the mentioned maximum-minimization method suffers from a time-complexity problem since the target matrix is usually large.Therefore,the eigenvalue of the target matrix through the disk theorem is considered to reach the domain range,and estimate the lower bound of the minimum eigenvalue.The simulation shows that the timecomplexity of the proposed method based on the disk theorem is significantly lower than the commonly used feature decomposition method.(3)The problem of selecting the best sampling operator for approximating band-limited graph signals is investigated.The approximated band-limited graph signal is a band-limited graph signal with high-frequency leakage or high-frequency interference.When processing an approximate bandlimited graph signal,the existing processing methods of the strict band-limited signal can be adopted and improved for better matches the characteristics of the actual signal.Based on the strict sampling theory of band-limited graph signals,this paper proposes a noval sampling operator selection algorithm for approximated band-limited graph signals.By restoring the norm approximation between the original signal and the recovery graph signal,the algorithm effectively reduces the interference caused by high-frequency leakage of the graph signal.Moreover,the proposed sampling algorithm can be applicable to both directed and undirected graphs,and the recovery assumption is easy to check and satisfy.