A local weak limit approach to the study of graphical data

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

• Prof. Venkat Anantharam, University of California, Berkeley
• Tuesday 21 May 2019, 15:00-16:00
• LT6, Baker Building, CUED.

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.

This talk is included in these lists:

• All Talks (aka the CURE list)
• Cambridge Centre for Data-Driven Discovery (C2D3)
• Cambridge University Engineering Department Talks
• Cambridge talks
• Centre for Smart Infrastructure & Construction
• Chris Davis' list
• Computational Continuum Mechanics Group Seminars
• Featured lists
• Information Engineering Division seminar list
• Interested Talks
• LT6, Baker Building, CUED
• School of Technology
• Signal Processing and Communications Lab Seminars
• Trust & Technology Initiative - interesting events
• bld31
• ndk22's list
• ob366-ai4er
• rp587

Note that ex-directory lists are not shown.