Sorry, you need to enable JavaScript to visit this website.

facebooktwittermailshare

Sampling Signals on Meet/Join Lattices

Abstract: 

We present a novel sampling theorem, and prototypical applications, for Fourier-sparse lattice signals, i.e., data indexed by a finite semi-lattice. A semilattice is a partially ordered set endowed with a meet (or join) operation that returns the greatest lower bound (smallest upper bound) of two elements. Semilattices can be viewed as a special class of directed graphs with a strictly triangular adjacency matrix , which thus cannot be diagonalized. Our work does not build on prior graph signal processing (GSP) frameworks but on the recently introduced discrete-lattice signal processing (DLSP), which uses the meet as shift operator to derive convolution and Fourier transform. DLSP is fundamentally different from GSP in that it requires several generating shifts that capture the partial-order-rather than the adjacency-structure, and a diagonalizing Fourier transform is always guaranteed by algebraic lattice theory. We apply and demonstrate the utility of our novel sampling scheme in three real-world settings from computational biology, document representation, and auction design.

up
0 users have voted:

Paper Details

Authors:
Markus Püschel
Submitted On:
15 November 2019 - 12:58pm
Short Link:
Type:
Presentation Slides
Event:
Presenter's Name:
Chris Wendler
Document Year:
2019
Cite

Document Files

globalsip2019-dlsp-sampling.pdf

(22)

globalsip2019-dlsp-sampling.pdf

(16)

Subscribe

[1] Markus Püschel, "Sampling Signals on Meet/Join Lattices", IEEE SigPort, 2019. [Online]. Available: http://sigport.org/4951. Accessed: Dec. 12, 2019.
@article{4951-19,
url = {http://sigport.org/4951},
author = {Markus Püschel },
publisher = {IEEE SigPort},
title = {Sampling Signals on Meet/Join Lattices},
year = {2019} }
TY - EJOUR
T1 - Sampling Signals on Meet/Join Lattices
AU - Markus Püschel
PY - 2019
PB - IEEE SigPort
UR - http://sigport.org/4951
ER -
Markus Püschel. (2019). Sampling Signals on Meet/Join Lattices. IEEE SigPort. http://sigport.org/4951
Markus Püschel, 2019. Sampling Signals on Meet/Join Lattices. Available at: http://sigport.org/4951.
Markus Püschel. (2019). "Sampling Signals on Meet/Join Lattices." Web.
1. Markus Püschel. Sampling Signals on Meet/Join Lattices [Internet]. IEEE SigPort; 2019. Available from : http://sigport.org/4951