We introduce a technique for the analysis of general spatially coupled systems that are governed by scalar recursions. Such systems can be expressed in variational form in terms of a potential function. We show, under mild conditions, that the potential function is displacement convex and that the minimizers are given by the fixed points (FPs) of the recursions. Furthermore, we give the conditions on the system such that the minimizing FP is unique up to translation along the spatial direction. The condition matches with that of Kudekar et al.[20] for the existence of spatial FPs. Displacement convexity applies to a wide range of spatially coupled recursions appearing in coding theory, compressive sensing, random constraint satisfaction problems, as well as statistical-mechanics models. We illustrate it with applications to low-density parity-check (LDPC) and generalized LDPC codes used for the transmission on the binary erasure channel or general binary memoryless symmetric channels within the Gaussian reciprocal channel approximation as well as compressive sensing.

We consider the dynamics of message passing for spatially coupled codes and, in particular, the set of density evolution equations that tracks the profile of decoding errors along the spatial direction of coupling. It is known that, for suitable boundary conditions and after a transient phase, the error profile exhibits a “solitonic behavior.” Namely, a uniquely shaped wavelike solution develops, which propagates with a constant velocity. Under this assumption, we derive an analytical formula for the velocity in the framework of a continuum limit of the spatially coupled system. The general formalism is developed for spatially coupled low-density parity-check codes on general binary memoryless symmetric channels, which form the main systems of interest in this paper. We apply the formula for special channels and illustrate that it matches the direct numerical evaluation of the velocity for a wide range of noise values. A possible application of the velocity formula to the evaluation of finite size scaling law parameters is also discussed. We conduct a similar analysis for general scalar systems and illustrate the findings with applications to compressive sensing and generalized low-density parity-check codes on the binary erasure or binary symmetric channels.

We consider the dynamics of belief propagation decoding of spatially coupled Low-Density Parity-Check codes. It has been conjectured that after a short transient phase, the profile of “error probabilities” along the spatial direction of a spatially coupled code develops a uniquely-shaped wavelike solution that propagates with constant velocity ν. Under this assumption and for transmission over general Binary Memoryless Symmetric channels, we derive a formula for ν. We also propose approximations that are simpler to compute and support our findings using numerical data.

We consider spatially coupled systems governed by a set of scalar density evolution equations. Such equations track the behavior of message-passing algorithms used, for example, in coding, sparse sensing, or constraint-satisfaction problems. Assuming that the “profile” describing the average state of the algorithm exhibits a solitonic wave-like behavior after initial transient iterations, we derive a formula for the propagation velocity of the wave. We illustrate the formula with two applications, namely Generalized LDPC codes and compressive sensing.

Potential functionals have been introduced recently as an important tool for the analysis of coupled scalar systems (e.g. density evolution equations). In this contribution we investigate interesting properties of this potential. Using the tool of displacement convexity we show that, under mild assumptions on the system, the potential functional is displacement convex. Furthermore, we give the conditions on the system such that the potential is strictly displacement convex in which case the minimizer is unique.

Spatial coupling has recently emerged as a powerful paradigm to construct graphical models that work well under low-complexity message-passing algorithms. Although much progress has been made on the analysis of spatially coupled models under message passing, there is still room for improvement, both in terms of simplifying existing proofs as well as in terms of proving additional properties. We introduce one further tool for the analysis, namely the concept of displacement convexity. This concept plays a crucial role in the theory of optimal transport and it is also well suited for the analysis of spatially coupled systems. In cases where the concept applies, displacement convexity allows functionals of distributions which are not convex to be represented in an alternative form, so that they are convex with respect to the new parametrization. The alternative convex structure can then often be used to prove the uniqueness of the minimizer of this functional. As a proof of concept we consider spatially coupled (l, r)-regular Gallager ensembles when transmission takes place over the binary erasure channel. In particular, we first show the existence of an optimal profile which minimizes the potential functional governing this system. This profile characterizes the “decoding wave” of the spatially coupled system. We then show that the potential function of the coupled system is displacement convex. Due to some translational degrees of freedom the convexity by itself falls short of establishing the uniqueness of the minimizing profile. But as we will discuss it is an important step in this direction.