Journal
IEEE TRANSACTIONS ON INFORMATION THEORY
Volume 58, Issue 7, Pages 4117-4134Publisher
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TIT.2012.2191659
Keywords
High dimensional inference; KL divergence between Ising models; Markov random fields; sample complexity; structure of Ising models
Funding
- National Science Foundation [CAREER-0545862, DMS-0528488]
- University of Hawaii, Honolulu
Ask authors/readers for more resources
The problem of graphical model selection is to estimate the graph structure of a Markov random field given samples from it. We analyze the information-theoretic limitations of the problem of graph selection for binary Markov random fields under high-dimensional scaling, in which the graph size and the number of edges k, and/or the maximal node degree d, are allowed to increase to infinity as a function of the sample size n. For pairwise binary Markov random fields, we derive both necessary and sufficient conditions for correct graph selection over the class G(p,k) of graphs on p vertices with at most k edges, and over the class G(p,d) of graphs on p vertices with maximum degree at most. For the class , we establish the existence of constants and such that if, any method has error probability at least uniformly over the family, and we demonstrate a graph decoder that succeeds with high probability uniformly over the family for sample sizes n > c(1)k(2) log p. Similarly, for the class G(p,d), we exhibit constants and such that for n < cd(2) log p, anymethod fails with probability at least 1/2, and we demonstrate a graph decoder that succeeds with high probability for n > c(1) d(3) log p.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available