Discrete Signal Processing with Set Functions
arXiv:2001.10290 · doi:10.1109/TSP.2020.3046972
Abstract
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.
arXiv comment16 pages, submitted for publication
References in corpus (15)
- Semi-Supervised Classification with Graph Convolutional Networks
- The Emerging Field of Signal Processing on Graphs: Extending High-Dimensional Data Analysis to Networks and Other Irregular Domains
- Geometric deep learning: going beyond Euclidean data
- Discrete Signal Processing on Graphs
- Discrete Signal Processing on Graphs: Sampling Theory
- Near-optimal Nonmyopic Value of Information in Graphical Models
- Topological Signal Processing over Simplicial Complexes
- Learning-based Compressive Subsampling
- Efficient Minimization of Decomposable Submodular Functions
- Precoder Design for Physical Layer Multicasting
- Near-Optimal Sparse Sensing for Gaussian Detection with Correlated Observations
- Discrete Signal Processing on Meet/Join Lattices
- Fourier Analysis-based Iterative Combinatorial Auctions
- Powerset Convolutional Neural Networks
- Submodular relaxation for inference in Markov random fields