The rapid development of signal processing on graphs provides a new perspective for processing large-scale data associated with irregular domains. In many practical applications, it is necessary to handle massive data sets through complex networks, in which most nodes have limited computing power. Designing efficient distributed algorithms is critical for this task. This paper focuses on the distributed reconstruction of a time-varying bandlimited graph signal based on observations sampled at a subset of selected nodes. A distributed least square reconstruction (DLSR) algorithm is proposed to recover the unknown signal iteratively, by allowing neighboring nodes to communicate with one another and make fast updates. DLSR uses a decay scheme to annihilate the out-of-band energy occurring in the reconstruction process, which is inevitably caused by the transmission delay in distributed systems. Proof of convergence and error bounds for DLSR are provided in this paper, suggesting that the algorithm is able to track time-varying graph signals and perfectly reconstruct time-invariant signals. The DLSR algorithm is numerically experimented with synthetic data and real-world sensor network data, which verifies its ability in tracking slowly time-varying graph signals.
Some theoretical results have been established for the sampling problem of bandlimited graph-based signals; see e.g., @cite_30 @cite_24 @cite_20 . The relation between the sample size necessary to obtain unique reconstruction and the cutoff frequency of bandlimited signal space has been studied. Similar to classical results on time-domain irregular sampling, the idea of frame" has been introduced for graph signal processing. The unique reconstruction conditions have been derived for normalized and unnormalized Laplacians @cite_30 @cite_43 . As the field of graph signal processing is rapidly developing, we summarize some recent related works as follows. A least square approach has been proposed in @cite_27 to reconstruct bandlimited graph signal from signal values observed on sampled vertices, using a centralized algorithm. An iterative method of bandlimited graph signal reconstruction has been proposed in @cite_45 , with the practical consideration of balancing a tradeoff between smoothness and data-fitting. Two more efficient iterative reconstruction methods using the local set have been considered in @cite_2 @cite_38 . A necessary and sufficient condition for perfect reconstruction of bandlimited graph signal has been derived in @cite_0 . Readers may refer to Section for more details of related works.
@cite_30 @cite_38 @cite_24 @cite_43 @cite_27 @cite_45 @cite_0 @cite_2 @cite_20
2030643321 2891091350 2030368230 2179147795
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. In this paper we propose a novel vertex based sampling method for k-bandlimited signals lying on arbitrary graphs, that has a reasonable computational complexity and results in low reconstruction error. Our goal is to find the smallest set of vertices that can guarantee a perfect reconstruction of any k-bandlimited signal on any connected graph. We propose to iteratively search for the vertices that yield the minimum reconstruction error, by minimizing the maximum eigenvalue of the error covariance matrix using a linear solver. We compare the performance of our method with state-of-the-art sampling strategies and random sampling on graphs. Experimental results show that our method successfully computes the smallest sample sets on arbitrary graphs without any parameter tuning. It provides a small reconstruction error, and is robust to noise. Signal processing on graph is attracting more and more attention. For a graph signal in the low-frequency subspace, the missing data on the vertices of graph can be reconstructed through the sampled data by exploiting the smoothness of graph signal. In this paper, two iterative methods are proposed to reconstruct bandlimited graph signal from sampled data. In each iteration, one of the proposed methods weights the sampled residual for different vertices, while the other conducts a limited propagation operation. Both the methods are proved to converge to the original signal under certain conditions. The proposed methods lead to a significantly faster convergence compared with the baseline method. Experiment results of synthetic graph signal and the real world data demonstrate the effectiveness of the reconstruction methods. We study the problem of sampling k-bandlimited signals on graphs. We propose two sampling strategies that consist in selecting a small subset of nodes at random. The first strategy is non-adaptive, i.e., independent of the graph structure, and its performance depends on a parameter called the graph coherence. On the contrary, the second strategy is adaptive but yields optimal results. Indeed, no more than O(k log(k)) measurements are sufficient to ensure an accurate and stable recovery of all k-bandlimited signals. This second strategy is based on a careful choice of the sampling distribution, which can be estimated quickly. Then, we propose a computationally efficient decoder to reconstruct k-bandlimited signals from their samples. We prove that it yields accurate reconstructions and that it is also stable to noise. Finally, we conduct several experiments to test these techniques. [Code available at http: grsamplingbox.gforge.inria.fr ]