• DocumentCode
    2947552
  • Title

    Sample complexity of determining structures of graphical models

  • Author

    Santhanam, Narayana ; Wainwright, Martin J.

  • Author_Institution
    EECS Depts., UC Berkeley, Berkeley, CA
  • fYear
    2008
  • fDate
    23-26 Sept. 2008
  • Firstpage
    1232
  • Lastpage
    1237
  • 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;
  • fLanguage
    English
  • Publisher
    ieee
  • 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
  • Type

    conf

  • DOI
    10.1109/ALLERTON.2008.4797701
  • Filename
    4797701
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=2947552