| For a discrete-time Markov process observed in memory-less noise, the recursive equations for maximum a posteriori probability state sequence (MAPSS) estimation can be applied using either continuous or discrete state spaces. For a linear system model on a continuous state space with additive white Gaussian noise, MAPSS estimation results in the Kalman filter (KF) and fixed interval smoother. For a Markov chain on a finite discrete state space, MAPSS estimation results in the Viterbi algorithm (VA). For applications on a continuous state space where linearity and additive white Gaussian noise assumptions may be invalid, the KF cannot be used to implement the MAPSS estimator. In this case, the continuous state space may be quantized onto a discrete state space grid so that a VA estimator can be implemented. Unfortunately, the computational requirements for a VA estimator become excessive when continuous state spaces are quantized onto grids, even for systems of moderate dimensionality.; The problem addressed in this research is the implementation of the algorithms for MAPSS estimation on a continuous state space using polyhedral parameterization. Several methods to represent polyhedra were investigated; it was found that algorithms for MAPSS estimation favor hyperplane representation. In hyperplane representation, polyhedral facets are created by the convex combination of closed linear half spaces defined by support hyperplanes. Hyperplane representation results in smaller data structures, relaxed numeric precision requirements, and simpler algorithms when compared to other methods of representing polyhedra.; The most computationally expensive operation in the MAPSS estimator is maximum convolution. However, maximum convolution of two polyhedral functions is greatly simplified with maximum transforms. Specifically, maximum convolution is replaced by the inverse transform of the sum of two transformed polyhedral functions. The maximum transform of a polyhedral function produces another polyhedral function with hyperplane abscissa and slopes interchanged and hyperplane ordinates and z-intercepts interchanged with negation.; For this research, polyhedral-based algorithms are developed for the MAPSS estimator. Computer simulations quantify the performance of KF, VA, and polyhedral MAPSS estimators for linear systems with state space dimensions of 1, 2, and 3. Hyperplane count is tracked. For similar performance levels, polyhedral estimation significantly reduces memory usage and computational load needed for VA estimation. |
