Module sampling 

Graph signal sampling: optimal set selection, bandlimited reconstruction, bandwidth estimation (Gershgorin), and the graph uncertainty principle.

Overview

Classical Nyquist–Shannon sampling requires that a signal’s bandwidth be at most half the sampling rate. On graphs, an analogous theory exists where “frequency” is defined through the Laplacian spectrum:

• A signal is k-bandlimited if its GFT coefficients beyond index k are zero.
• A sampling set S ⊆ V is k-valid if the restriction U_k|_S (top-k eigenvectors restricted to rows in S) has full column rank.
• Gershgorin circles provide fast spectral radius bounds without computing the full eigendecomposition.
• The graph uncertainty principle quantifies the trade-off between spatial spread and spectral spread of a signal.

References

• Pesenson (2008). “Sampling in Paley-Wiener spaces on combinatorial graphs.”
• Shomorony & Avestimehr (2014). “Sampling large graphs.”
• Agaskar & Lu (2013). “A spectral graph uncertainty principle.”

Example

use scirs2_core::ndarray::Array2;
use scirs2_graph::signal_processing::sampling::{GraphSampling, BandlimitedReconstruction};
use scirs2_graph::signal_processing::gsp::GraphFourierTransform;

let mut adj = Array2::<f64>::zeros((6, 6));
for i in 0..5_usize { adj[[i, i+1]] = 1.0; adj[[i+1, i]] = 1.0; }
let gft = GraphFourierTransform::from_adjacency(&adj).unwrap();

// Find a 2-valid sampling set
let sampler = GraphSampling::new(2);
let set = sampler.greedy_sampling_set(&gft).unwrap();
println!("Sampling set: {set:?}");

Structs

BandlimitedReconstruction

Reconstruct a k-bandlimited graph signal from its samples on a node set.

GershgorinBound

Gershgorin-circle-based bounds on the graph Laplacian spectrum.

GraphSampling

Optimal graph signal sampling set selection.

GraphUncertaintyPrinciple

Graph uncertainty principle: spatial spread vs. spectral spread tradeoff.