Research On Efficient Subset Sampling Of Graph Signals

Graph signal processing(GSP)is the study of discrete signals that live on irregular data kernels described by graphs,which appear from extensive applications like wireless communication,social network and recommendation system.To process such graphsupported signals,amounts of literature are published in the recent years to propose basic definitions and techniques in the GSP field,like graph signal shift,sampling,filtering and convolution.The major difference between handling graph signals and processing signals lived in regular domain,such as time-series signals,images and videos,is to take the underlying topological graph into account.Similar to discrete Fourier transform(DFT),graph Fourier transform(GFT)plays an important role in GSP filed.GFT regards eigenvectors and eigenvalues of graph operator matrix as Fourier basis and graph spectral frequency respectively.Then,the spectral characteristic of graph signals are analyzed via their projection into graph Fourier space.Basing on the notion of GFT,bandlimited graph signals can be clearly defined from graph frequency domain,which often exist in real-world scenes.Sampling of bandlimited graph signals is an important basic problem in GSP,since sensing in practice is often expensive.Generally,sampling of graph signals in the literature can be defined from three different perspectives: aggregation sampling,local measurement and subset sampling.In this dissertation,we focus on addressing the problem of subset sampling of graph signals---optimally select a subset of graph nodes from which to collect samples such that an assumed graph signals can be reconstructed in high fidelity.The existing graphic sampling methods either suffer from high complexities to collect samples or achieve inferior performance.To tackle this complexity-performance tradeoff problem,we will propose fast efficient graph sampling methods with considerable performance.The main contributions of this dissertation are as follows.We first seek a sampling strategy that directly minimizes the mean square error(MSE)of the reconstructed bandlimited graph signals.Assuming an independent and identically distributed noise model,minimizing MSE value leads naturally to A-optimal criterion in experiments design field.To avoid matrix inversion,we prove that the inverse of the information matrix in the A-optimal criterion is equivalent to a Neumann matrix series.Then,to detour eigen-decomposition of graph Laplacian matrix,we transform the truncated Neumann series-based sampling problem into an equivalent expression with a submatrix of an ideal low-pass graph filter.Finally,we approximate the ideal filter using a Chebyshev matrix polynomial.For signal reconstruction,we propose a fast accompanied signal reconstruction strategy that reuses the approximated filter submatrix and is provably more robust than conventional least square(LS)recovery.Simulation results show that our sampling strategy outperforms two popular graph sampling schemes in MSE performance with comparable complexity.Truncated Neumann series-based sampling still suffers from heavy matrix series multiplications for good approximation.To further reduce the sampling complexity and improve the performance,we next propose an augmented objective based on Neumann series.Specifically,we show that a shifted A-optimal criterion can be equivalently written as a function of an ideal low-pass(LP)graph filter,which in turn can be approximated efficiently via fast graph Fourier transform(FGFT).To minimize the new objective,we select nodes greedily without large matrix inversions using a matrix inverse lemma.Besides,the greedy solution is proved to achieve bounded performance since its corresponding set function is approximate supermodular.Then,for the dynamic subset sampling case,we further propose an extended sampling strategy based on fast node exchange.For signal reconstruction,we propose an accompanied biased signal recovery strategy that reuses the approximated filter from sampling,which benefits from low complexity.Experiments show that our reconstruction is more robust to large noise than the LS solution,and our sampling strategy far outperforms several existing schemes,including the method based on truncated Neumann series.In the third core part of this dissertation,we expand our research scope into graph sampling for matrix signals,which can be interpreted as matrix graph signals defined on double factor graphs in some applications.Matrix completion algorithms fill missing entries in a large matrix given a subset of observed samples.The problem of how to pre-select a subset of entries for graph sampling to maximize the reconstructed matrix fidelity is the key problem in data mining field.In this dissertation,we propose two graph sampling algorithms to tackle this problem:(i)a fast base sampling algorithm on general single graphs,and(ii)an extended sampling algorithm from the base algorithm for active matrix completion.Assuming the double graph smoothness prior where rows / columns of the matrix signal are smooth with respect to row / column factor graphs,we first show that a matrix signal can be recovered from partial observations by solving a system of linear equations,where the sought matrix is vectorized as vector and interpreted as a graph signal residing on a single product graph.On this single graph,to promote small reconstruction error and stability of the linear system,we maximize the smallest eigenvalue of the coefficient matrix by greedily selecting samples corresponding to the largest magnitude entries in the first eigenvectors,based on a corollary of the Gershgorin circle theorem.For large-scale active matrix completion cases,we extend the base algorithm by alternately choosing entries in the rows and columns corresponding to the largest magnitude entries in the first eigenvectors of the row / column coefficient matrix.Our algorithm benefits computationally from warm start as the first eigenvectors are computed recurrently for more samples.Extensive experiments on both synthetic and realworld datasets show that our extended graph sampling algorithm outperforms existing sampling schemes for matrix signals,when combined with a range of modern matrix completion algorithms.In summary,this dissertation at first presents one efficient subset graph sampling algorithm for bandlimited graph signals without full eigen-decomposition and any matrix inversions.Then,towards sampling on relatively large-scale problem,we further propose a faster graph sampling method using twice Nuemann series theorem to improve both sampling speed and reconstruction accuracy.For acitve matrix completion problem,we next propose one Gershgorin disc shift-based alternating matrix graph signal sampling.Extensive experiments on real-world datasets from wireless commutation and recommendation system have verified the performance and complexity superiority of the proposed graph sampling algorithms in this dissertation.