An improvement to the interacting multiple model (IMM) algorithm

Computing the optimal conditional mean state estimate for a jump Markov linear system requires exponential complexity, and hence, practical filtering algorithms are necessarily suboptimal. In the target tracking literature, suboptimal multiple-model filtering algorithms, such as the interacting multiple model (IMM) method and generalized pseudo-Bayesian (GPB) schemes, are widely used for state estimation of such systems. We derive a reweighted interacting multiple model algorithm. Although the IMM algorithm is an approximation of the conditional mean state estimator, our algorithm is a recursive implementation of a maximum a posteriori (MAP) state sequence estimator. This MAP estimator is an instance of a previous version of the EM algorithm known as the alternating expectation conditional maximization (AECM) algorithm. Computer simulations indicate that the proposed reweighted IMM algorithm is a competitive alternative to the popular IMM algorithm and GPB methods     

Iterative algorithms for state estimation of jump Markov linearsystems

Jump Markov linear systems (JMLSs) are linear systems whose parameters evolve with time according to a finite state Markov chain. Given a set of observations, our aim is to estimate the states of the finite state Markov chain and the continuous (in space) states of the linear system. In this paper, we present original deterministic and stochastic iterative algorithms for optimal state estimation of JMLSs. The first stochastic algorithm yields minimum mean square error (MMSE) estimates of the finite state space Markov chain and of the continuous state of the JMLS. A deterministic and a stochastic algorithm are given to obtain the marginal maximum a posteriori (MMAP) sequence estimate of the finite state Markov chain. Finally, a deterministic and a stochastic algorithm are derived to obtain the MMAP sequence estimate of the continuous state of the JMLS. Computer simulations are carried out to evaluate the performance of the proposed algorithms. The problem of deconvolution of Bernoulli-Gaussian (BG) processes and the problem of tracking a maneuvering target are addressed     

Simulated annealing for maximum a posteriori parameter estimationof hidden Markov models

Hidden Markov models are mixture models in which the populations from one observation to the next are selected according to an unobserved finite state-space Markov chain. Given a realization of the observation process, our aim is to estimate both the parameters of the Markov chain and of the mixture model in a Bayesian framework. We present an original simulated annealing algorithm which, in the same way as the EM (expectation-maximization) algorithm, relies on data augmentation, and is based on stochastic simulation of the hidden Markov chain. This algorithm is shown to converge toward the set of maximum a posteriori (MAP) parameters under suitable regularity conditions     

Particle filters for state estimation of jump Markov linear systems

Jump Markov linear systems (JMLS) are linear systems whose parameters evolve with time according to a finite state Markov chain. In this paper, our aim is to recursively compute optimal state estimates for this class of systems. We present efficient simulation-based algorithms called particle filters to solve the optimal filtering problem as well as the optimal fixed-lag smoothing problem. Our algorithms combine sequential importance sampling, a selection scheme, and Markov chain Monte Carlo methods. They use several variance reduction methods to make the most of the statistical structure of JMLS. Computer simulations are carried out to evaluate the performance of the proposed algorithms. The problems of on-line deconvolution of impulsive processes and of tracking a maneuvering target are considered. It is shown that our algorithms outperform the current methods     

On-line estimation of hidden Markov model parameters based on theKullback-Leibler information measure

Sequential or online hidden Markov model (HMM) signal processing schemes are derived, and their performance is illustrated by simulation. The online algorithms are sequential expectation maximization (EM) schemes and are derived by using stochastic approximations to maximize the Kullback-Leibler information measure. The schemes can be implemented either as filters or fixed-lag or sawtooth-lag smoothers. They yield estimates of the HMM parameters including transition probabilities, Markov state levels, and noise variance. In contrast to the offline EM algorithm (Baum-Welch scheme), which uses the fixed-interval forward-backward scheme, the online schemes have significantly reduced memory requirements and improved convergence, and they can estimate HMM parameters that vary slowly with time or undergo infrequent jump changes. Similar techniques are used to derive online schemes for extracting finite-state Markov chains imbedded in a mixture of white Gaussian noise (WGN) and deterministic signals of known functional form with unknown parameters     

Online Bayesian estimation of transition probabilities for Markovian jump systems

Markovian jump systems (MJSs) evolve in a jump-wise manner by switching among simpler models, according to a finite Markov chain, whose parameters are commonly assumed known. This paper addresses the problem of state estimation of MJS with unknown transition probability matrix (TPM) of the embedded Markov chain governing the jumps. Under the assumption of a time-invariant but random TPM, an approximate recursion for the TPMs posterior probability density function (PDF) within the Bayesian framework is obtained. Based on this recursion, four algorithms for online minimum mean-square error (MMSE) estimation of the TPM are derived. The first algorithm (for the case of a two-state Markov chain) computes the MMSE estimate exactly, if the likelihood of the TPM is linear in the transition probabilities. Its computational load is, however, increasing with the data length. To limit the computational cost, three alternative algorithms are further developed based on different approximation techniques-truncation of high order moments, quasi-Bayesian approximation, and numerical integration, respectively. The proposed TPM estimation is naturally incorporable into a typical online Bayesian estimation scheme for MJS [e.g., generalized pseudo-Bayesian (GPB) or interacting multiple model (IMM)]. Thus, adaptive versions of MJS state estimators with unknown TPM are provided. Simulation results of TPM-adaptive IMM algorithms for a system with failures and maneuvering target tracking are presented.     

Time-delay estimation for filtered Poisson processes using anEM-type algorithm

We develop a modified EM algorithm to estimate a nonrandom time shift parameter of an intensity associated with an inhomogeneous Poisson process N_t, whose points are only partially observed as a noise-contaminated output X of a linear time-invariant filter excited by a train of delta functions, a filtered Poisson process. The exact EM algorithm for computing the maximum likelihood time shift estimate generates a sequence of estimates each of which attempt to maximize a measure of similarity between the assumed shifted intensity and the conditional mean estimate of the Poisson increment dN_t. We modify the EM algorithm by using a linear approximation to this conditional mean estimate. The asymptotic performance of the modified EM algorithm is investigated by an asymptotic estimator consistency analysis. We present simulation results that show that the linearized EM algorithm converges rapidly and achieves an improvement over conventional time-delay estimation methods, such as linear matched filtering and leading edge thresholding. In these simulations our algorithm gives estimates of time delay whose mean square error virtually achieves the CR lower bound for high count rates     

Sequence detection and channel state estimation over finite stateMarkov channels

A useful model for general time-varying channels is a finite state Markov chain. In this paper, maximum likelihood sequence estimation (MLSE) for signals over finite state Markov channels (FSMCs) is studied. Also studied is the maximum a posteriori (MAP) channel state estimation. When coded signals with interleaving are transmitted, the channel estimates can be used to make soft-decision decoding. The error performance of the proposed sequence and channel state estimation schemes are evaluated through computer simulations. The effect of channel modeling error is also discussed     

Blind equalization of IIR channels using hidden Markov models andextended least squares

In this paper, we present a blind equalization algorithm for noisy IIR channels when the channel input is a finite state Markov chain. The algorithm yields estimates of the IIR channel coefficients, channel noise variance, transition probabilities, and state of the Markov chain. Unlike the optimal maximum likelihood estimator which is computationally infeasible since the computing cost increases exponentially with data length, our algorithm is computationally inexpensive. Our algorithm is based on combining a recursive hidden Markov model (HMM) estimator with a relaxed SPR (strictly positive real) extended least squares (ELS) scheme. In simulation studies we show that the algorithm yields satisfactory estimates even in low SNR. We also compare the performance of our scheme with a truncated FIR scheme and the constant modulus algorithm (CMA) which is currently a popular algorithm in blind equalization     

Bayesian decision feedback for segmentation of binary images

We present real-time algorithms for the segmentation of binary images modeled by Markov mesh random fields (MMRFs) and corrupted by independent noise. The goal is to find a recursive algorithm to compute the maximum a posteriori (MAP) estimate of each pixel of the scene using a fixed lookahead of D rows and D columns of the observations. First, this MAP fixed-lag estimation problem is set up and the corresponding optimal recursive (but computationally complex) estimator is derived. Then, both hard and soft (conditional) decision feedbacks are introduced at appropriate stages of the optimal estimator to reduce the complexity. The algorithm is applied to several synthetic and real images. The results demonstrate the viability of the algorithm both complexity-wise and performance-wise, and show its subjective relevance to the image segmentation problem.     

A novel truncated approximation based algorithm for state estimation of discrete-time Markov jump linear systems

In this paper, state estimation problem for discrete-time Markov jump linear systems is considered. First, three equalities are proposed. Next, they are applied to the state estimation problem of considered systems so that a novel suboptimal algorithm in the sense of minimum mean-square error estimate is obtained where the computation and storage load of the suboptimal algorithm is not ever-increasing with the length of the noise observation sequence. The proposed algorithm and the suboptimal adaptive algorithm proposed in [1] are all based on a truncated approximation strategy. However, compared with the algorithm of [1], the proposed algorithm requires much less approximations. Computer simulations are carried out to evaluate the performance of the proposed algorithm.     

基于马尔科夫链的灰狼优化算法收敛性研究

针对灰狼优化算法（Grey Wolf Optimization,GWO）在收敛性研究上的不足,首先,通过定义灰狼群状态转移序列,建立了GWO算法的马尔科夫（Markov）链模型,通过分析Markov链的性质,证明它是有限齐次 Markov链;其次,通过分析灰狼群状态序列最终转移状态,结合随机搜索算法的收敛准则,验证了GWO算法的全局收敛性;最后,对典型测试函数、偏移函数及旋转函数进行仿真实验,并与多种群体智能算法进行对比分析.实验结果表明,GWO算法具有全局收敛性强、计算耗时短和寻优精度高等优势.     

Structured Threshold Policies for Dynamic Sensor Scheduling—A Partially Observed Markov Decision Process Approach

We consider the optimal sensor scheduling problem formulated as a partially observed Markov decision process (POMDP). Due to operational constraints, at each time instant, the scheduler can dynamically select one out of a finite number of sensors and record a noisy measurement of an underlying Markov chain. The aim is to compute the optimal measurement scheduling policy, so as to minimize a cost function comprising of estimation errors and measurement costs. The formulation results in a nonstandard POMDP that is nonlinear in the information state. We give sufficient conditions on the cost function, dynamics of the Markov chain and observation probabilities so that the optimal scheduling policy has a threshold structure with respect to a monotone likelihood ratio (MLR) ordering. As a result, the computational complexity of implementing the optimal scheduling policy is inexpensive. We then present stochastic approximation algorithms for estimating the best linear MLR order threshold policy.     

Contributions to the application of the Viterbi algorithm

The Viterbi algorithm is an efficient technique to estimate the state sequence of a discrete-time finite-state Markov process in the presence of memoryless noise. This work sets up a relationship to a general class of linear and nonlinear fast algorithms such as FFT, FWT, and optimal sorting. The performance of a Viterbi detector is a function of the minimum distance between signals in the observation space of the estimated Markov process. It is shown that this distance may efficiently be calculated with dynamic programming using a slightly modified Viterbi algorithm of an increased basis.     

Finite dimensional smoothers for MAP state estimation of bilinearsystems

In this paper, we present two finite-dimensional iterative algorithms for maximum a posteriori (MAP) state sequence estimation of bilinear systems. Bilinear models are appealing in their ability to represent or approximate a broad class of nonlinear systems. Our iterative algorithms for state estimation are based on the expectation-maximization (EM) algorithm and outperform the widely used extended Kalman smoother (EKS). Unlike the EKS, these EM algorithms are optimal (in the MAP sense) finite-dimensional solutions to the state sequence estimation problem for bilinear models. We also present recursive (on-line) versions of the two algorithms and show that they outperform the extended Kalman filter (EKF). Our main conclusion is that the EM-based algorithms presented in this paper are novel nonlinear filtering methods that perform better than traditional methods such as the EKF     

Adaptive nonlinear filters for narrow-band interference suppressionin spread-spectrum CDMA systems

This paper presents a novel nonlinear filter and parameter estimator for narrow band interference suppression in code division multiple access spread-spectrum systems. As in the article by Rusch and Poor (1994), the received sampled signal is modeled as the sum of the spread-spectrum signal (modeled as a finite state independently identically distributed (i.i.d.) process-here we generalize to a finite state Markov chain), narrow-band interference (modeled as a Gaussian autoregressive process), and observation noise (modeled as a zero-mean white Gaussian process). The proposed algorithm combines a recursive hidden Markov model (HMM) estimator, Kalman filter (KF), and the recursive expectation maximization algorithm. The nonlinear filtering techniques for narrow-band interference suppression presented in Rusch and Poor and our proposed HMM-KF algorithm have the same computational cost. Detailed simulation studies show that the HMM-KF algorithm outperforms the filtering techniques in Rusch and Poor. In particular, significant improvements in the bit error rate and signal-to-noise ratio (SNR) enhancement are obtained in low to medium SNR. Furthermore, in simulation studies we investigate the effect on the performance of the HMM-KF and the approximate conditional mean (ACM) filter in the paper by Rusch and Poor, when the observation noise variance is increased. As expected, the performance of the HMM-KF and ACM algorithms worsen with increasing observation noise and number of users. However, HMM-KF significantly outperforms ACM in medium to high observation noise     

On the unnormalized solution of the filtering problem with countingprocess observations

A general procedure to solve filtering problems for counting process observations is discussed. Linear (nonstochastic, integro-differential) equations describe the evolution of unnormalized conditional distribution of the state process between observation jump times, while at jump times a linear updating is required. Final normalization is the only nonlinear operation to be implemented. Quite general situations may be accommodated in the present setup; the state can be virtually any Markov semimartingale, the observation process may affect the dynamics of the state and vice versa, and there is complete freedom in correlating state and observation martingale terms     

Hidden Gauss-Markov models for signal classification

Continuous-state hidden Markov models (CS-HMMs) are developed as a tool for signal classification. Analogs of the Baum (1972), Viterbi (1962), and Baum-Welch algorithms are formulated for this class of models. The CS-HMM algorithms are then specialized to hidden Gauss-Markov models (HGMMs) with linear Gaussian state-transition and output densities. A new Gaussian refactorization lemma is used to show that the Baum and Viterbi algorithms for HGMMs are implemented by two different formulations of the fixed-interval Kalman smoother. The measurement likelihoods obtained from the forward pass of the HGMM Baum algorithm and from the Kalman-filter innovation sequence are shown to be equal. A direct link between the Baum-Welch training algorithm and an existing expectation-maximization (EM) algorithm for Gaussian models is demonstrated. A new expression for the cross covariance between time-adjacent states in HGMMs is derived from the off-diagonal block of the conditional joint covariance matrix. A parameter invariance structure is noted for the HGMM likelihood function. CS-HMMs and HGMMs are extended to incorporate mixture densities for the a priori density of the initial state. Application of HGMMs to signal classification is demonstrated with a three-class test simulation     

Time discretization of continuous-time filters and smoothers forHMM parameter estimation

In this paper we propose algorithms for parameter estimation of fast-sampled homogeneous Markov chains observed in white Gaussian noise. Our algorithms are obtained by the robust discretization of stochastic differential equations involved in the estimation of continuous-time hidden Markov models (HMM's) via the EM algorithm. We present two algorithms: the first is based on the robust discretization of continuous-time filters that were recently obtained by Elliott to estimate quantities used in the EM algorithm; the second is based on the discretization of continuous-time smoothers, yielding essentially the well-known Baum-Welch re-estimation equations. The smoothing formulas for continuous-time HMM's are new, and their derivation involves two-sided stochastic integrals. The choice of discretization results in equations which are identical to those obtained by deriving the results directly in discrete time. The filter-based EM algorithm has negligible memory requirements; indeed, independent of the number of observations. In comparison the smoother-based discrete-time EM algorithm requires the use of the forward-backward algorithm, which is a fixed-interval smoothing algorithm and has memory requirements proportional to the number of observations. On the other hand, the computational complexity of the filter-based EM algorithm is greater than that of the smoother-based scheme. However, the filters may be suitable for parallel implementation. Using computer simulations we compare the smoother-based and filter-based EM algorithms for HMM estimation. We provide also estimates for the discretization error     

MAP decoding in channels with memory

The expectation-maximization (EM) algorithm is popular in estimating the parameters of various statistical models. We consider applications of the EM algorithm to the maximum a posteriori (MAP) sequence decoding assuming that sources and channels are described by hidden Markov models (HMMs). The HMMs can accurately approximate a large variety of communication channels with memory and, in particular, wireless fading channels with noise. The direct maximization of the a posteriori probability (APP) is too complex. The EM algorithm allows us to obtain the MAP sequence estimation iteratively. Since each step of the EM algorithm increases the APP, the algorithm can improve the performance of any decoding procedure