Subset Random Sampling and Reconstruction of Finite Time-Vertex Graph Signals

Abstract

Finite time-vertex graph signals (FTVGS) provide an efficient representation for capturing spatio-temporal correlations across multiple data sources on irregular structures. Although sampling and reconstruction of FTVGS with known spectral support have been extensively studied, the case of unknown spectral support requires further investigation. Existing random sampling methods may extract samples from any vertex at any time, but such strategies are not friendly in practice, where sampling is typically limited to a subset of vertices and moments. To address this requirement, we propose a subset random sampling scheme for FTVGS. Specifically, we first randomly select a subset of rows and columns to form a submatrix, followed by random sampling within that submatrix. In theory, we provide sufficient conditions for reconstructing the original FTVGS with high probability. Additionally, we introduce a reconstruction framework incorporating low-rank, sparsity, and smoothness priors (LSSP), and verify the feasibility of the reconstruction and the effectiveness of the framework through experiments.

arXiv commentThis paper was published in IEEE Transactions on Signal and Information Processing over Networks (2025)

References in corpus (9)

• Graph Signal Processing: History, Development, Impact, and Outlook
• Noisy low-rank matrix completion with general sampling distribution
• Adaptive Graph Signal Processing: Algorithms and Optimal Sampling Strategies
• Reconstruction of Time-varying Graph Signals via Sobolev Smoothness
• Robust CUR Decomposition: Theory and Imaging Applications
• Graph Fourier Transform: A Stable Approximation
• A Hilbert Space Theory of Generalized Graph Signal Processing
• Matrix Completion with Cross-Concentrated Sampling: Bridging Uniform Sampling and CUR Sampling
• Sampling Theory of Jointly Bandlimited Time-vertex Graph Signals