1
$\begingroup$

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?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.