The posterior matching scheme, for feedback encoding of a message point lying on the unit interval over memoryless channels, maximizes mutual information for an arbitrary number of channel uses. However, it in general does not always achieve any positive rate; so far, elaborate analyses have been required to show that it achieves any positive rate below capacity. More recent efforts have introduced a random "dither" shared by the encoder and decoder to the problem formulation, to simplify analyses and guarantee that the randomized scheme achieves any rate below capacity. Motivated by applications (e.g. human-computer interfaces) where (a) common randomness shared by the encoder and decoder may not be feasible and (b) the message point lies in a higher dimensional space, we focus here on the original formulation without common randomness, and use optimal transport theory to generalize the scheme for a message point in a higher dimensional space. By defining a stricter, almost sure, notion of message decoding, we use classical probabilistic techniques (e.g. change of measure and martingale convergence) to establish succinct necessary and sufficient conditions on when the message point can be recovered from infinite observations: Birkhoff ergodicity of a random process sequentially generated by the encoder. We also show a surprising "all or nothing" result: the same ergodicity condition is necessary and sufficient to achieve any rate below capacity. We provide applications of this message point framework in human-computer interfaces and multi-antenna communications.
Shayevitz and Feder introduced the posterior matching scheme for the message point lying on the @math interval in @cite_57 that is applicable to any memoryless channel. It includes the encoding schemes for the BSC and AWGN channel by Horstein and Schalkwijk-Kailath as special cases and provides the first rigorous proof that the Horstein scheme achieves capacity on the BSC.
@cite_57
2509220592 2011914761 2964122424 2074430484
Shayevitz and Feder proposed a capacity-achieving sequential transmission scheme for memoryless channels called posterior matching (PM). The proof of capacity achievability of PM is involved and requires invertibility of the PM kernel (also referred to as one-step invertibility). Recent work by the same authors provided a simpler proof but still requires PM kernel invertibility. In this paper, we introduce a fundamental principle for optimal communication over general memoryless channels in the presence of noiseless feedback, termed posterior matching. Using this principle, we devise a (simple, sequential) generic feedback transmission scheme suitable for a large class of memoryless channels and input distributions, achieving any rate below the corresponding mutual information. This provides a unified framework for optimal feedback communication in which the Horstein scheme (BSC) and the Schalkwijk-Kailath scheme (AWGN channel) are special cases. Thus, as a corollary, we prove that the Horstein scheme indeed attains the BSC capacity, settling a longstanding conjecture. We further provide closed form expressions for the error probability of the scheme over a range of rates, and derive the achievable rates in a mismatch setting where the scheme is designed according to the wrong channel model. Several illustrative examples of the posterior matching scheme for specific channels are given, and the corresponding error probability expressions are evaluated. The proof techniques employed utilize novel relations between information rates and contraction properties of iterated function systems. Posterior matching (PM) is a sequential horizon-free feedback communication scheme introduced by the authors, who also provided a rather involved optimality proof, showing that it achieves capacity for a large class of memoryless channels. considered a non-sequential variation of PM with a fixed number of messages and a random decision-time, and gave a simpler proof establishing its optimality via a novel extrinsic Jensen–Shannon divergence argument. Another simpler optimality proof was given by Li and El Gamal, who considered a fixed-rate fixed block-length variation of PM with an additional randomization. Both these works also provided error exponent bounds. However, their simpler achievability proofs apply only to discrete memoryless channels, and are restricted to a non-sequential setup with a fixed number of messages. In this paper, we provide a short and transparent proof for the optimality of the fully sequential randomized horizon-free PM scheme over general memoryless channels. Borrowing the key randomization idea of Li and El Gamal, our proof is based on analyzing the random walk behavior of the shrinking posterior intervals induced by a reversed iterated function system decoder. This paper re-visits Shayevitz & Feder's recent ‘Posterior Matching Scheme’, an explicit, dynamical system encoder for communication with feedback that treats the message as a point on the [0,1] line and achieves capacity on memo-ryless channels. It has two key properties that ensure that it maximizes mutual information at each step: (a) the encoder sequentially hands the decoder what is missing; and (b) the next input has the desired statistics. Motivated by brain-machine interface applications and multi-antenna communications, we consider developing dynamical system feedback encoders for scenarios when the message point lies in higher dimensions. We develop a necessary and sufficient condition — the Jacobian equation — for any dynamical system encoder that maximizes mutual information. In general, there are many solutions to this equation. We connect this to the Monge-Kantorovich Optimal Transportation Problem, which provides a framework to identify a unique solution suiting a specific purpose. We provide two examplar capacity-achieving solutions — for different purposes — for the multi-antenna Gaussian channel with feedback. This insight further elucidates an interesting relationship between interactive decision theory problems and the theory of optimal transportation.