Quickest detection of Markov networks

Javad Heydari, Ali Tajer, H. Vincent Poor

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations

Abstract

Detecting correlation structures in large networks arises in many domains. Such detection problems are often studied independently of the underlying data acquisition process, rendering settings in which data acquisition policies and the associated sample size are pre-specified. Motivated by the advantages of data-adaptive sampling in data dimensionality reduction, especially in large networks, as well as enhancing the agility of the sampling process, this paper treats the inherently problems of data acquisition and correlation detection. Specifically, this paper considers a network of nodes generating random variables and designs the quickest sequential sampling strategy for collecting data and reliably deciding whether the network is a Markov network with a known correlation structure. By abstracting the Markov network as an undirected graph, in which the vertices represent the random variables and their connectivities model the correlation structure of interest, designing the quickest sampling strategy becomes equivalent to sequentially and data-adaptively identifying and sampling a sequence of vertices in the graph. Optimal sampling strategies are proposed and their associated optimality guarantees are established. Performance evaluations are provided to demonstrate the gains of the proposed sequential approaches.

Original languageEnglish (US)
Title of host publicationProceedings - ISIT 2016; 2016 IEEE International Symposium on Information Theory
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages1341-1345
Number of pages5
ISBN (Electronic)9781509018062
DOIs
StatePublished - Aug 10 2016
Event2016 IEEE International Symposium on Information Theory, ISIT 2016 - Barcelona, Spain
Duration: Jul 10 2016Jul 15 2016

Publication series

NameIEEE International Symposium on Information Theory - Proceedings
Volume2016-August
ISSN (Print)2157-8095

Other

Other2016 IEEE International Symposium on Information Theory, ISIT 2016
CountrySpain
CityBarcelona
Period7/10/167/15/16

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Information Systems
  • Modeling and Simulation
  • Applied Mathematics

Keywords

  • Correlation detection
  • Markov network
  • quickest detection
  • sequential sampling

Fingerprint Dive into the research topics of 'Quickest detection of Markov networks'. Together they form a unique fingerprint.

  • Cite this

    Heydari, J., Tajer, A., & Poor, H. V. (2016). Quickest detection of Markov networks. In Proceedings - ISIT 2016; 2016 IEEE International Symposium on Information Theory (pp. 1341-1345). [7541517] (IEEE International Symposium on Information Theory - Proceedings; Vol. 2016-August). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ISIT.2016.7541517