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.
Smooth signals or approximately smooth signals over graph are common in practical applications @cite_15 @cite_26 @cite_31 @cite_38 , especially for those cases in which the graph topologies are constructed to enforce the smoothness property of signals @cite_25 . Exploiting the smoothness of a graph signal, it may be reconstructed through its entries on only a part of the vertices, i.e. samples of the graph signal.
@cite_38 @cite_31 @cite_26 @cite_15 @cite_25
2103351706 2215668387 2964012239 2398592859
In this paper, we introduce the concept of smoothness for signals supported on the vertices of a graph. We provide theoretical explanations when and why the Laplacian eigenbasis can be regarded as a meaningful “Fourier” transform of such signals. Moreover, we analyze the desired properties of the underlying graphs for better compressibility of the signals. We verify our theoretical work by experiments on real world data. In many applications, the observations can be represented as a signal defined over the vertices of a graph. The analysis of such signals requires the extension of standard signal processing tools. In this paper, first, we provide a class of graph signals that are maximally concentrated on the graph domain and on its dual. Then, building on this framework, we derive an uncertainty principle for graph signals and illustrate the conditions for the recovery of band-limited signals from a subset of samples. We show an interesting link between uncertainty principle and sampling and propose alternative signal recovery algorithms, including a generalization to frame-based reconstruction methods. After showing that the performance of signal recovery algorithms is significantly affected by the location of samples, we suggest and compare a few alternative sampling strategies. Finally, we provide the conditions for perfect recovery of a useful signal corrupted by sparse noise, showing that this problem is also intrinsically related to vertex-frequency localization properties. The construction of a meaningful graph plays a crucial role in the success of many graph-based representations and algorithms for handling structured data, especially in the emerging field of graph signal processing. However, a meaningful graph is not always readily available from the data, nor easy to define depending on the application domain. In particular, it is often desirable in graph signal processing applications that a graph is chosen such that the data admit certain regularity or smoothness on the graph. In this paper, we address the problem of learning graph Laplacians, which is equivalent to learning graph topologies, such that the input data form graph signals with smooth variations on the resulting topology. To this end, we adopt a factor analysis model for the graph signals and impose a Gaussian probabilistic prior on the latent variables that control these signals. We show that the Gaussian prior leads to an efficient representation that favors the smoothness property of the graph signals. We then propose an algorithm for learning graphs that enforces such property and is based on minimizing the variations of the signals on the learned graph. Experiments on both synthetic and real world data demonstrate that the proposed graph learning framework can efficiently infer meaningful graph topologies from signal observations under the smoothness prior. The construction of a meaningful graph plays a crucial role in the success of many graph-based data representations and algorithms, especially in the emerging field of signal processing on graphs. However, a meaningful graph is not always readily available from the data, nor easy to define depending on the application domain. In this paper, we address the problem of graph learning, where we are interested in learning graph topologies, namely, the relationships between data entities, that well explain the signal observations. In particular, we want to infer a graph such that the input data forms graph signals with smooth variations on the resulting topology. To this end, we adopt a factor analysis model for the graph signals and impose a Gaussian probabilistic prior on the latent variables that control these graph signals. We show that the Gaussian prior leads to an efficient representation that favors the smoothness property of the graph signals. We then propose an algorithm for learning graphs that enforce such smoothness property for the signal observations by minimizing the variations of the signals on the learned graph. Experiments on both synthetic and real world data demonstrate that the proposed graph learning framework can efficiently infer meaningful graph topologies from only the signal observations.