# Discrete Signal Processing with Set Functions

arXiv: https://arxiv.org/abs/2001.10290 · HTML: https://mlsanity.com/paper/2001.10290/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Jan 2020.

## Built on by (most cited first, 8 of 8)

- [Causal Fourier Analysis on Directed Acyclic Graphs and Posets](https://mlsanity.com/paper/2209.07970/) (2022)
- [Learning with Multigraph Convolutional Filters](https://mlsanity.com/paper/2210.16272/) (2022)
- [Convolutional Filtering with RKHS Algebras](https://mlsanity.com/paper/2411.01341/) (2024)
- [Advances in Set Function Learning: A Survey of Techniques and Applications](https://mlsanity.com/paper/2501.14991/) (2025)
- [Submodular Maximization Approaches for Equitable Client Selection in Federated Learning](https://mlsanity.com/paper/2408.13683/) (2024)
- [RKHS Representation of Algebraic Convolutional Filters with Integral Operators](https://mlsanity.com/paper/2602.19094/) (2026)
- [Non Commutative Convolutional Signal Models in Neural Networks: Stability to Small Deformations](https://mlsanity.com/paper/2310.03879/) (2023)
- [Fundamental Limits of Transferability and Equivariance in Algebraic Signal Models I: Finite Dimensions](https://mlsanity.com/paper/2609.36106/) (2026)

## Abstract (arXiv)

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.