So the well-cited article by Feldman et al from 2005 has a method of constructing the convex hull of the feasible set for ML-decoding.

Basically, he considers the parity check matrix $H$ as a Tanner graph. For each check node $j$ and its neighboring variable node set $N(j)$, he considers the set of all even-sized subsets $S$ of each $N(j)$ and introduces an auxilliary indicator variable $w_{j,S}$ that is one if and only if each variable in $S$ is set to one. He then requires that at least one of these is set to one (or that $w_{j,\emptyset}$ is set to one) and that $x_i = \sum w_{j,S}$, i.e. $x_i$ is one iff its included in some even sized subset $S$ with $w_{j,S} = 1$.

Clearly, this results in a highly exponential algorithm for non-LDPC codes, but ok. What I'm wondering is why the 'first thing that pops into your mind' doesn't work.

What I mean by that is that we have constraints like the following:

$$x_1 + x_2 + x_3 = 0 \text{ (mod 2)}$$

It's easy to check that the convex hull of this corresponds to four hyperplanes in $\mathbb{R}^3$. I haven't calculated it for degree four explicitily, but say a degree four equation would correspond to $M$ linear inequalities in $\mathbb{R}^4$.

Given that we have an LDPC code with $m$ parity check equations, each of degree four or less, the complexity of calculating the convex hull by explicitly producing the corresponding linear inequalities would be $\mathcal{O}(m)$ - still linear.

So why go through all the trouble of introducing an auxilliary variable at all? What's the problem with computing the convex hull directly?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.