Fast Graph Sampling Set Selection Using Gershgorin Disc Alignment

Abstract

Graph sampling set selection, where a subset of nodes are chosen to collect samples to reconstruct a smooth graph signal, is a fundamental problem in graph signal processing (GSP). Previous works employ an unbiased least-squares (LS) signal reconstruction scheme and select samples via expensive extreme eigenvector computation. Instead, we assume a biased graph Laplacian regularization (GLR) based scheme that solves a system of linear equations for reconstruction. We then choose samples to minimize the condition number of the coefficient matrix---specifically, maximize the smallest eigenvalue ${\lambda }_{\min }$. Circumventing explicit eigenvalue computation, we maximize instead the lower bound of ${\lambda }_{\min }$, designated by the smallest left-end of all Gershgorin discs of the matrix. To achieve this efficiently, we first convert the optimization to a dual problem, where we minimize the number of samples needed to align all Gershgorin disc left-ends at a chosen lower-bound target $T$. Algebraically, the dual problem amounts to optimizing two disc operations: i) shifting of disc centers due to sampling, and ii) scaling of disc radii due to a similarity transformation of the matrix. We further reinterpret the dual as an intuitive disc coverage problem bearing strong resemblance to the famous NP-hard set cover (SC) problem. The reinterpretation enables us to derive a fast approximation scheme from a known SC error-bounded approximation algorithm. We find an appropriate target $T$ efficiently via binary search. Extensive simulation experiments show that our disc-based sampling algorithm runs substantially faster than existing sampling schemes and outperforms other eigen-decomposition-free sampling schemes in reconstruction error.

Very fast deterministic graph sampling set selection algorithm without explicit eigen-decomposition

References in corpus (18)

• The Emerging Field of Signal Processing on Graphs: Extending High-Dimensional Data Analysis to Networks and Other Irregular Domains
• Discrete Signal Processing on Graphs: Sampling Theory
• Efficient Sampling Set Selection for Bandlimited Graph Signals Using Graph Spectral Proxies
• Signals on Graphs: Uncertainty Principle and Sampling
• Sampling of graph signals with successive local aggregations
• GSPBOX: A toolbox for signal processing on graphs
• Graph Laplacian Regularization for Image Denoising: Analysis in the Continuous Domain
• Graph-Based Blind Image Deblurring From a Single Photograph
• Greedy Sampling of Graph Signals
• Random Walk Graph Laplacian based Smoothness Prior for Soft Decoding of JPEG Images
• Eigendecomposition-Free Sampling Set Selection for Graph Signals
• Low-complexity Graph Sampling with Noise and Signal Reconstruction via Neumann Series
• A Sampling Theory Perspective of Graph-based Semi-supervised Learning
• Sparse Sampling for Inverse Problems with Tensors
• A-Optimal Sampling and Robust Reconstruction for Graph Signals via Truncated Neumann Series
• Sampling of graph signals via randomized local aggregations
• Bias-Variance Tradeoff of Graph Laplacian Regularizer
• 3D Point Cloud Denoising via Bipartite Graph Approximation and Reweighted Graph Laplacian

Cited by in corpus (8)

• Sampling Signals on Graphs: From Theory to Applications
• Localized Spectral Graph Filter Frames: A Unifying Framework, Survey of Design Considerations, and Numerical Comparison (Extended Cut)
• Graph Sampling for Matrix Completion Using Recurrent Gershgorin Disc Shift
• Non-Bayesian Estimation Framework for Signal Recovery on Graphs
• Sampling and Recovery of Graph Signals based on Graph Neural Networks
• A Bayesian Perspective on Uncertainty Quantification for Estimated Graph Signals
• Graph Metric Learning via Gershgorin Disc Alignment
• Signed Graph Metric Learning via Gershgorin Disc Perfect Alignment