1 Show That The Counting Numbers Defined By Equation 11 26 Are Convex 2 In This Exer 2528121

1. Show that the counting numbers defined by equation (11.26) are convex.

2. In this exercise, we will derive another message passing algorithm, called the two-way algorithm, for finding fixed points of region-based energy functionals; this algorithm allows for more general region graphs than in exercise. It uses two messages along each link r → r’: one from r to r’ and one from r’ to r. Consider a region-based free energy as in equation (11.27). For any region r, let pr = |Up(r)| be the number of regions that are directly upward of r. Assume that for any top region (so that pr = 0), we have that κr = 1. We now define qr = (1 − κr)/pregion, taking qr = 1 when pr = 0 (so that κr = 1, as per our assumption). Assume furthermore that qr ≠ 2, and define βr = 1/(2 − qr).

The following equalities define the messages and the potentials in this algorithm:

Note that the messages are as we would expect: the message sent from r to r’ is simply the product of r’s initial potential with all of its incoming messages except the one from r’ (and similarly for the message sent from r’ to r). However, as we discussed in our derivation of the region graph algorithm, this computation will double-count the information that arrived at r from r’ via an indirect path. The final computation of the messages δ is intended to correct for that double-counting. In this exercise, you will show that the fixed points are precisely the same as the fixed points of the update equations equation (11.71)–equation (11.76).