

![0_image_0.png](0_image_0.png) 
variances are underestimates by 21.5 percent (averaged over all nodes), while LR variances for K = 8 are overestimates by 16.1 percent. In Figure 6 (top) we show convergence of LR for several values of K, and compare it to LBP. The convergence of variances is similar to LBP, while for the means LR converges considerably faster. In addition, the means in LR converge faster than using block Gauss-Seidel on the same set of overlapping K ×50 vertical strips.

Next, we use the *thin plate model*, which enforces that each node v is close to the average of its nearest neighbors N(v) in the grid, and penalizes curvature. At each node there is a potential: fi(xi,xN(i)) = (xi − 1 |N(i)| ∑j∈N(i) xj)
2. LBP does not converge for this model. LR gives rather loose variance bounds for this more difficult model: for K = 12, it overestimates the variances by 75.4 percent. More importantly, it accelerate convergence of the means. In Figure 6 (bottom) we show convergence plots for means and variances, for several values of K. As K increases, the agreement is achieved faster, and for K = 12 agreement is achieved in under 13 iterations for both means and variances. We note that LR
with K = 4 converges much faster for the means than block Gauss-Seidel.

## V. Multi-Scale Lagrangian Relaxation

In this section, we propose an extension of the LR method considered thus far. Previously, we have considered relaxations based on augmented models where x
′ = ζ(x) involves replication of variables. Here, we consider more general definition of ζ to allow the augmented model to include summary variables, such as a sum over a subset of variables, or any linear combination of these. In discrete models, summary variables can also be non-linear functions of x. For example, "parity bits" are used in coding applications and the "majority rule" is used to define coarse-scale binary variables in the renormalization group approach [19].

Using this idea, we develop a *multiscale* Lagrangian relaxation approach for MRFs defined on grids. The purpose of this relaxation is similar to that of the multigrid and renormalization group methods [20], [19]. Iterative methods generally involve simple rules that propagate information

![0_image_1.png](0_image_1.png)

locally within the graph. Using a multiscale representation of the model allows information to propagate through coarse scales, which improves the rate of convergence to global equilibrium. Also, in discrete problems, such multiscale representations can help to avoid local minima. In the context of our convex LR approach, we expect this to translate into a reduction of the duality gap to obtain the optimal MAP estimate in a larger class of problems.

## A. An Equivalent Multiscale Model

We illustrate the general idea with a simple example based on a 1D Markov chain. While this case is actually tractable by exact methods, it serves to illustrate our approach, which generalizes to 2D grids and 3D lattices. In Fig. 7, we show how to construct the augmented model f
′(x
′) defined on a graph G
′. This is done in two stages.

First, as illustrated in Fig. 7(a), we introduce coarse-scale representations of the fine scale variables by recursively defining summary variables at coarser scales to be functions of variables at the next level down. This defines a set of crossscale constraints, denoted by the square nodes. To allow interactions between coarse-scale variables, while maintaining consistency with the original single-scale model, we introduce extra edges (the dotted ones in Fig. 7(a)) between blocks of nodes that have a (solid) edge between their summary nodes at the next coarser scale. This representation allows us to define a family of constrained multiscale models that are all equivalent to the original single-scale model.

For 2D and 3D lattices, this model is still intractable even after relaxing the cross-scale constraints because each scale is itself intractable.

Next, to obtain a tractable dual problem, we break up the graph into smaller subgraphs, introducing additional constraints to enforce consistency among replicated variables.

In the example, we break the augmented graph at each scale into its maximal cliques, shown in Fig. 7(b). This defines the final augmented model and the corresponding graph. In a 2D graph, the same idea applies, but we obtain a set of maximal cliques consisting of overlapping 2 × 4 and 4 × 2 blocks of