University of Cambridge > > Signal Processing and Communications Lab Seminars > A local weak limit approach to the study of graphical data

A local weak limit approach to the study of graphical data

Add to your list(s) Download to your calendar using vCal

If you have a question about this talk, please contact Prof. Ramji Venkataramanan.

By graphical data, we mean data indexed by the vertices and edges of a sparse graph rather than by linearly ordered time. Just as a stochastic process is a stochastic model for a time series got by picking a time index at random and viewing how the time series looks from that time index, in the local weak limit theory one studies graphical data by picking a node of the graph at random and seeing how the data looks from the point of view of that node. What results is a so-called sofic distribution on rooted marked graphs.

Bordenave and Caputo (2014) defined a notion of entropy for probability distributions on rooted graphs with finite expected degree at the root. We call this BC entropy. We develop the parallel result for probability distributions on marked rooted graphs. Our graphs have vertex marks drawn from a finite set and directed edge marks, one towards each vertex, drawn from a finite set.

We develop the details of our generalization of BC entropy to the case of rooted marked graphs. We then illustrate the value of this viewpoint by proving a universal lossless data compression theorem analogous to the basic universal lossless data compression theorem for time series. We also prove, for graphical data, an analog of the Slepian-Wolf theorem of distributed compression for Erdos-Renyi and configuration model ensembles.

This is joint work with Payam Delgosha.

This talk is part of the Signal Processing and Communications Lab Seminars series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.


© 2006-2023, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity