Efficient methods to compute optimal tree approximations of directed information graphs

Christopher J. Quinn, Negar Kiyavash, Todd P. Coleman

Research output: Contribution to journalArticlepeer-review

Abstract

Recently, directed information graphs have been proposed as concise graphical representations of the statistical dynamics among multiple random processes. A directed edge from one node to another indicates that the past of one random process statistically affects the future of another, given the past of all other processes. When the number of processes is large, computing those conditional dependence tests becomes difficult. Also, when the number of interactions becomes too large, the graph no longer facilitates visual extraction of relevant information for decision-making. This work considers approximating the true joint distribution on multiple random processes by another, whose directed information graph has at most one parent for any node. Under a Kullback-Leibler (KL) divergence minimization criterion, we show that the optimal approximate joint distribution can be obtained by maximizing a sum of directed informations. In particular, each directed information calculation only involves statistics among a pair of processes and can be efficiently estimated and given all pairwise directed informations, an efficient minimum weight spanning directed tree algorithm can be solved to find the best tree. We demonstrate the efficacy of this approach using simulated and experimental data. In both, the approximations preserve the relevant information for decision-making.

Original languageEnglish (US)
Article number6506113
Pages (from-to)3173-3182
Number of pages10
JournalIEEE Transactions on Signal Processing
Volume61
Issue number12
DOIs
StatePublished - Jun 3 2013

Keywords

  • Directed trees
  • graphical models
  • network approximations

ASJC Scopus subject areas

  • Signal Processing
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'Efficient methods to compute optimal tree approximations of directed information graphs'. Together they form a unique fingerprint.

Cite this