Efficient Sampling Set Selection for Bandlimited Graph Signals Using Graph Spectral Proxies
arXiv:1510.00297 · doi:10.1109/TSP.2016.2546233
Abstract
We study the problem of selecting the best sampling set for bandlimited reconstruction of signals on graphs. A frequency domain representation for graph signals can be defined using the eigenvectors and eigenvalues of variation operators that take into account the underlying graph connectivity. Smoothly varying signals defined on the nodes are of particular interest in various applications, and tend to be approximately bandlimited in the frequency basis. Sampling theory for graph signals deals with the problem of choosing the best subset of nodes for reconstructing a bandlimited signal from its samples. Most approaches to this problem require a computation of the frequency basis (i.e., the eigenvectors of the variation operator), followed by a search procedure using the basis elements. This can be impractical, in terms of storage and time complexity, for real datasets involving very large graphs. We circumvent this issue in our formulation by introducing quantities called graph spectral proxies, defined using the powers of the variation operator, in order to approximate the spectral content of graph signals. This allows us to formulate a direct sampling set selection approach that does not require the computation and storage of the basis elements. We show that our approach also provides stable reconstruction when the samples are noisy or when the original signal is only approximately bandlimited. Furthermore, the proposed approach is valid for any choice of the variation operator, thereby covering a wide range of graphs and applications. We demonstrate its effectiveness through various numerical experiments.
14 pages, 3 figures, 4 tables, Accepted for publication in IEEE Transactions on Signal Processing
References in corpus (5)
Cited by in corpus (88)
- Convolutional Neural Network Architectures for Signals Supported on Graphs
- Graph Representation Learning: A Survey
- Kernel-based Reconstruction of Graph Signals
- Fast Resampling of 3D Point Clouds via Graphs
- Signal Processing on Higher-Order Networks: Livin' on the Edge ... and Beyond
- Sampling Signals on Graphs: From Theory to Applications
- Greedy Sampling of Graph Signals
- Adaptive Graph Signal Processing: Algorithms and Optimal Sampling Strategies
- Eigendecomposition-Free Sampling Set Selection for Graph Signals
- Graph Unrolling Networks: Interpretable Neural Networks for Graph Signal Denoising
- Subgraph-based filterbanks for graph signals
- Grid-Graph Signal Processing (Grid-GSP): A Graph Signal Processing Framework for the Power Grid
- Irregularity-Aware Graph Fourier Transforms
- Semi-Blind Inference of Topologies and Dynamical Processes over Graphs
- Spectral Domain Sampling of Graph Signals
- Deep Unsupervised Learning of 3D Point Clouds via Graph Topology Inference and Filtering
- Two-Channel Critically-Sampled Graph Filter Banks With Spectral Domain Sampling
- Reconstruction of Time-varying Graph Signals via Sobolev Smoothness
- A User Guide to Low-Pass Graph Signal Processing and its Applications
- Compressive Spectral Clustering
- Fast Graph Sampling Set Selection Using Gershgorin Disc Alignment
- Learning Graphs with Monotone Topology Properties and Multiple Connected Components
- Generalized Sampling on Graphs With Subspace and Smoothness Priors
- Graph Fourier Transform: A Stable Approximation
- Low-complexity Graph Sampling with Noise and Signal Reconstruction via Neumann Series
- A Sampling Theory Perspective of Graph-based Semi-supervised Learning
- Sensor scheduling with time, energy and communication constraints
- Inference of Spatio-Temporal Functions over Graphs via Multi-Kernel Kriged Kalman Filtering
- Semi-supervised Learning in Network-Structured Data via Total Variation Minimization
- Adaptation and learning over networks under subspace constraints -- Part I: Stability Analysis
- A-Optimal Sampling and Robust Reconstruction for Graph Signals via Truncated Neumann Series
- Graph Signal Sampling Under Stochastic Priors
- Signal Representations on Graphs: Tools and Applications
- Graph Learning from Data under Structural and Laplacian Constraints
- Gegenbauer Graph Neural Networks for Time-varying Signal Reconstruction
- Sampling of graph signals via randomized local aggregations
- Iterative reconstruction of signals on graph
- Graph Signal Restoration Using Nested Deep Algorithm Unrolling
- Graph Signal Processing: Dualizing GSP Sampling in the Vertex and Spectral Domains
- Bias-Variance Tradeoff of Graph Laplacian Regularizer
- Convolutional Learning on Multigraphs
- Graph Sampling for Matrix Completion Using Recurrent Gershgorin Disc Shift
- Two Channel Filter Banks on Arbitrary Graphs with Positive Semi Definite Variation Operators
- Discrete Signal Processing on Meet/Join Lattices
- Non-Bayesian Estimation Framework for Signal Recovery on Graphs
- Graph Vertex Sampling with Arbitrary Graph Signal Hilbert Spaces
- Graph Signal Processing: Modulation, Convolution, and Sampling
- Graph Signal Processing -- Part II: Processing and Analyzing Signals on Graphs
- Sampling Theory of Jointly Bandlimited Time-vertex Graph Signals
- Detecting Localized Categorical Attributes on Graphs
- Sampling and Inference of Networked Dynamics using Log-Koopman Nonlinear Graph Fourier Transform
- Localization, Decomposition, and Dictionary Learning of Piecewise-Constant Signals on Graphs
- Signal Recovery on Graphs: Fundamental Limits of Sampling Strategies
- Graph Signal Processing: Overview, Challenges and Applications
- Hilbert Transform, Analytic Signal, and Modulation Analysis for Graph Signal Processing
- Random sampling of bandlimited signals on graphs
- Fast Path Localization on Graphs via Multiscale Viterbi Decoding
- Optimal Sampling of Water Distribution Network Dynamics using Graph Fourier Transform
- Sampling and Recovery of Graph Signals based on Graph Neural Networks
- Decentralized Eigendecomposition for Online Learning over Graphs with Applications
- Filter Design for Autoregressive Moving Average Graph Filters
- On the Supermodularity of Active Graph-based Semi-supervised Learning with Stieltjes Matrix Regularization
- Folded Graph Signals: Sensing with Unlimited Dynamic Range
- Learning Optimal Graph Filters for Clustering of Attributed Graphs
- Robust recovery of bandlimited graph signals via randomized dynamical sampling
- Graph Blind Deconvolution with Sparseness Constraint
- Scalable -Channel Critically Sampled Filter Banks for Graph Signals
- What's in a frequency: new tools for graph Fourier Transform visualization
- Online Distributed Learning over Graphs with Multitask Graph-Filter Models
- Bayesian Design of Sampling Set for Bandlimited Graph Signals
- Optimal Sampling for Dynamic Complex Networks with Graph-Bandlimited Initialization
- Active Sampling for Approximately Bandlimited Graph Signals
- Graph Signal Processing over a Probability Space of Shift Operators
- Performance Analysis of Plug-and-Play ADMM: A Graph Signal Processing Perspective
- On Critical Sampling of Time-Vertex Graph Signals
- Constrained Sampling: Optimum Reconstruction in Subspace with Minimax Regret Constraint
- Design of Sampling Set for Bandlimited Graph Signal Estimation
- Neural Network Approximation of Graph Fourier Transforms for Sparse Sampling of Networked Flow Dynamics
- Sampling Theory of Bandlimited Continuous-Time Graph Signals
- A low discrepancy sequence on graphs
- A Novel Scheme for Support Identification and Iterative Sampling of Bandlimited Graph Signals
- Sampling Policy Design for Tracking Time-Varying Graph Signals with Adaptive Budget Allocation
- Pooling in Graph Convolutional Neural Networks
- Sensor selection on graphs via data-driven node sub-sampling in network time series
- Joint Forecasting and Interpolation of Graph Signals Using Deep Learning
- Estimating Network Processes via Blind Identification of Multiple Graph Filters
- Estimating Centrality Blindly from Low-pass Filtered Graph Signals
- Reconstruction-Cognizant Graph Sampling using Gershgorin Disc Alignment