The emerging field of signal processing on graph plays a more and more important role in processing signals and information related to networks. Existing works have shown that under certain conditions a smooth graph signal can be uniquely reconstructed from its decimation, i.e., data associated with a subset of vertices. However, in some potential applications (e.g., sensor networks with clustering structure), the obtained data may be a combination of signals associated with several vertices, rather than the decimation. In this paper, we propose a new concept of local measurement, which is a generalization of decimation. Using the local measurements, a local-set-based method named iterative local measurement reconstruction (ILMR) is proposed to reconstruct bandlimited graph signals. It is proved that ILMR can reconstruct the original signal perfectly under certain conditions. The performance of ILMR against noise is theoretically analyzed. The optimal choice of local weights and a greedy algorithm of local set partition are given in the sense of minimizing the expected reconstruction error. Compared with decimation, the proposed local measurement sampling and reconstruction scheme is more robust in noise existing scenarios.
There have been several works focusing on the theory of exactly reconstructing a bandlimited graph signal from its decimation. Sufficient conditions for unique reconstruction of bandlimited graph signals from decimation are given for normalized @cite_30 and unnormalized Laplacian @cite_35 . In @cite_1 , a necessary and sufficient condition on the cutoff frequency is established and the bandwidth is estimated based on the concept of spectral moments. Several algorithms are proposed to reconstruct graph signals from decimation. In @cite_43 , an algorithm named iterative least square reconstruction (ILSR) is proposed and the tradeoff between data-fitting and smoothness is also considered. Two more efficient algorithms named iterative weighting reconstruction (IWR) and iterative propagating reconstruction (IPR) are proposed in @cite_20 with much faster convergence.
@cite_30 @cite_35 @cite_1 @cite_43 @cite_20
2024457004 1986880804 2030319053 2095414057 2030643321
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. 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 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. 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.