Displacement Convexity in Spatially Coupled Scalar Recursions

Rafah El-Khatib, Nicolas Macris, Tom Richardson, Rüdiger L. UrbankeIEEE Trans. Information Theory 2017 · DOI · OpenReview

Abstract

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 functional. We show, under mild conditions, that the potential functional is displacement convex and that the minimizers are given by the fixed points of the recursions. Furthermore, we give the conditions on the system such that the minimizing fixed point is unique up to translation along the spatial direction. The condition matches those in previous literature for the existence of spatial fixed points. 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 mechanical models. We illustrate it with applications to Low-Density Parity-Check and generalized LDPC codes used for transmission on the binary erasure channel, or general binary memoryless symmetric channels within the Gaussian reciprocal channel approximation, as well as compressive sensing.

Introduction

In fields like coding theory and statistical physics, spatial coupling has emerged as a transformative technique. By linking a series of independent systems—such as error-correcting codes—into a spatial chain, researchers discovered that low-complexity iterative algorithms can achieve theoretically optimal performance, a phenomenon known as "threshold saturation."

To analyze the asymptotic performance of these systems, researchers typically use iterative update equations called "density evolution" (DE) equations. However, proving the convergence and stability of these equations is mathematically challenging because the underlying energy landscapes are often complex and non-convex. This paper addresses this gap by revealing a hidden mathematical structure called "displacement convexity" within the equations governing these systems.

The Variational Formulation and Potential Functional

The analysis begins by approximating the discrete chain of coupled systems as a continuous spatial line (the continuum limit). This allows the system's state to be described by a potential functional $\mathcal{W}(f,g)$, where finding the fixed points of the density evolution equations is equivalent to finding the stationary points of this functional.

The functions $h_f(u)$ and $h_g^{-1}(u)$ and the area between them, which characterizes the potential functional.

A critical component of this formulation is the relationship between the scalar functions $h_f$ and $h_g$. As shown in the figure above, the potential is essentially defined by the gap between these functions. The "positive gap condition" ensures that the system can transition from a high-error state to a low-error state, represented by a propagating wave profile.

Methods: Displacement Convexity and Rearrangement

The core innovation of this work is the application of displacement convexity, a concept borrowed from optimal transport theory. Standard convexity considers the linear average of two functions. In contrast, displacement convexity interpolates their inverses—effectively averaging their spatial coordinates rather than their amplitudes.

To simplify the search for a minimum, the authors employ rearrangement inequalities. They prove that any non-monotonic or "bumpy" profile can be smoothed into a strictly non-decreasing profile without increasing the potential. This allows the analysis to focus exclusively on monotonic functions, which correspond to the physical intuition of a smooth transition or "wave" moving through the spatially coupled system.

Key Insights and Results

  1. Strict Displacement Convexity: The paper formally proves (Proposition 5.1) that the potential functional is strictly displacement convex under mild conditions. This is the "right" kind of convexity for these systems because it respects the translational nature of spatial coupling.
  2. Uniqueness of the Wave: Because the functional is displacement convex, the minimizing solution is unique up to a simple spatial shift. This implies that the system will not get stuck in fundamentally different stable states; there is only one stable "wave" profile.
  3. Broad Applicability: The framework is validated across several domains:
  4. LDPC Codes: Regular and Generalized LDPC codes over the Binary Erasure Channel (BEC).
  5. Gaussian Approximations: Systems analyzed for general binary memoryless symmetric channels.
  6. Compressive Sensing: State evolution equations used to track algorithm performance.

Limitations and Future Work

While the continuum approximation provides elegant proofs, real-world spatially coupled systems are inherently discrete. Adapting this displacement convexity analysis to a strictly discrete formulation remains a significant open problem. Additionally, while the authors show that monotonic profiles are preferred, further work is needed to definitively rule out non-monotonic minimizers in more exotic system configurations.

In conclusion, displacement convexity provides a powerful new lens for understanding why spatially coupled systems work so well, offering a rigorous mathematical foundation for the observed stability and optimality of these modern engineering marvels.

Summary updated

Abstract

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 functional. We show, under mild conditions, that the potential functional is \emph{displacement convex} and that the minimizers are given by the fixed points of the recursions. Furthermore, we give the conditions on the system such that the minimizing fixed point is unique up to translation along the spatial direction. The condition matches those in \cite{KRU12} for the existence of spatial fixed points. \emph{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 mechanical models. We illustrate it with applications to Low-Density Parity-Check and generalized LDPC codes used for transmission on the binary erasure channel, or general binary memoryless symmetric channels within the Gaussian reciprocal channel approximation, as well as compressive sensing.
BibTeX
@article{elkhatib2017displacement,
  author = {Rafah El-Khatib and Nicolas Macris and Tom Richardson and Rüdiger L. Urbanke},
  title = {{Displacement Convexity in Spatially Coupled Scalar Recursions}},
  journal = {IEEE Transactions on Information Theory},
  year = {2017},
  doi = {10.1109/tit.2018.2864728},
}
Figure