Optimal detection and error exponents for hidden semi-Markov models

Dragana Bajović, Kanghang He, Lina Stanković, Dejan Vukobratović, Vladimir Stanković

Research output: Contribution to journalArticle

1 Citation (Scopus)

Abstract

We study detection of random signals corrupted by noise that over time switch their values (states) between a finite set of possible values, where the switchings occur at unknown points in time. We model such signals as hidden semi-Markov signals (HSMS), which generalize classical Markov chains by introducing explicit (possibly non-geometric) distribution for the time spent in each state. Assuming two possible signal states and Gaussian noise, we derive optimal likelihood ratio test and show that it has a computationally tractable form of a matrix product, with the number of matrices involved in the product being the number of process observations. The product matrices are independent and identically distributed, constructed by a simple measurement modulation of the sparse semi-Markov model transition matrix that we define in the paper. Using this result, we show that the Neyman-Pearson error exponent is equal to the top Lyapunov exponent for the corresponding random matrices. Using theory of large deviations, we derive a lower bound on the error exponent. Finally, we show that this bound is tight by means of numerical simulations.
LanguageEnglish
Pages1077-1092
Number of pages16
JournalIEEE Journal on Selected Topics in Signal Processing
Volume12
Issue number5
Early online date29 Jun 2018
DOIs
Publication statusPublished - 31 Oct 2018

Fingerprint

Time switches
Markov processes
Modulation
Computer simulation

Keywords

  • multi-state processes
  • hidden semi Markov models
  • explicit random duration
  • hypothesis testing
  • error exponent
  • large deviations principle
  • threshold effect
  • Lyapunov exponent

Cite this

@article{c4c41ce8cf6143a0904dd0576c8819ff,
title = "Optimal detection and error exponents for hidden semi-Markov models",
abstract = "We study detection of random signals corrupted by noise that over time switch their values (states) between a finite set of possible values, where the switchings occur at unknown points in time. We model such signals as hidden semi-Markov signals (HSMS), which generalize classical Markov chains by introducing explicit (possibly non-geometric) distribution for the time spent in each state. Assuming two possible signal states and Gaussian noise, we derive optimal likelihood ratio test and show that it has a computationally tractable form of a matrix product, with the number of matrices involved in the product being the number of process observations. The product matrices are independent and identically distributed, constructed by a simple measurement modulation of the sparse semi-Markov model transition matrix that we define in the paper. Using this result, we show that the Neyman-Pearson error exponent is equal to the top Lyapunov exponent for the corresponding random matrices. Using theory of large deviations, we derive a lower bound on the error exponent. Finally, we show that this bound is tight by means of numerical simulations.",
keywords = "multi-state processes, hidden semi Markov models, explicit random duration, hypothesis testing, error exponent, large deviations principle, threshold effect, Lyapunov exponent",
author = "Dragana Bajović and Kanghang He and Lina Stanković and Dejan Vukobratović and Vladimir Stanković",
year = "2018",
month = "10",
day = "31",
doi = "10.1109/JSTSP.2018.2851506",
language = "English",
volume = "12",
pages = "1077--1092",
journal = "IEEE Journal on Selected Topics in Signal Processing",
issn = "1932-4553",
number = "5",

}

Optimal detection and error exponents for hidden semi-Markov models. / Bajović, Dragana; He, Kanghang; Stanković, Lina; Vukobratović, Dejan; Stanković, Vladimir.

In: IEEE Journal on Selected Topics in Signal Processing, Vol. 12, No. 5, 31.10.2018, p. 1077-1092.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Optimal detection and error exponents for hidden semi-Markov models

AU - Bajović, Dragana

AU - He, Kanghang

AU - Stanković, Lina

AU - Vukobratović, Dejan

AU - Stanković, Vladimir

PY - 2018/10/31

Y1 - 2018/10/31

N2 - We study detection of random signals corrupted by noise that over time switch their values (states) between a finite set of possible values, where the switchings occur at unknown points in time. We model such signals as hidden semi-Markov signals (HSMS), which generalize classical Markov chains by introducing explicit (possibly non-geometric) distribution for the time spent in each state. Assuming two possible signal states and Gaussian noise, we derive optimal likelihood ratio test and show that it has a computationally tractable form of a matrix product, with the number of matrices involved in the product being the number of process observations. The product matrices are independent and identically distributed, constructed by a simple measurement modulation of the sparse semi-Markov model transition matrix that we define in the paper. Using this result, we show that the Neyman-Pearson error exponent is equal to the top Lyapunov exponent for the corresponding random matrices. Using theory of large deviations, we derive a lower bound on the error exponent. Finally, we show that this bound is tight by means of numerical simulations.

AB - We study detection of random signals corrupted by noise that over time switch their values (states) between a finite set of possible values, where the switchings occur at unknown points in time. We model such signals as hidden semi-Markov signals (HSMS), which generalize classical Markov chains by introducing explicit (possibly non-geometric) distribution for the time spent in each state. Assuming two possible signal states and Gaussian noise, we derive optimal likelihood ratio test and show that it has a computationally tractable form of a matrix product, with the number of matrices involved in the product being the number of process observations. The product matrices are independent and identically distributed, constructed by a simple measurement modulation of the sparse semi-Markov model transition matrix that we define in the paper. Using this result, we show that the Neyman-Pearson error exponent is equal to the top Lyapunov exponent for the corresponding random matrices. Using theory of large deviations, we derive a lower bound on the error exponent. Finally, we show that this bound is tight by means of numerical simulations.

KW - multi-state processes

KW - hidden semi Markov models

KW - explicit random duration

KW - hypothesis testing

KW - error exponent

KW - large deviations principle

KW - threshold effect

KW - Lyapunov exponent

U2 - 10.1109/JSTSP.2018.2851506

DO - 10.1109/JSTSP.2018.2851506

M3 - Article

VL - 12

SP - 1077

EP - 1092

JO - IEEE Journal on Selected Topics in Signal Processing

T2 - IEEE Journal on Selected Topics in Signal Processing

JF - IEEE Journal on Selected Topics in Signal Processing

SN - 1932-4553

IS - 5

ER -