Sampling Signals on Graphs: From Theory to Applications

The study of sampling signals on graphs, with the goal of building an analog of sampling for standard signals in the time and spatial domains, has attracted considerable attention recently. Beyond adding to the growing theory on graph signal processing (GSP), sampling on graphs has various promising applications. In this article, we review the current progress on sampling over graphs, focusing on theory and potential applications.

Although most methodologies used in graph signal sampling are designed to parallel those used in sampling for standard signals, sampling theory for graph signals significantly differs from the theory of Shannon–Nyquist and shift-invariant (SI) sampling. This is due, in part, to the fact that the definitions of several important properties, such as shift invariance and bandlimitedness, are different in GSP systems. Throughout this review, we discuss similarities and differences between standard and graph signal sampling and highlight open problems and challenges.

Sampling is one of the fundamental tenets of digital signal processing (see [1] and the references therein). As such, it has been studied extensively for decades and continues to draw considerable research efforts. Standard sampling theory relies on concepts of frequency domain analysis, SI signals, and bandlimitedness [1]. The sampling of time and spatial domain signals in SI spaces is one of the most important building blocks of digital signal processing systems. However, in the big data era, the signals we need to process often have other types of connections and structure, such as network signals described by graphs.