TY - JOUR
T1 - Robust estimation of latent tree graphical models
T2 - Inferring hidden states with inexact parameters
AU - Mossel, Elchanan
AU - Roch, Sébastien
AU - Sly, Allan
PY - 2013/7
Y1 - 2013/7
N2 - Latent tree graphical models are widely used in computational biology, signal and image processing, and network tomography. Here, we design a new efficient, estimation procedure for latent tree models, including Gaussian and discrete, reversible models, that significantly improves on previous sample requirement bounds. Our techniques are based on a new hidden state estimator that is robust to inaccuracies in estimated parameters. More precisely, we prove that latent tree models can be estimated with high probability in the so-called Kesten-Stigum regime with O(log2n) samples, where n is the number of nodes.
AB - Latent tree graphical models are widely used in computational biology, signal and image processing, and network tomography. Here, we design a new efficient, estimation procedure for latent tree models, including Gaussian and discrete, reversible models, that significantly improves on previous sample requirement bounds. Our techniques are based on a new hidden state estimator that is robust to inaccuracies in estimated parameters. More precisely, we prove that latent tree models can be estimated with high probability in the so-called Kesten-Stigum regime with O(log2n) samples, where n is the number of nodes.
KW - Gaussian graphical models on trees
KW - Kesten-Stigum (KS) reconstruction bound
KW - Markov random fields on trees
KW - Phase transitions
UR - http://www.scopus.com/inward/record.url?scp=84897699286&partnerID=8YFLogxK
U2 - 10.1109/TIT.2013.2251927
DO - 10.1109/TIT.2013.2251927
M3 - Article
SN - 0018-9448
VL - 59
SP - 4357
EP - 4373
JO - IEEE Transactions on Information Theory
JF - IEEE Transactions on Information Theory
IS - 7
M1 - 6476722
ER -