Graph signals provide a natural representation of data in many applications, such as social networks, web information analysis, sensor networks, and machine learning. Graph signal & data processing is currently an active field of mathematical research that aims to extend the well-developed tools for analyzing conventional signals to signals on graphs while exploiting the underlying connectivity. A key challenge in this context is the problem of quantization, that is, finding efficient ways of representing the values of graph signals with only a finite number of bits.
In this talk, we address the problem of quantizing bandlimited graph signals. We introduce two classes of noise-shaping algorithms for graph signals that differ in their sampling methodologies. We demonstrate that these algorithms can efficiently construct quantized representatives of bandlimited graph-based signals with bounded amplitude.
Inspired by the results of Zhang et al. in 2022, we provide theoretical guarantees on the relative error between the true signal and its quantized representative for one of the algorithms.
As will be discussed, the incoherence of the underlying graph plays an important role in the quantization process. Namely, bandlimited signals supported on graphs of lower incoherence allow for smaller relative errors. We support our findings with various numerical experiments showcasing the performance of the proposed quantization algorithms for bandlimited signals defined on graphs with different degrees of incoherence.
This is joint work with Felix Krahmer (Technical University of Munich), He Lyu (Meta), Rayan Saab (University of California San Diego), and Rongrong Wang (Michigan State University).