And now to something completely different: Spatial coupling as a proof technique
Andrei Giurgiu, Nicolas Macris, Rudiger L. Urbanke · 2013
The aim of this paper is to show that spatial coupling can be viewed not only as a means to build better graphical models, but also as a tool to better understand uncoupled models. The starting point is the observation that some asymptotic properties of graphical models are easier to prove in the case of spatial coupling. In such cases, one can then use the so-called interpolation method to transfer results known for the spatially coupled case to the uncoupled one. Our main application of this framework is to LDPC codes, where we use interpolation to show that the average entropy of the codeword conditioned on the observation is asymptotically the same for spatially coupled as for uncoupled ensembles. We use this fact to prove the so-called Maxwell conjecture for a large class of ensembles. In a first paper last year, we have successfully implemented this strategy for the case of LDPC ensembles where the variable node degree distribution is Poisson. In the current paper we now show how to treat the practically more relevant case of general left degree distributions. In particular, regular ensembles fall within this framework. As we will see, a number of technical difficulties appear when compared to the simpler case of Poisson-distributed degrees. For our arguments to hold we need symmetry to be present. For coding, this symmetry follows from the channel symmetry; for general graphical models the required symmetry is called Nishimori symmetry.