Robust directed tree approximations for networks of stochastic processes

Christopher J. Quinn; Jalal Etesami; Negar Kiyavash; Todd P. Coleman

doi:10.1109/ISIT.2013.6620627

Robust directed tree approximations for networks of stochastic processes

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

Industrial and Enterprise Systems Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

We develop low-complexity algorithms to robustly identify the best directed tree approximation for a network of stochastic processes in the finite-sample regime. Directed information is used to quantify influence between stochastic processes and identify the best directed tree approximation in terms of Kullback-Leibler (KL) divergence. We provide finite-sample complexity bounds for confidence intervals of directed information estimates. We use these confidence intervals to develop a minimax framework to identify the best directed tree that is robust to point estimation errors. We provide algorithms for this minimax calculation and describe the relationships between exactness and complexity.

Original language	English (US)
Title of host publication	2013 IEEE International Symposium on Information Theory, ISIT 2013
Pages	2254-2258
Number of pages	5
DOIs	https://doi.org/10.1109/ISIT.2013.6620627
State	Published - Dec 19 2013
Event	2013 IEEE International Symposium on Information Theory, ISIT 2013 - Istanbul, Turkey Duration: Jul 7 2013 → Jul 12 2013

Publication series

Name	IEEE International Symposium on Information Theory - Proceedings
ISSN (Print)	2157-8095

Other

Other	2013 IEEE International Symposium on Information Theory, ISIT 2013
Country/Territory	Turkey
City	Istanbul
Period	7/7/13 → 7/12/13

ASJC Scopus subject areas

Theoretical Computer Science
Information Systems
Modeling and Simulation
Applied Mathematics

Online availability

10.1109/ISIT.2013.6620627

Library availability

Discover UIUC Full Text

Cite this

Robust directed tree approximations for networks of stochastic processes. / Quinn, Christopher J.; Etesami, Jalal; Kiyavash, Negar et al.
2013 IEEE International Symposium on Information Theory, ISIT 2013. 2013. p. 2254-2258 6620627 (IEEE International Symposium on Information Theory - Proceedings).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Quinn, CJ, Etesami, J, Kiyavash, N & Coleman, TP 2013, Robust directed tree approximations for networks of stochastic processes. in 2013 IEEE International Symposium on Information Theory, ISIT 2013., 6620627, IEEE International Symposium on Information Theory - Proceedings, pp. 2254-2258, 2013 IEEE International Symposium on Information Theory, ISIT 2013, Istanbul, Turkey, 7/7/13. https://doi.org/10.1109/ISIT.2013.6620627

@inproceedings{4d117871cbde4d58a4e05adb1932aa3b,

title = "Robust directed tree approximations for networks of stochastic processes",

abstract = "We develop low-complexity algorithms to robustly identify the best directed tree approximation for a network of stochastic processes in the finite-sample regime. Directed information is used to quantify influence between stochastic processes and identify the best directed tree approximation in terms of Kullback-Leibler (KL) divergence. We provide finite-sample complexity bounds for confidence intervals of directed information estimates. We use these confidence intervals to develop a minimax framework to identify the best directed tree that is robust to point estimation errors. We provide algorithms for this minimax calculation and describe the relationships between exactness and complexity.",

author = "Quinn, {Christopher J.} and Jalal Etesami and Negar Kiyavash and Coleman, {Todd P.}",

year = "2013",

month = dec,

day = "19",

doi = "10.1109/ISIT.2013.6620627",

language = "English (US)",

isbn = "9781479904464",

series = "IEEE International Symposium on Information Theory - Proceedings",

pages = "2254--2258",

booktitle = "2013 IEEE International Symposium on Information Theory, ISIT 2013",

note = "2013 IEEE International Symposium on Information Theory, ISIT 2013 ; Conference date: 07-07-2013 Through 12-07-2013",

}

TY - GEN

T1 - Robust directed tree approximations for networks of stochastic processes

AU - Quinn, Christopher J.

AU - Etesami, Jalal

AU - Kiyavash, Negar

AU - Coleman, Todd P.

PY - 2013/12/19

Y1 - 2013/12/19

N2 - We develop low-complexity algorithms to robustly identify the best directed tree approximation for a network of stochastic processes in the finite-sample regime. Directed information is used to quantify influence between stochastic processes and identify the best directed tree approximation in terms of Kullback-Leibler (KL) divergence. We provide finite-sample complexity bounds for confidence intervals of directed information estimates. We use these confidence intervals to develop a minimax framework to identify the best directed tree that is robust to point estimation errors. We provide algorithms for this minimax calculation and describe the relationships between exactness and complexity.

AB - We develop low-complexity algorithms to robustly identify the best directed tree approximation for a network of stochastic processes in the finite-sample regime. Directed information is used to quantify influence between stochastic processes and identify the best directed tree approximation in terms of Kullback-Leibler (KL) divergence. We provide finite-sample complexity bounds for confidence intervals of directed information estimates. We use these confidence intervals to develop a minimax framework to identify the best directed tree that is robust to point estimation errors. We provide algorithms for this minimax calculation and describe the relationships between exactness and complexity.

UR - http://www.scopus.com/inward/record.url?scp=84890354228&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84890354228&partnerID=8YFLogxK

U2 - 10.1109/ISIT.2013.6620627

DO - 10.1109/ISIT.2013.6620627

M3 - Conference contribution

AN - SCOPUS:84890354228

SN - 9781479904464

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 2254

EP - 2258

BT - 2013 IEEE International Symposium on Information Theory, ISIT 2013

T2 - 2013 IEEE International Symposium on Information Theory, ISIT 2013

Y2 - 7 July 2013 through 12 July 2013

ER -

Robust directed tree approximations for networks of stochastic processes

Abstract

Publication series

Other

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this