Discrete Signal Processing on Meet/Join Lattices
arXiv:2012.04358 · doi:10.1109/TSP.2021.3081036
Abstract
A lattice is a partially ordered set supporting a meet (or join) operation that returns the largest lower bound (smallest upper bound) of two elements. Just like graphs, lattices are a fundamental structure that occurs across domains including social data analysis, natural language processing, computational chemistry and biology, and database theory. In this paper we introduce discrete-lattice signal processing (DLSP), an SP framework for data, or signals, indexed by such lattices. We use the meet (or join) to define a shift operation and derive associated notions of filtering, Fourier basis and transform, and frequency response. We show that the spectrum of a lattice signal inherits the lattice structure of the signal domain and derive a sampling theorem. Finally, we show two prototypical applications: spectral analysis of formal concept lattices in social science and sampling and Wiener filtering of multiset lattices in combinatorial auctions. Formal concept lattices are a compressed representation of relations between objects and attributes. Since relations are equivalent to bipartite graphs and hypergraphs, DLSP offers a form of Fourier analysis for these structures.
arXiv comment13 pages
References in corpus (12)
- 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
- Efficient Sampling Set Selection for Bandlimited Graph Signals Using Graph Spectral Proxies
- Topological Signal Processing over Simplicial Complexes
- Introducing Hypergraph Signal Processing: Theoretical Foundation and Practical Applications
- Graphon Signal Processing
- Discrete Signal Processing with Set Functions
- Deep Learning-powered Iterative Combinatorial Auctions
- Fourier Analysis-based Iterative Combinatorial Auctions
- Quiver Signal Processing (QSP)
- Multidimensional Persistence Module Classification via Lattice-Theoretic Convolutions