Controlling the Number of Sample-Contributive Vertices in Generalized Sampling of Graph Signals

This paper proposes a method for sampling graph signals by designing a flexible sampling operator via a difference-of-convex (DC) based algorithm. Departing from conventional methods limited to bandlimited signals, our method extend the generalized sampling theory to handle graph signals beyond bandlimitedness. Our method aims to design a flexible sampling operator that mixes vertex values, while controlling the number of sample-contributive vertices. The operator design is formulated as a feasibility problem with an invertibility constraint for the best possible recovery and a constraint controlling the number of sample-contributive vertices. We reformulate the problem as a DC-like optimization problem by using the nuclear norm to obtain a tight relaxation of the invertibility constraint. To solve this problem, we present a DC-based algorithm. The effectiveness of our approach is demonstrated through sampling and recovery experiments on various graph signal models.