Robust estimation of latent tree graphical models: Inferring hidden states with inexact parameters

Elchanan Mossel, Sébastien Roch, Allan Sly

Research output: Contribution to journalArticle

6 Scopus citations

Abstract

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.

Original languageEnglish (US)
Article number6476722
Pages (from-to)4357-4373
Number of pages17
JournalIEEE Transactions on Information Theory
Volume59
Issue number7
DOIs
StatePublished - Jul 2013

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences

Keywords

  • Gaussian graphical models on trees
  • Kesten-Stigum (KS) reconstruction bound
  • Markov random fields on trees
  • Phase transitions

Fingerprint Dive into the research topics of 'Robust estimation of latent tree graphical models: Inferring hidden states with inexact parameters'. Together they form a unique fingerprint.

  • Cite this