Estimation of stochastic processes with random structure and Markov switches in discrete time (Review)

Serhii Ya. Zhuk

doi:10.3103/S0735272720100015

Authors

Serhii Ya. Zhuk Igor Sikorsky Kyiv Polytechnic Institute, Kyiv, Ukraine https://orcid.org/0000-0002-0046-8450

DOI:

https://doi.org/10.3103/S0735272720100015

Keywords:

random structure, dynamic structure, mixed Markov process, filtration algorithm, a posteriori probability density, two-step algorithm, interpolation algorithm, filtering and segmentation of images

Abstract

The review of algorithms of estimation of stochastic processes with random structure and Markov switch obtained on a basis of mathematic tool of mixed Markov processes in discrete time is represented. It is shown that Markov property including continuous valued process with random structure in discrete time and Markov chain controlling its structure modification. There are considered recurrent optimal and quasi-optimal filtering algorithms describing the evolution of a posteriori probability density of the mixed process. Adaptive filters belong to devices class with feedbacks between channels. There is represented Bayesian decision rule for definition of the estimations of discrete and continuous components which are mutually coupled. There are considered recurrent optimal interpolation algorithms: at the fixed point, in the fixed interval and with constant delay and their analysis is carried out. There are represented examples of application of considered estimation algorithms for solution of applicable problems. There are considered two-step algorithms of mutual filtering and segmentation of textural images allowing to preserve computational advantages of single-dimension algorithms of estimation of the processes with random structure and adequate to digital devices with parallel architecture.

References

R. L. Stratonovich, Conditional Markov Processes and their Application to Theory of Optimal Control [in Russian]. Moscow: MGU, 1965.

V. I. Tikhonov, N. K. Kulman, Non-linear Filtering and Quasi-Coherent Signals Reception [in Russian]. Moscow: Sov. Radio, 1975.

V. I. Tikhonov, V. N. Kharisov, Statistic Analysis and Synthesis of Radio Engineering Devices and Systems [in Russian]. Moscow: Radio i Svyaz’, 1991.

R. L. Stratonovich, “Conditional markov processes,” Theory Probab. Its Appl., vol. 5, no. 2, pp. 156–178, 1960, doi: https://doi.org/10.1137/1105015.

V. I. Tikhonov, A. S. Stepanov, “Mutual filtering of continuous and discrete markov’s processes,” Radio Eng. Electron. Phys., vol. 18, no. 7, pp. 1376–1383, 1973.

M. S. Yarlykov, V. A. Smirnov, “Nonlinear filtering of discretely-continuous markovian signals,” Radio Eng. Electron. Phys., vol. 20, no. 2, pp. 32–38, 1975.

V. A. Bukhalev, “Optimal filtering in systems with random stepwise changes of the structure,” Autom. Remote Control, vol. 37, no. 2, pp. 160–169, 1976, uri: http://mi.mathnet.ru/eng/at7690.

V. M. Artemiev, Theory of Systems with Random Structure Modification [in Russian]. Minsk: Vysheish. Shkola, 1979.

I. E. Kazakov, V. M. Artemiev, Optimization of Dynamic Systems of Random Structure [in Russian]. Moscow: Nauka, 1980.

I. E. Kazakov, V. M. Artemiev, V. A. Bukhalev, Analysis of Systems of Random Structure [in Russian]. Moscow: Fizmatlit, 1993.

A. V. Borisov, “Analysis and estimation of the states of special jump markov processes. ii. optimal filtration in wiener noise,” Autom. Remote Control, vol. 65, no. 5, pp. 741–754, 2004, doi: https://doi.org/10.1023/B:AURC.0000028322.97957.ca.

A. V. Borisov, “Analysis of hidden markov models states generated by special jump processes,” Theory Probab. its Appl., vol. 51, no. 3, pp. 589–600, 2006, doi: https://doi.org/10.4213/tvp41.

A. V. Borisov, “Backward representation of markov jump processes and related problems. ii. optimal nonlinear estimation,” Autom. Remote Control, vol. 67, no. 9, pp. 1466–1484, 2006, doi: https://doi.org/10.1134/S0005117906090098.

L. E. Baum, T. Petrie, “Statistical inference for probabilistic functions of finite state markov chains,” Ann. Math. Stat., vol. 37, no. 6, pp. 1554–1563, 1966, doi: https://doi.org/10.1214/AOMS/1177699147.

L. E. Baum, T. Petrie, G. Soules, N. Weiss, “A maximization technique occurring in the statistical analysis of probabilistic functions of markov chains,” Ann. Math. Stat., vol. 41, no. 1, pp. 164–171, 1970, doi: https://doi.org/10.1214/AOMS/1177697196.

L. R. Rabiner, “A tutorial on hidden markov models and selected applications in speech recognition,” Proc. IEEE, vol. 77, no. 2, pp. 257–286, 1989, doi: https://doi.org/10.1109/5.18626.

V. V. Mottl, I. B. Muchnik, Hidden Markov Models in Structural Analysis of Signals [in Russian]. Moscow: Nauka, 1999.

Y. Ephraim, N. Merhav, “Hidden markov processes,” IEEE Trans. Inf. Theory, vol. 48, no. 6, pp. 1518–1569, 2002, doi: https://doi.org/10.1109/TIT.2002.1003838.

O. Cappé, E. Moulines, T. Rydén, Inference in Hidden Markov Models. New York, NY: Springer New York, 2005, doi: https://doi.org/10.1007/0-387-28982-8.

M. Gales, S. Young, “The application of hidden markov models in speech recognition,” Found. Trends Signal Process., vol. 1, no. 3, pp. 195–304, 2007, doi: https://doi.org/10.1561/2000000004.

R. J. Elliott, L. Aggoun, J. B. Moore, Hidden Markov Models: Estimation and Control, vol. 29. New York, NY: Springer New York, 1995, doi: https://doi.org/10.1007/978-0-387-84854-9.

G. A. Ackerson, K. S. Fu, “On state estimation in switching environments,” IEEE Trans. Autom. Control, vol. AC-15, no. 1, pp. 10–17, 1970, doi: https://doi.org/10.1109/TAC.1970.1099359.

N. S. Gritsenko, V. P. Loginov, K. K. Sevostyanov, “Adaptive estimation. part 2,” Zarubezhnaya Radioelektronika, no. 3, pp. 27–50, 1985.

Y. P. Grishin, Y. M. Kazarinov, Dynamic Systems Tolerant to Failure [in Russian]. Moscow: Radio i Svyaz’, 1985.

H. A. P. Blom, Y. Bar-Shalom, “The interacting multiple model algorithm for systems with markovian switching coefficients,” IEEE Trans. Autom. Control, vol. 33, no. 8, pp. 780–783, 1988, doi: https://doi.org/10.1109/9.1299.

V. A. Bukhalev, Recognition, Estimation and Control in Systems with Random Stepwise Structure [in Russian]. Moscow: Nauka-Fizmatlit, 1996.

V. A. Bukhalev, Optimal Smoothing in Systems with Randomly Switching Structure [in Russian]. Moscow: Fizmatlit, 2013.

S. Y. Zhuk, Optimization Methods of Discrete Dynamic Systems with Random Structure [in Russian]. Kyiv: NTUU KPI, 2008.

S. Y. Zhuk, “Joint filtering of mixed Markov processes in discrete time,” Radioelectron. Commun. Syst., vol. 31, no. 1, pp. 29–35, 1988.

Y. A. Kliokis, “Optimal filtering in discrete-time random structure systems,” Avtom. i Telemekhanika, no. 11, pp. 61–70, 1987, uri: http://mi.mathnet.ru/eng/at4629.

V. I. Tikhonov, V. A. Smirnov, V. N. Kharisov, “Optimal filtering of discrete-continuous processes,” Radio Eng. Electron. Phys., vol. 23, no. 7, pp. 1441–1452, 1978.

S. Y. Zhuk, P. A. Yevlanov, “Mutual filtering of parameters of target movement and its maneuver type,” Radiotekhnika, no. 2, pp. 12–14, 1990.

Y. Bar-Shalom, X.-R. Li, Multitarget-Multisensor Tracking: Principles and Techniques. Storrs: YBS Publishing, 1995, uri: https://www.amazon.com/Multitarget-multisensor-tracking-Principles-techniques-1995/dp/0964831201.

X. R. Li, V. P. Jilkov, “Survey of maneuvering target tracking. part v: multiple-model methods,” IEEE Trans. Aerosp. Electron. Syst., vol. 41, no. 4, pp. 1255–1321, 2005, doi: https://doi.org/10.1109/TAES.2005.1561886.

A. A. Konovalov, Basic Principles of Trajectory Processing of Radar Information. Part 2 [in Russian]. St. Petersburg: LETI, 2014.

A. P. Trifonov, Y. S. Shinakov, Joint Discrimination of Signals and Estimation of their Parameters against the Background of Interferences [in Russian]. Moscow: Radio i Svyaz’, 1986.

S. Y. Zhuk, “Applying bi-functional decision rules to the optimization of random-structure discrete dynamic systems,” Sov. J. Comput. Syst. Sci., vol. 29, no. 1, pp. 10–17, 1991.

A. I. Zabrodskiy, S. Y. Zhuk, “Filtering of processes with random structure on background of markov noise in discrete time,” Radioelectron. Commun. Syst., vol. 38, no. 1, pp. 27–33, 1995.

S. Y. Zhuk, “Synthesis of digital detector-meters for mixed Markovian processes,” Radioelectron. Commun. Syst., vol. 32, no. 11, pp. 29–34, 1989.

S. Y. Zhuk, “Direct interpolation of mixed markovian processes in discrete time,” Radioelectron. Commun. Syst., vol. 33, no. 3, pp. 15–21, 1990.

S. Y. Zhuk, “Inverse interpolation of mixed markovian processes in discrete time,” Radioelectron. Commun. Syst., vol. 34, no. 5, pp. 70–75, 1991.

S. Y. Zhuk, “Constant-delay interpolation of random-structure processes in a discrete time,” Radioelectron. Commun. Syst., vol. 35, no. 5, pp. 32–38, 1992.

V. A. Bukhalev, “Optimal smoothing in systems with a randomly switching structure,” Avtom. i Telemekhanika, vol. 53, no. 6, pp. 823–831, 1992, uri: http://mi.mathnet.ru/eng/at3316.

P. A. Evlanov, S. Y. Zhuk, “Integration of meters with failures,” Radioelectron. Commun. Syst., vol. 33, no. 7, pp. 49–53, 1990.

V. I. Gupal, S. Y. Zhuk, Y. A. Mamonov, “Combined filtering and recognition of the type of segment of excitation of noisy speech signals,” Radioelectron. Commun. Syst., vol. 35, no. 11, pp. 7–11, 1992.

S. Y. Zhuk, A. I. Zabrodskij, “Adaptive filtering of speech signals in the presence of colored interferences,” Radioelectron. Commun. Syst., vol. 38, no. 6, pp. 60–65, 1995.

A. A. Shpylka, S. Y. Zhuk, “Joint interpolation of data and parameter filtration of a multibeam communications channel,” Radioelectron. Commun. Syst., vol. 53, no. 1, pp. 20–24, 2010, doi: https://doi.org/10.3103/S0735272710010048.

A. A. Shpylka, S. Y. Zhuk, “Joint decoding of convolution codes and estimation of multipath communication channel’s parameters on a sliding interval,” Radioelectron. Commun. Syst., vol. 54, no. 3, pp. 124–130, 2011, doi: https://doi.org/10.3103/S0735272711030022.

I. O. Tovkach, S. Y. Zhuk, “Adaptive filtration of radio source movement parameters with complex use of sensor network data based on TDOA and RSS methods,” Radioelectron. Commun. Syst., vol. 60, no. 12, pp. 528–537, 2017, doi: https://doi.org/10.3103/S0735272717120020.

I. O. Tovkach, S. Y. Zhuk, “Adaptive filtration of parameters of the uav movement based on the tdoa-measurement sensor networks,” J. Aerosp. Technol. Manag., no. 11, p. e3519, 2019, doi: https://doi.org/10.5028/jatm.v11.1062.

S. Y. Zhuk, I. O. Tovkach, Y. Y. Reutska, “Adaptive filtration of radio source movement parameters based on sensor network TDOA measurements in presence of anomalous measurements,” Radioelectron. Commun. Syst., vol. 62, no. 2, pp. 61–71, 2019, doi: https://doi.org/10.3103/S073527271902002X.

T. V. Baringolts, D. V. Domin, S. Y. Zhuk, V. V. Tsisarzh, “Adaptive algorithm of maneuvering target tracking in complex jamming situation for multifunctional radar with phased antenna array,” Radioelectron. Commun. Syst., vol. 62, no. 7, pp. 342–355, 2019, doi: https://doi.org/10.3103/S0735272719070021.

I. Tovkach, S. Zhuk, “Adaptive filtration of the uav movement parameters based on the aoa-measurement sensor networks,” Int. J. Aviat. Aeronaut. Aerosp., vol. 7, no. 3, p. 0, 2020.

R. A. Schowengerdt, Remote Sensing: Models and Methods for Image Processing, 3rd ed. Cambridge, MA: Academic Press, 2007.

N. V. Verdenskaya, “Images segmentation - statistic models and methods,” Uspekhi Sovrem. Radioelektroniki. Zarubezhnaya Radioelektronika, no. 12, pp. 33–47, 2002.

R. M. Haralick, “Statistical and structural approaches to texture,” Proc. IEEE, vol. 67, no. 5, pp. 786–804, 1979, doi: https://doi.org/10.1109/PROC.1979.11328.

V. T. Fissenko, T. Y. Fissenko, “Segmentation of textured images using fractal methods,” J. Instrum. Eng., vol. 56, no. 5, pp. 63–70, 2013, uri: https://pribor.ifmo.ru/en/article/6254/fraktalnye_metody_segmentacii_teksturnyh_izobrazheniy.htm.

A. K. Jain, “Advances in mathematical models for image processing,” Proc. IEEE, vol. 69, no. 5, pp. 502–528, 1981, doi: https://doi.org/10.1109/PROC.1981.12021.

K. K. Vasiliev, V. R. Krasheninnikov, Statistic Analysis of Images Sequences [in Russian]. Moscow: Radiotekhnika, 2017.

M. I. Rabinovich, A. B. Yezerskiy, Dynamic Theory of Shaping [in Russian]. Moscow: Yanus-K, 1998.

J. W. Woods, S. Dravida, R. Mediavilla, “Image estimation using doubly stochastic gaussian random field models,” IEEE Trans. Pattern Anal. Mach. Intell., vol. PAMI-9, no. 2, pp. 245–253, 1987, doi: https://doi.org/10.1109/TPAMI.1987.4767898.

F. C. Jeng, J. W. Woods, “Texture discrimination using doubly stochastic gaussian random fields,” in ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings, 1989, vol. 3, pp. 1675–1678, doi: https://doi.org/10.1109/icassp.1989.266769.

V. I. Gupal, S. Y. Zhuk, A. V. Murovanyj, “Joint filtration and segmentation of images,” Izv. Akad. Nauk Tekhnicheskaia Kibern., no. 6, pp. 136–141, 1991.

K. K. Vasil’ev, V. E. Dement’ev, N. A. Andriyanov, “Application of mixed models for solving the problem on restoring and estimating image parameters,” Pattern Recognit. Image Anal., vol. 26, no. 1, pp. 240–247, 2016, doi: https://doi.org/10.1134/S1054661816010284.

N. A. Andriyanov, V. E. Dementiev, K. K. Vasiliev, “Developing a filtering algorithm for doubly stochastic images based on models with multiple roots of characteristic equations,” Pattern Recognit. Image Anal., vol. 29, no. 1, pp. 10–20, 2019, doi: https://doi.org/10.1134/S1054661819010048.

N. A. Andriyanov, V. E. Dementiev, “Developing and studying the algorithm for segmentation of simple images using detectors based on doubly stochastic random fields,” Pattern Recognit. Image Anal., vol. 29, no. 1, pp. 1–9, 2019, doi: https://doi.org/10.1134/S105466181901005X.

O. N. Skrypnik, B. V. Lezhankin, A. N. Malov, B. M. Mironov, S. F. Galliev, “Shaping of classification map of underlying surface using images from coherent radar,” Komputernaya Opt., no. 29, pp. 151–159, 2006.

A. N. Malov, B. M. Mironov, V. A. Kuznetsov, “Detection of small-sized objects with segmentation algorithms on a basis of model of system with random stepwise structure,” Komputernaya Opt., vol. 32, no. 1, pp. 89–92, 2008.

I. S. Gruzman, V. I. Mikerin, A. A. Spektor, “Two-step image filtering based on limited data,” J. Commun. Technol. Electron., vol. 40, no. 8, pp. 76–82, 1995.

S. V. Vishnevyy, S. Y. Zhuk, “Two-stage joint non-causal filtering and segmentation of nonuniform images,” Radioelectron. Commun. Syst., vol. 54, no. 10, pp. 554–565, 2011, doi: https://doi.org/10.3103/S0735272711100050.

S. V. Vishnevyy, S. Y. Zhuk, “Two-stage mutual causal filtration and segmentation of heterogeneous images,” Radioelectron. Commun. Syst., vol. 54, no. 1, pp. 37–44, 2011, doi: https://doi.org/10.3103/S0735272711010067.

S. V. Vishnevyy, S. Y. Zhuk, A. N. Pavliuchenkova, “Noncausal two-stage image filtration at presence of observations with anomalous errors,” Visnyk NTUU KPI Seriia - Radiotekhnika Radioaparatobuduvannia, no. 52, pp. 21–28, 2013, uri: http://radap.kpi.ua/radiotechnique/article/view/529.

O. Y. Myronchuk, A. A. Shpylka, S. Y. Zhuk, “Two-stage method for joint estimation of information symbols and channel frequency response in OFDM communication systems,” Radioelectron. Commun. Syst., vol. 63, no. 8, pp. 418–429, 2020, doi: https://doi.org/10.3103/S073527272008004X.