Orbit-product representation and correction of gaussian belief propagation

We present a new view of Gaussian belief propagation (GaBP) based on a representa- tion of the determinant as a product over or- bits of a graph. We show that the GaBP determinant estimate captures totally backtracking orbits of the graph and consider how to correct this estimate. We show that the missing orbits may be grouped into equiva-lence classes corresponding to backtrackless orbits and the contribution of each equiv- alence class is easily determined from the GaBP solution. Furthermore, we demon- strate that this multiplicative correction fac- tor can be interpreted as the determinant of a backtrackless adjacency matrix of the graph with edge weights based on GaBP. Finally, an efficient method is proposed to compute a truncated correction factor including all backtrackless orbits up to a specified length.