Grant: Discovery Grants Program - Individual
University of British Columbia
$42,000.00
Entropy for Hidden Markov Processes and Markov Random Fields
EF 2016-17
Résumé
Stationary Markov processes are ubiquitous as tractable models of random phenomena. The simplest setting isthat of finite-state, discrete-time stationary Markov chains, which model one-dimensional random sequences.These processes are fairly well understood. In this project, we focus on two generalizations of this simplesetting: 1) stationary hidden Markov processes (HMP) and 2) stationary Markov random fields (MRF). Theformer models sequences generated by a Markov chain and observed in the presence of noise. The lattermodels random arrays in higher dimensions, either on a square or cubic lattice or some other kind of graphstructure. Both are indispensable for modeling random phenomena in applications ranging from speechrecognition to network communications. For both classes, we focus on the finite-state, discrete-time andstationary cases.One of the the most fundamental properties of a stationary process is its entropy, sometimes called entropy rate. Computation of entropy is an important first step in the design of codes for data compression or error correction. While there is a simple, closed-form expression for the entropy of a Markov chain, it is rare that the entropy of an HMP or MRF can be computed exactly. The hard square model is a classical example, for which computation of entropy has eluded a solution for decades. The main goals of this project are to further develop estimates and asymptotics of entropy for HMP's and MRF's and to solve related structural problemsfor such processes. We will extend our previous work on HMP's from discrete-valued to continuous-valued processes and will improve our earlier work on exponentially-fast approximations to entropyfor MRF's.
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
British Columbia, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data
Tel que publié
Application id
261611-2012
Name nom
Marcus, Brian
Department département
Mathematics
Organization id
2
Institution établissement
University of British Columbia
Province en
British Columbia
Province fr
Colombie-Britannique
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2016
Competition year année de concours
2012
Award amount
42000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
1510
Committee name en
Electrical and Computer Engineering
Committee name fr
Génie électrique et informatique
Area of application code
1205
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Mathematical sciences
Area of application fr
Sciences mathématiques
Research subject code
2959
Research subject group en
Applied mathematics
Research subject group fr
Mathématiques appliquées
Research subject en
Mathematics of communications
Research subject fr
Mathématiques des télécommunications
Partie
5
Nb partie
5
Application title
Entropy for Hidden Markov Processes and Markov Random Fields
Keyword
NSERC
Application summary
Stationary Markov processes are ubiquitous as tractable models of random phenomena. The simplest setting isthat of finite-state, discrete-time stationary Markov chains, which model one-dimensional random sequences.These processes are fairly well understood. In this project, we focus on two generalizations of this simplesetting: 1) stationary hidden Markov processes (HMP) and 2) stationary Markov random fields (MRF). Theformer models sequences generated by a Markov chain and observed in the presence of noise. The lattermodels random arrays in higher dimensions, either on a square or cubic lattice or some other kind of graphstructure. Both are indispensable for modeling random phenomena in applications ranging from speechrecognition to network communications. For both classes, we focus on the finite-state, discrete-time andstationary cases.One of the the most fundamental properties of a stationary process is its entropy, sometimes called entropy rate. Computation of entropy is an important first step in the design of codes for data compression or error correction. While there is a simple, closed-form expression for the entropy of a Markov chain, it is rare that the entropy of an HMP or MRF can be computed exactly. The hard square model is a classical example, for which computation of entropy has eluded a solution for decades. The main goals of this project are to further develop estimates and asymptotics of entropy for HMP's and MRF's and to solve related structural problemsfor such processes. We will extend our previous work on HMP's from discrete-valued to continuous-valued processes and will improve our earlier work on exponentially-fast approximations to entropyfor MRF's.