Title :
Sample complexity of determining structures of graphical models
Author :
Santhanam, Narayana ; Wainwright, Martin J.
Author_Institution :
EECS Depts., UC Berkeley, Berkeley, CA
Abstract :
We consider discovering the graph structure of a pairwise Markov random field (MRF) on p binary random variables using n samples from the underlying MRF distribution. We analyze the information-theoretic limitations of this problem under high-dimensional scaling, when the number of connections of each variable in the underlying MRF is bounded by d.We derive both necessary and sufficient conditions on the scaling of the triplet (n, p, d) for asympotically reliable recovery of the graph structure.
Keywords :
Markov processes; graph theory; information theory; random processes; asympotically reliable reocovery; graph structure; graphical models; information-theoretic limitations; p binary random variables; pairwise Markov random field; Graphical models; Image analysis; Information analysis; Magnetic analysis; Markov random fields; Random variables; Social network services; Statistical distributions; Sufficient conditions; Tree graphs;
Conference_Titel :
Communication, Control, and Computing, 2008 46th Annual Allerton Conference on
Conference_Location :
Urbana-Champaign, IL
Print_ISBN :
978-1-4244-2925-7
Electronic_ISBN :
978-1-4244-2926-4
DOI :
10.1109/ALLERTON.2008.4797701
