Several multi-user coding problems ask the transmitter to find a good approximation of a random binary vector, but only among codewords that satisfy a prescribed set of parity equations. The standard example is writing on a channel whose interference the transmitter knows in advance, the Gelfand-Pinsker problem. There, the message selects a "bin" (a coset: a shifted copy of a linear code). The encoder then has to quantize the known interference using only codewords from that bin. Theory says sparse-graph codes can do this optimally. Martinian and Wainwright proved that compound codes reach the Wyner-Ziv and Gelfand-Pinsker limits (ISIT version). These codes stack a sparse parity-check (LDPC) layer on the hidden bits of a sparse generator-matrix (LDGM) quantizer. The proof assumes exhaustive maximum-likelihood encoding, though, and the authors flag the practical encoder as open. The workhorse practical encoder, belief-propagation-guided decimation (BPGD), repeatedly estimates which way each bit leans and permanently fixes the most confident ones. It stalls or lands in contradictions once hard parity constraints sit on top of the quantizer.
This note proposes treating the parity constraints as a stiffness that is ramped up during decimation, rather than enforced from the first step. Early on, the encoder behaves like a pure LDGM quantizer, a regime where spatially coupled BPGD is known to work. As more bits are fixed, parity violations are penalized more heavily. The few violations that remain at the end are removed by a small channel-decoding step on the parity layer. The bet is that decimation on compound graphs fails because the encoder commits early to bits that make the parity constraints expensive to satisfy later. We call this entrapment. The bet is not that the marginals themselves are uninformative. A continuation that keeps the parity layer "cheaply repairable" at every step should avoid it.
Core Claim
Let $\mathbf{x}\in\{0,1\}^n$ be the vector to quantize, $\mathbf{m}\in\{0,1\}^k$ the hidden bits, $G$ the sparse generator, $\mathbf{H}$ the sparse parity-check matrix defining the bins, and $\mathbf{s}$ the syndrome (bin label) fixed by the message. The encoder must output $\mathbf{m}$ with $\mathbf{H}\mathbf{m}=\mathbf{s}$ and small Hamming distortion $d_H(\mathbf{x},\mathbf{m}G)/n$. We run decimation on the tempered measure
$$P_{\beta,\lambda}(\mathbf{m}) \propto \exp\!\big(-\beta\, d_H(\mathbf{x},\mathbf{m}G) \;-\; \lambda\, |\mathbf{H}\mathbf{m}\oplus\mathbf{s}|\big),$$
where $\beta$ is the usual test-channel inverse temperature, $|\cdot|$ counts unsatisfied parity checks, and $\lambda$ is the parity stiffness. $\lambda$ rises from near zero to large values as the fraction of decimated bits grows. After decimation, the residual syndrome $\mathbf{r}$ is cleared by solving
$$\min_{\mathbf{e}} \textstyle\sum_i c_i e_i \quad \text{s.t.}\quad \mathbf{H}\mathbf{e}=\mathbf{r},$$
where $c_i$ is the distortion increase from flipping hidden bit $i$, read off locally from the LDGM layer. This is weighted syndrome decoding on an LDPC code. Min-sum belief propagation solves it well whenever the density of violated checks is below the repair decoder's threshold.
That threshold gives a principled schedule. The rule is to raise $\lambda$ whenever BP's estimate of the violated-check density, projected to the end of decimation, would exceed what the repair decoder can clear. The claim that is new is the following. With spatial coupling on both layers and this repair-aware stiffness schedule, the encoder should output codewords exactly inside the prescribed coset. It should reach distortion as close to the Shannon bound as unconstrained coupled LDGM quantization achieves at the same effective rate. Hard-constrained compound BPGD, which fixes $\lambda=\infty$ from the start, should not.
Research Program
The work has three parts, and the first is a diagnosis. We will instrument hard compound BPGD, in the style of Wainwright and Maneva's decimation extended to the three-layer graph. At each decimation step we will record two quantities. The first is the marginal bias profile, which tells us whether beliefs have collapsed toward $1/2$. The second is an estimated repair cost: the weighted syndrome decoder is run on the current partial assignment, and we record the minimum distortion needed to restore parity.
The two failure explanations predict different signatures. If loops in the pre-code are corrupting the marginals, bias profiles should flatten before any repair cost appears. If entrapment by early commitments is the cause, repair cost should jump abruptly at some decimation fraction while biases stay sharp. This connects to Murayama and Davis's spin-glass picture of LDGM encoders being caught in metastable states. It also connects to the observation of Soleymani et al. that re-running inference between decimation steps is what prevents cascading errors. Our diagnosis asks which of these mechanisms dominates once parity is added.
The second part is the algorithm. Following Aref, Macris, Urbanke and Vuffray, we couple the LDGM quantizer and the parity layer along a chain of $L$ positions. Seeded decimation then moves as a wave from the boundary, and parity violations appear only just behind the wave front. That lets the repair decoder work in a sliding window rather than on the whole block. The stiffness $\lambda$ plays the role of a continuation parameter, as in Mobahi and Fisher's Gaussian continuation. We do not import their bound, which is proved only for continuous domains. We borrow the idea of starting from an easy landscape and tracking it toward the hard one.
The relaxation of hard constraints into weighted penalties echoes Relaxed Survey Propagation, which softened clause constraints for Max-SAT. Our case differs in one important way: the constraints must hold exactly at the end, which is why the terminal repair step exists.
The third part is analysis. Using density evolution on the coupled ensemble, we will ask whether a finite $\lambda$ schedule keeps the projected violated-check density below the repair threshold throughout the wave. This would give a computable admissible region for $(\beta,\lambda)$. Aref et al. note that the choice of $\beta$ is empirical, and the same holds for $\lambda$ here. Even a partial characterization of the stiffness schedule would replace a grid search.
Baselines
The naive reference point is to ignore the bin during quantization and then repair: run coupled LDGM BPGD with $\lambda=0$, then apply the weighted syndrome decoder once. This isolates the value of continuation. If the unconstrained solution violates roughly half the checks, repair should be very costly. If it violates few, our schedule is unnecessary. Both runs use the same graph, block length, BP iteration budget and repair decoder.
The direct existing method is hard-constrained compound BPGD, with $\lambda=\infty$ throughout, on both uncoupled and coupled compound graphs. Running it with coupling is itself the "obvious" combination of Martinian and Wainwright's construction with Aref et al.'s seeded decimation. It is the strongest competitor, because if coupling alone fixes compound encoding, our contribution collapses. It gets the same tuning budget over $\beta$, decimation rate and damping as our method gets over $(\beta,\lambda)$.
The reference for the best achievable distortion is unconstrained coupled LDGM BPGD at the same effective rate. Aref et al. report Hamming distortion $D=0.1105$ at rate $R=0.5$ with chain length $L=64$, against a Shannon bound of about $0.1100$, on the symmetric Bernoulli source. Our method beats hard compound BPGD if it lands in the coset on at least 99% of blocks with distortion within $0.001$ of this unconstrained number at matched $n$, $L$ and coupling width, while hard compound BPGD does not.
For the full Gelfand-Pinsker system, there is no reported practical-encoder result found on Lacuna. The comparison there is to the computed Gelfand-Pinsker capacity and to the baselines above. A second ablation, constant $\lambda$ at its final value, separates "any soft penalty" from "a ramped penalty".
Why not just…?
Why not just spatially couple the compound graph and keep hard parity? This is a real threat, and nothing in the file shows it failing: Martinian and Wainwright discuss uncoupled message passing, and Aref et al. never add a parity layer. It is therefore our main baseline rather than a straw man. The diagnostic will show whether hard decimation on the coupled compound graph produces repair-cost jumps. If it reaches the unconstrained distortion without them, we report that as the finding and drop the continuation.
Why not quantize first and bin afterwards, as in Wyner-Ziv designs? For Wyner-Ziv this works in principle. The encoder quantizes freely and sends a syndrome of whatever hidden bits it found, which is the structure Nangir et al. use. The coset problem then moves to the decoder, where belief propagation is ordinary channel decoding, much as Nagpal et al. push all soft resolution to the receiver. We therefore expect no gain on Wyner-Ziv and include it only as a control. In Gelfand-Pinsker, however, the message fixes the coset before encoding, so the encoder cannot escape the constraint. That is why Gelfand-Pinsker is our primary target.
Why not eliminate the constraints algebraically? If $\mathbf{H}=[I\,|\,A]$ with sparse $A$, one can solve for the parity bits and obtain an unconstrained LDGM quantizer with effective generator $AG_p+G_f$. Coupled BPGD could then run directly on that quantizer. The catch is on both sides. Sparse systematic parity matrices make weak bin codes at the decoder, because degree-one variables hurt the decoding threshold. Good LDPC matrices, meanwhile, have dense systematic forms. We will test this trade-off explicitly. We will build a pre-code family with sparse systematic part, measure both encoder distortion and decoder message-recovery threshold, and compare against our method on well-designed LDPC bins.
Why not random restarts or reinforcement-style soft decimation? Restarting greedy decimation retries an exponentially large tree of early commitments. Friesen and Domingos found restarts orders of magnitude slower than structured decomposition in rugged landscapes. We will nonetheless give restarts a compute budget equal to our method. We will also run soft decimation that tempers the fixing of bits but keeps parity hard. This separates softness in commitments from softness in constraints.
Proposed Experiments
The first experiment is coset-constrained quantization of the binary symmetric source. We use block lengths $n=10^4$ to $10^5$, matching the regime of Wainwright and Maneva and Aref et al., with chain lengths $L\in\{32,64,128\}$ and coupling widths $w\in\{2,3,4\}$. Effective rates sweep around $0.5$, and the syndrome $\mathbf{s}$ is drawn at random. Because a coset of a linear code quantizes a symmetric source as well as the code itself, the target is $h_2^{-1}(1-R)$. The metrics are distortion gap, fraction of blocks ending exactly in the coset, and wall-clock cost relative to unconstrained coupled BPGD.
The second experiment is binary Gelfand-Pinsker coding with a symmetric Bernoulli interference, a transmit-weight constraint and a binary symmetric channel. The metric is the highest message rate at which the receiver's BP decoder on the compound graph reaches bit error rate $10^{-5}$, compared with capacity. The third experiment is the Wyner-Ziv control against quantize-then-bin. The fourth is the entrapment diagnostic, applied to every method: repair-cost and bias trajectories versus decimated fraction.
The decisive check is the stiffness ablation on the first experiment. The contrasts are $\lambda=0$ followed by repair, constant $\lambda$, hard parity with coupling, and the repair-aware ramp. The hypothesis is supported only if the ramp alone keeps the repair cost flat and matches the unconstrained $0.1105$-level distortion inside the coset. It is refuted if hard coupled BPGD already does.
References
- Analysis of LDGM and compound codes for lossy compression and binning
- Low-density constructions can achieve the Wyner-Ziv and Gelfand-Pinsker bounds
- Lossy source encoding via message-passing and decimation over generalized codewords of LDGM codes
- Rate Distortion Codes in Sensor Networks
- Matrix Completion over Finite Fields: Bounds and Belief Propagation Algorithms
- Lossy source coding via spatially coupled LDGM ensembles
- A Theoretical Analysis of Optimization by Gaussian Continuation
- Relaxed Survey Propagation: A Sum-Product Algorithm for Max-SAT
- Approaching the Rate-Distortion Limit With Spatial Coupling, Belief Propagation, and Decimation
- Successive Wyner-Ziv Coding for the Binary CEO Problem Under Logarithmic Loss
- Coding and System Design for Quantize-Map-and-Forward Relaying
- Recursive Decomposition for Nonconvex Optimization - IJCAI-15 Distinguished Paper