# Sampling Method for Generalized Graph Signals with Pre-selected Vertices via DC Optimization

arXiv: https://arxiv.org/abs/2509.14836 · HTML: https://mlsanity.com/paper/2509.14836/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 17 of its 48 references that are in the map.
- First posted on arXiv 18 Sep 2025.

## Builds on (most cited first, 17 of 17)

- [Graph Spectral Image Processing](https://mlsanity.com/paper/1801.04749/) (2018)
- [Discrete Signal Processing on Graphs: Sampling Theory](https://mlsanity.com/paper/1503.05432/) (2015)
- [Stationary signal processing on graphs](https://mlsanity.com/paper/1601.02522/) (2016)
- [Sampling of graph signals with successive local aggregations](https://mlsanity.com/paper/1504.04687/) (2015)
- [Graph Learning from Filtered Signals: Graph System and Diffusion Kernel Identification](https://mlsanity.com/paper/1803.02553/) (2018)
- [A Multiscale Pyramid Transform for Graph Signals](https://mlsanity.com/paper/1308.4942/) (2013)
- [Random sampling of bandlimited signals on graphs](https://mlsanity.com/paper/1511.05118/) (2015)
- [Group SLOPE - adaptive selection of groups of predictors](https://mlsanity.com/paper/1610.04960/) (2016)
- [Graph Signal Restoration Using Nested Deep Algorithm Unrolling](https://mlsanity.com/paper/2106.15910/) (2021)
- [Fast Graph Sampling Set Selection Using Gershgorin Disc Alignment](https://mlsanity.com/paper/1907.06179/) (2019)
- [Generalized Sampling on Graphs With Subspace and Smoothness Priors](https://mlsanity.com/paper/1905.04441/) (2019)
- [Practical graph signal sampling with log-linear size scaling](https://mlsanity.com/paper/2102.10506/) (2021)
- [A Probabilistic Interpretation of Sampling Theory of Graph Signals](https://mlsanity.com/paper/1503.06629/) (2015)
- [Robust Time-Varying Graph Signal Recovery for Dynamic Physical Sensor Network Data](https://mlsanity.com/paper/2202.06432/) (2022)
- [A general double-proximal gradient algorithm for d.c. programming](https://mlsanity.com/paper/1610.06538/) (2016)
- [Graph Signal Sampling Under Stochastic Priors](https://mlsanity.com/paper/2206.00382/) (2022)
- [Generalized Graph Signal Sampling by Difference-of-Convex Optimization](https://mlsanity.com/paper/2306.14634/) (2023)

## Abstract (arXiv)

This paper proposes a method for vertex-wise flexible sampling of a broad class of graph signals, designed to attain the best possible recovery based on the generalized sampling theory. This is achieved by designing a sampling operator by an optimization problem, which is inherently non-convex, as the best possible recovery imposes a rank constraint. An existing method for vertex-wise flexible sampling is able to control the number of active vertices but cannot incorporate prior knowledge of mandatory or forbidden vertices. To address these challenges, we formulate the operator design as a problem that handles a constraint of the number of active vertices and prior knowledge on specific vertices for sampling, mandatory inclusion or exclusion. We transformed this constrained problem into a difference-of-convex (DC) optimization problem by using the nuclear norm and a DC penalty for vertex selection. To solve this, we develop a convergent solver based on the general double-proximal gradient DC algorithm. The effectiveness of our method is demonstrated through experiments on various graph signal models, including real-world data, showing superior performance in the recovery accuracy by comparing to existing methods.