Discrete Signal Processing with Set Functions
This work provides new tools for analyzing set functions, addressing their exponential complexity, which is a problem for researchers and practitioners in optimization and machine learning, though it appears incremental as it builds on existing signal processing concepts.
The paper tackles the challenge of processing set functions, which are fundamental in various domains like image segmentation and game theory, by introducing discrete-set signal processing, a novel shift-invariant linear framework. It demonstrates applications in compressing submodular functions and sampling for preference elicitation, showing practical utility.
Set functions are functions (or signals) indexed by the powerset (set of all subsets) of a finite set N. They are fundamental and ubiquitous in many application domains and have been used, for example, to formally describe or quantify loss functions for semantic image segmentation, the informativeness of sensors in sensor networks the utility of sets of items in recommender systems, cooperative games in game theory, or bidders in combinatorial auctions. In particular, the subclass of submodular functions occurs in many optimization and machine learning problems. In this paper, we derive discrete-set signal processing (SP), a novel shift-invariant linear signal processing framework for set functions. Discrete-set SP considers different notions of shift obtained from set union and difference operations. For each shift it provides associated notions of shift-invariant filters, convolution, Fourier transform, and frequency response. We provide intuition for our framework using the concept of generalized coverage function that we define, identify multivariate mutual information as a special case of a discrete-set spectrum, and motivate frequency ordering. Our work brings a new set of tools for analyzing and processing set functions, and, in particular, for dealing with their exponential nature. We show two prototypical applications and experiments: compression in submodular function optimization and sampling for preference elicitation in combinatorial auctions.