Signal processing on graph is attracting more and more attentions. For a graph signal in the low-frequency subspace, the missing data associated with unsampled vertices can be reconstructed through the sampled data by exploiting the smoothness of the graph signal. In this paper, the concept of local set is introduced and two local-set-based iterative methods are proposed to reconstruct bandlimited graph signal from sampled data. In each iteration, one of the proposed methods reweights the sampled residuals for different vertices, while the other propagates the sampled residuals in their respective local sets. These algorithms are built on frame theory and the concept of local sets, based on which several frames and contraction operators are proposed. We then prove that the reconstruction methods converge to the original signal under certain conditions and demonstrate the new methods lead to a significantly faster convergence compared with the baseline method. Furthermore, the correspondence between graph signal sampling and time-domain irregular sampling is analyzed comprehensively, which may be helpful to future works on graph signals. Computer simulations are conducted. The experimental results demonstrate the effectiveness of the reconstruction methods in various sampling geometries, imprecise priori knowledge of cutoff frequency, and noisy scenarios.
There has been some theoretical analysis on the sampling and reconstruction of bandlimited graph signals @cite_29 @cite_13 @cite_17 @cite_35 . Some existing works focus on the theoretical conditions for the exact reconstruction of bandlimited signals. The relationships between the sampling sets of unique reconstruction and the cutoff frequency of bandlimited signal space are established for normalized Laplacian @cite_29 and unnormalized Laplacian @cite_17 @cite_35 , respectively. Recently, a necessary and sufficient condition of exact reconstruction is established in @cite_0 . In order to reconstruct bandlimited graph signals from sampled data, several methods have been proposed. In @cite_26 a least square approach is proposed to solve this problem. Furthermore, an iterative reconstruction method is proposed and a tradeoff between smoothness and data-fitting is introduced for real world applications @cite_43 .
@cite_35 @cite_26 @cite_29 @cite_0 @cite_43 @cite_13 @cite_17
1986880804 2119699244 2024457004 2030319053 2095414057 1974306717
We prove Poincare and Plancherel--Polya inequalities for weighted @math -spaces on weighted graphs in which the constants are explicitly expressed in terms of some geometric characteristics of a graph. We use a Poincare-type inequality to obtain some new relations between geometric and spectral properties of the combinatorial Laplace operator. Several well-known graphs are considered to demonstrate that our results are reasonably sharp. The Plancherel--Polya inequalities allow for application of the frame algorithm as a method for reconstruction of Paley--Wiener functions on weighted graphs from a set of samples. The results are illustrated by developing Shannon-type sampling in the case of a line graph. In this paper, we propose a novel algorithm to interpolate data defined on graphs, using signal processing concepts. The interpolation of missing values from known samples appears in various applications, such as matrix vector completion, sampling of high-dimensional data, semi-supervised learning etc. In this paper, we formulate the data interpolation problem as a signal reconstruction problem on a graph, where a graph signal is defined as the information attached to each node (scalar or vector values mapped to the set of vertices edges of the graph). We use recent results for sampling in graphs to find classes of bandlimited (BL) graph signals that can be reconstructed from their partially observed samples. The interpolated signal is obtained by projecting the input signal into the appropriate BL graph signal space. Additionally, we impose a bilateral' weighting scheme on the links between known samples, which further improves accuracy. We use our proposed method for collaborative filtering in recommendation systems. Preliminary results show a very favorable trade-off between accuracy and complexity, compared to state of the art algorithms. A notion of Paley-Wiener spaces on combinatorial graphs is introduced. It is shown that functions from some of these spaces are uniquely determined by their values on some sets of vertices which are called the uniqueness sets. Such uniqueness sets are described in terms of Poincare-Wirtinger-type inequalities. A reconstruction algorithm of Paley-Wiener functions from uniqueness sets which uses the idea of frames in Hilbert spaces is developed. Special consideration is given to the n-dimensional lattice, homogeneous trees, and eigenvalue and eigenfunction problems on finite graphs. In this paper, we extend the Nyquist-Shannon theory of sampling to signals defined on arbitrary graphs. Using spectral graph theory, we establish a cut-off frequency for all bandlimited graph signals that can be perfectly reconstructed from samples on a given subset of nodes. The result is analogous to the concept of Nyquist frequency in traditional signal processing. We consider practical ways of computing this cut-off and show that it is an improvement over previous results. We also propose a greedy algorithm to search for the smallest possible sampling set that guarantees unique recovery for a signal of given bandwidth. The efficacy of these results is verified through simple examples. In this paper, we present two localized graph filtering based methods for interpolating graph signals defined on the vertices of arbitrary graphs from only a partial set of samples. The first method is an extension of previous work on reconstructing bandlimited graph signals from partially observed samples. The iterative graph filtering approach very closely approximates the solution proposed in the that work, while being computationally more efficient. As an alternative, we propose a regularization based framework in which we define the cost of reconstruction to be a combination of smoothness of the graph signal and the reconstruction error with respect to the known samples, and find solutions that minimize this cost. We provide both a closed form solution and a computationally efficient iterative solution of the optimization problem. The experimental results on the recommendation system datasets demonstrate effectiveness of the proposed methods. In this paper we address sampling and approximation of functions on combinatorial graphs. We develop filtering on graphs by using Schrodinger’s group of operators generated by combinatorial Laplace operator. Then we construct a sampling theory by proving Poincare and Plancherel-Polya-type inequalities for functions on graphs. These results lead to a theory of sparse approximations on graphs and have potential applications to filtering, denoising, data dimension reduction, image processing, image compression, computer graphics, visualization and learning theory.