Graph Signal Sampling And Filter Design

With the development of information technology,all kinds of data are flooding all aspects of people's lives,and these data are usually high-dimensional and irregular.To deal with these irregular signals,graph signal processing(GSP)technology is proposed.This thesis mainly studies the problems of sampling and graph filter design in GSP.The main contributions of this thesis are summarized as follows:1.In view of the complexity of some sampling algorithms,this thesis proposes a filter-based sampling strategy for band-limited graph signals.First,we discuss the relationship between the unique sampling set and the bandwidth of the graph signal,and then construct a problem to solve the optimal sampling set.As it is hard to obtain optimal sampling set directly,we turn to solve the complement of the sampling set instead.After that,a filter-based algorithm is proposed.Here,the Chebyshev polynomial is used to approximate the ideal filter to reduce the computational complexity.Next,the low-bound of the minimum eigenvalue is estimated using Gershgorin Circle Theorem,and a low-complexity sampling algorithm is obtained.Based on the previous filter approximation,a low complexity reconstruction strategy is further proposed.2.Aiming at the problem that graph topology may change in actual application scenarios,this thesis studies the sampling strategy in graph perturbation model,where the graph perturbation model is that the edges between any vertices may change randomly with a small probability.According to the spectral decomposition characteristics of the graph perturbation model,we formulate the problem of minimizing the restoration error and propose a greedy algorithm to solve the target sampling set.Furthermore,we approximate the matrix inverse operation with Newman series,which greatly reduced the algorithm complexity.The simulation results show that our proposed algorithm is better than the traditional algorithms.3.As the order and the cost of finite impulse response(FIR)graph filter are very high,this thesis studies the design of autoregressive moving average(ARMA)graph filter to release the corresponding problem.The main purpose of our design is to make the frequency response of the designed ARMA graph filter as close as possible to the expected frequency response.We first formulate the original problem about the ARMA filter design.Then we propose a genetic algorithm to obtain the optimal ARMA graph filter's coefficients.The simulation results show that the proposed ARMA graph filter design method can achieve better performance compared with the existing FIR graph filter and other ARMA graph filter design methods.