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.
As far as we know, there is no work on reconstructing graph signals from local measurements. The idea of local measurements can be traced back to time-domain nonuniform sampling @cite_42 , or irregular sampling @cite_38 @cite_28 , which has a close relationship with graph signal sampling and reconstruction. For the signals in time-domain @cite_3 @cite_6 , shift-invariant space @cite_14 , or on manifolds @cite_11 @cite_21 , based on the theoretical results of signal reconstruction from samples, there has been extended works on reconstructing signals from local averages. However, there is no such work on graph-signal-related problems.
@cite_38 @cite_14 @cite_28 @cite_42 @cite_21 @cite_6 @cite_3 @cite_11
48974879 2100836068 607933207 2122735658 2075125636
This chapter presents methods for the reconstruction of bandlimited functions from irregular samples. The first part discusses algorithms for a constructive solution of the irregular sampling problem. An important aspect of these algorithms is the explicit knowledge of the constants involved and efficient error estimates. The second part discusses the numerical implementation of these algorithms and compares the performance of various reconstruction methods. Although most of the material has already appeared in print, several new results are included: (a) a new method to estimate frame bounds, (b) a reconstruction of band-limited functions from partial information, which is not just the samples; (c) a new result on the complete reconstruction of band-limited functions from local averages; (d) a systematic exposition of recent experimental results. Abstract The problem of reconstructing a function f from a set of non-uniformly distributed, weighted-average sampled values ∫ R d f(x)ψ x j (x) d x: j∈J is studied in the context of shift-invariant subspaces of L 2 ( R d ) . Necessary density conditions on the sampling set X= x j : j∈J for stable reconstruction are obtained, and fast iterative algorithms are described. The performance of the algorithms are analyzed when the data are corrupted by noise. Estimates are derived for the convergence rates of the algorithms in terms of the sampling density and the diameters of the sampling functionals ψ x j : x j ∈X . The results provide a mathematical framework for situations arising frequently in applications, e.g., when the sample values are not precise because they are gathered by real-world acquisition devices. 1. Introduction F. Marvasti. 2. An Introduction to Sampling Analysis P.L. Butzer, et al 3. Lagrange Interpolation and Sampling Theorems A.I. Zayed, P.L. Butzer. 4. Random Topics in Nonuniform Sampling F. Marvasti. 5. Iterative and Noniterative Recovery of Missing Samples for 1- D Band-Limited Signals P.J.S.G. Ferreira. 6. Numerical and Theoretical Aspects of Nonuniform Sampling of Band-Limited Images K. Grochenig, T. Strohmer. 7. The Nonuniform Discrete Fourier Transform S. Bagchi, S.K. Mitra. 8. Reconstruction of Stationary Processes Sampled at Random Times B. Lacaze. 9. Zero Crossings of Random Processes with Application to Estimation and Detection J. Barnett. 10. Magnetic Resonance Image Reconstruction from Nonuniformly Sampled k-Space Data F.T.A.W. Wajer, et al 11. Irregular and Sparse Sampling in Exploration Seismology A.J.W. Duijndam, et al 12. Randomized Digital Optimal Control W.L. de Koning, L.G. van Willigenburg. 13. Prediction of Band-Limited Signals from Past Samples and Applications to Speech Coding D.H. Muler, Y. Wu. 14. Frames, Irregular Sampling, and a Wavelet Auditory Model J.J. Benedetto, S. Scott. 15. Application of the Nonuniform Sampling to Motion Compensated Prediction A. Sharif, et al 16. Applications of Nonuniform Sampling to Nonlinear Modulation, A D and D A Techniques F. Marvasti, M. Sandler. 17. Applications to Error Correction Codes F. Marvasti. 18. Application of Nonuniform Sampling to Error Concealment M. Hasan, F. Marvasti. 19. Sparse Sampling in Array Processing S. Holm, et al 20. Fractional Delay Filters: Design and Applications V. Valimaki, T.I. Laakso. A constructive solution of the irregular sampling problem for band- limited functions is given. We show how a band-limited function can be com- pletely reconstructed from any random sampling set whose density is higher than the Nyquist rate, and give precise estimates for the speed of convergence of this iteration method. Variations of this algorithm allow for irregular sampling with derivatives, reconstruction of band-limited functions from local averages, and irregular sampling of multivariate band-limited functions. In the irregular sampling problem one is asked whether and how a band- limited function can be completely reconstructed from its irregularly sam- pled values f(xi). This has many applications in signal and image processing, seismology, meteorology, medical imaging, etc. Finding constructive solutions of this problem has received considerable attention among mathematicians and engineers. The mathematical literature provides several uniqueness results (1, 2, 17, 18, 19). It is now part of the folklore that for stable sampling the sampling rate must be at least the Nyquist rate (18). These results, as deep as they are, have had little impact for the applied sciences, because they were not constructive. If the sampling set is just a perturbation of the regular oversampling, then a reconstruction method has been obtained in a seminal paper by Duffin and Schaeffer (6) (see also (29)): if for some L > 0, a > 0, and o > 0 the sampling points xk , k e Z , satisfy (a) - ok a, k ^ I, then the norm equivalence A iR (x) ) with w < n o. This norm equivalence implies that it is possible to reconstruct through an iterative procedure, the so-called frame method. Most of the later work on constructive methods consists of variations of this method (3, 21, 22, 26). The above conditions on the sampling set exclude random irregular sampling sets, e.g., sets with regions of higher sampling density. A partial, but undesirable remedy, to handle highly irregular sampling sets, would be to force the above conditions by throwing away information on part of the points and accept a very slow convergence of the iteration. The main goal of the article is to show that Paley-Wiener functions ƒ ∈ L 2(M) of a fixed band width to on a Riemannian manifold of bounded geometry M completely determined and can be reconstructed from a set of numbers Φi (ƒ), i ∈ ℕwhere Φi is a countable sequence of weighted integrals over a collection of “small” and “densely” distributed compact subsets. In particular, Φi, i ∈ ℕ,can be a sequence of weighted Dirac measures δxi, xi ∈M.