Discrete Signal Processing with Set Functions
  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.
