.png){kind=icon}
.png){kind=icon}
Return
Sampling and Uniqueness Sets in Graphon Signal Processing
.png){kind=icon}
PRE
AI
DOI：10.1109/TSP.2025.3577112.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
In this work, we study the properties of sampling sets on families of large graphs by leveraging the theory of graphons and graph limits. We extend to graphon signals the notion of removable and uniqueness sets, which was developed originally for the analysis of signals on graphs. We state the formal definition of a <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\Lambda-$</tex-math></inline-formula>removable set and conditions under which a bandlimited graphon signal can be represented uniquely when its samples are obtained from the complement of a <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\Lambda-$</tex-math></inline-formula>removable set in the graphon. By leveraging such results we show that graphon representations of graph signals can be used as a common framework to compare sampling sets between graphs with different numbers of nodes and node labelings. Additionally, given a sequence of graphs that converges to a graphon, we show that the sequences of sampling sets whose graphon representation is identical in <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$[0,1]$</tex-math></inline-formula> are convergent as well. We exploit the convergence results to provide an algorithm that obtains approximately close to optimal sampling sets in large graphs where traditional methods are intractable. Performing a set of numerical experiments, we evaluate the quality of these sampling sets. Our results open the door for the efficient computation of optimal sampling sets in large graphs relying on existing methods that can be applied in small graphs.
Keywords:
Graphons
graph dense limits
signals on graphons
graph signal processing
graph signal processing on large graphs
Journal
IF:
13.7
Papers:
1.0W
Citations:
8.4W