Generalized Graph Signal Sampling by Difference-of-Convex Optimization

We propose a comprehensive framework for the generalized sampling and recovery of generalized graph signals by leveraging difference-of-convex (DC) optimization. A fundamental challenge in graph signal processing is sampling, especially for graph signals that are not bandlimited. To accurately capture complex real-world phenomena, it is essential to handle beyond bandlimited graph signals, moving past traditional bandlimited assumptions. Consequently, extending the generalized sampling theory to graph signals has been studied, enabling the best possible recovery for a wide range of signals by assuming signal priors. However, achieving the best possible recovery requires handling inherently non-convex and computationally intractable constraints such as full rank constraint. As a result, existing methods have relied on either aggressive convex relaxations that sacrifice accuracy or greedy algorithms that risk falling into poor suboptimal solutions, facing a fundamental dilemma between modeling accuracy and optimization tractability. To overcome this dilemma, we propose a DC optimization-based method for designing an aggregation sampling operator for beyond bandlimited graph signals that comprehensively handles arbitrary signal priors assumed in the generalized sampling theory. Specifically, the intractable full rank constraint is tightly relaxed using the nuclear norm, reformulating the design problem into a DC optimization problem. We developed a solver based on the general double-proximal gradient DC algorithm, which theoretically guarantees convergence to a critical point. Experimental results on synthetic and real-world data demonstrate the superiority of our method in sampling and recovering beyond bandlimited graph signals compared to existing approaches.