Subsampling of Correlated Graph Signals
Graph signals are functions of the underlying graph. When the edge-weight between a pair of nodes is high, the corresponding signals generally have a higher correlation. As a result, the signals can be represented in terms of a graph-based generative model. The question then arises whether measurements can be obtained on a few nodes and whether the correlation structure between the signals can be used to reconstruct the graph signal on the remaining nodes. We show that node subsampling is always possible for graph signals obtained through a generative model. Further, a method to determine the number of nodes to select is proposed based on the tolerable error. A correlation-based fast greedy algorithm is developed for selecting the nodes. Finally, we verify the proposed method on different deterministic and random graphs, and show that near-perfect reconstruction is possible with node subsampling.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Robust Scaling in Human Brain Dynamics Despite Latent Variables and Limited Sampling Distortions
The idea that information-processing systems operate near criticality to enhance computational performance is supported by scaling signatures in brain activity. However, external signals raise the question of whether thi…
Sampling and Reconstruction of Signals on Product Graphs
In this paper, we consider the problem of subsampling and reconstruction of signals that reside on the vertices of a product graph, such as sensor network time series, genomic signals, or product ratings in a social netw…
Active LearningRecommendation SystemsTime SeriesTime Series AnalysisSampling of Correlated Bandlimited Continuous Signals by Joint Time-vertex Graph Fourier Transform
When sampling multiple signals, the correlation between the signals can be exploited to reduce the overall number of samples. In this paper, we study the sampling theory of multiple correlated signals, using correlation …
Model-based Subsampling for Knowledge Graph Completion
Subsampling is effective in Knowledge Graph Embedding (KGE) for reducing overfitting caused by the sparsity in Knowledge Graph (KG) datasets. However, current subsampling approaches consider only frequencies of queries t…
Graph EmbeddingKnowledge Graph CompletionKnowledge Graph EmbeddingmodelLearning-based Compressive Subsampling
The problem of recovering a structured signal $\mathbf{x} \in \mathbb{C}^p$ from a set of dimensionality-reduced linear measurements $\mathbf{b} = \mathbf {A}\mathbf {x}$ arises in a variety of applications, such as medi…
Combinatorial Optimization