A Discrete Signal Processing Framework for Set Functions

摘要

A set function associates a real (or complex) value with every subset of a given finite set S. In this paper, we derive a novel discrete signal processing (DSP) framework for such functions. This means we define and derive suitable notions of basic DSP concepts including shift, filtering, frequency response, Fourier transform, and convolution theorems. At the heart is the definition of the shift on subsets for which we consider the two most natural choices, i.e., those most analogous to the time shift in standard DSP. Set functions naturally occur in many contexts associated with probability distributions, graph cuts, sensor placements, mutual information, entropy of sets of random variables, and others. Our work offers a new set of tools for their processing.