Thermodynamics of the binary symmetric channel
Tóm tắt
We study a hidden Markov process which is the result of a transmission of the binary symmetric Markov source over the memoryless binary symmetric channel. This process has been studied extensively in Information Theory and is often used as a benchmark case for the so-called denoising algorithms. Exploiting the link between this process and the 1D Random Field Ising Model (RFIM), we are able to identify the Gibbs potential of the resulting Hidden Markov process. Moreover, we obtain a stronger bound on the memory decay rate. We conclude with a discussion on implications of our results for the development of denoising algorithms.
Tài liệu tham khảo
Behn, U, Zagrebnov, VA: One-dimensional Markovian-field Ising model: physical properties and characteristics of the discrete stochastic mapping. J. Phys. A. 21(9), 2151–2165 (1988). ISSN:0305-4470, MR952930 (89j:82024).
Berghout, S, Verbitskiy, E: On bi-directional modeling of information sources (2015).
Bowen, R: Some systems with unique equilibrium states. Math. Systems Theory. 8(3), 193–202. (1974/75). ISSN:0025-5661, MR0399413 (53 #3257).
Ephraim, Y, Merhav, N: Hidden Markov processes, Special issue on Shannon theory: perspective, trends, and applications. IEEE Trans. Inform. Theory. 48(6), 1518–1569 (2002). ISSN:0018-9448, MR1909472 (2003f:94024), doi:10.1109/TIT.2002.1003838.
Ermolaev, V, Verbitskiy, E: Thermodynamic Gibbs Formalism and Information Theory. In: The Impact of Applications on Mathematics (M. Wakayama et al, ed.), Mathematics for Industry, pp. 349–362. Springer Japan (2014).
Fernandez, F, Viola, A, Weinberger, MJ: Efficient Algorithms for Constructing Optimal Bi-directional Context Sets. Data Compression Conference (DCC), 179–188 (2010). http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=5453460. doi:10.1109/DCC.2010.23.
Fernández, R, Ferrari, PA, Galves, A: Coupling renewal and perfect simulation of chains of infinite order, Ubatuba (2001).
Hochwald, BM, Jelenkovic, PŔ: State learning and mixing in entropy of hidden Markov processes and the Gilbert-Elliott channel. IEEE Trans. Inform. Theory. 45(1), 128–138 (1999). ISSN:0018-9448, MR1677853 (99k:94028).
Jacquet, P, Seroussi, G, Szpankowski, W: On the entropy of a hidden Markov process. Theoret Comput. Sci. 395(2–3), 203–219 (2008).
Ordentlich, E, Weissman, T: Approximations for the entropy rate of a hidden Markov process. In: Proceedings International Symposium on Information Theory 2005, pp. 2198–2202 (2005). http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=1523737. doi:10.1109/ISIT.2005.1523737.
Ordentlich, E, Weinberger, MJ, Weissman, T: Multi-directional context sets with applications to universal denoising and compression. In: ISIT 2005. Proceedings International Symposium on Information Theory. pp. 1270–1274 (2005). http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=1523546. doi:10.1109/ISIT.2005.1523546.
Pollicott M: Computing entropy rates for hidden Markov processes. In: Entropy of hidden Markov processes and connections to dynamical systems, London Math. Soc. Lecture Note Ser, pp. 223–245 (2011). Cambridge Univ. Press, Cambridge MR2866670 (2012i:37010).
Rabiner, LR: A tutorial on hidden Markov models and selected applications in speech recognition. Proc IEEE. 77, 257–286 (1989).
Ruján, P: Calculation of the free energy of Ising systems by a recursion method. Physica A: Stat Theoretical Phys. 91(3–4), 549–562 (1978).
Verbitskiy, EA: Thermodynamics of Hidden Markov Processes. In: Markus, B, Petersen, K, Weissman, T (eds.)Papers from the Banff International Research Station Workshop on Entropy of Hidden Markov Processes and Connections to Dynamical Systems, pp. 258–272. London Mathematical Society, Lecture Note Series (2011). http://dx.doi.org/10.1017/CBO9780511819407.010.
Weissman, T, Ordentlich, E, Seroussi, G, Verdú, S, Weinberger, MJ: Universal discrete denoising: known channel, IEEE Trans. Inform. Theory. 51(1), 5–28 (2005). ISSN: 0018-9448 MR2234569 (2008h:94036).
Yu, J, Verdú, S: Schemes for bidirectional modeling of discrete stationary sources. IEEE Trans. Inform. Theory. 52(11), 4789–4807 (2006). ISSN:0018-9448, MR2300356 (2007m:94144).
Zuk, O, Domany, E, Kanter, I, Aizenman, M: From Finite-System Entropy to Entropy Rate for a Hidden Markov Process. IEEE Sig Proc. Letters. 13(9), 517–520 (2006).