Team for Research in
Ubiquitous Secure Technology

Citation
Tanya Roosta, Martin J. Wainwright, Shankar Sastry. "Convergence Analysis of Reweighted Sum-Product Algorithms". International Conference on Acoustic, Speech and Signal Processing, April, 2007.

Abstract
Many signal processing applications of graphical models require efficient methods for computing (approximate) marginal probabilities over subsets of nodes in the graph. The intractability of this marginalization problem for general graphs with cycles motivates the use of approximate message-passing algorithms, including the sum-product algorithm and variants thereof. This paper studies the convergence and stability properties of the family of reweighted sum-product algorithms, a generalization of the standard updates in which messages are adjusted with graph-dependent weights. For homogenous models, we provide a complete characterization of the potential settings and message weightings that guarantee uniqueness of fixed points, and convergence of the updates. For more general inhomogeneous models, we derive a set of sufficient conditions that ensure convergence, and provide estimates of rates. These theoretical results are complemented with experimental simulations on various classes of graphs.

Electronic downloads

• d_icassp_RooWai06.pdf · application/pdf · 97 kbytes

• HTML

  Tanya Roosta, Martin J. Wainwright, Shankar Sastry. <a
  href="http://www.truststc.org/pubs/234.html"
  >Convergence Analysis of Reweighted Sum-Product
  Algorithms</a>, International Conference on Acoustic,
  Speech and Signal Processing, April, 2007.

• Plain text

  Tanya Roosta, Martin J. Wainwright, Shankar Sastry.
  "Convergence Analysis of Reweighted Sum-Product
  Algorithms". International Conference on Acoustic,
  Speech and Signal Processing, April, 2007.

• BibTeX

  @inproceedings{RoostaWainwrightSastry07_ConvergenceAnalysisOfReweightedSumProductAlgorithms,
      author = {Tanya Roosta and Martin J. Wainwright and Shankar
                Sastry},
      title = {Convergence Analysis of Reweighted Sum-Product
                Algorithms},
      booktitle = {International Conference on Acoustic, Speech and
                Signal Processing},
      month = {April},
      year = {2007},
      abstract = {Many signal processing applications of graphical
                models require efficient methods for computing
                (approximate) marginal probabilities over subsets
                of nodes in the graph. The intractability of this
                marginalization problem for general graphs with
                cycles motivates the use of approximate
                message-passing algorithms, including the
                sum-product algorithm and variants thereof. This
                paper studies the convergence and stability
                properties of the family of reweighted sum-product
                algorithms, a generalization of the standard
                updates in which messages are adjusted with
                graph-dependent weights. For homogenous models, we
                provide a complete characterization of the
                potential settings and message weightings that
                guarantee uniqueness of fixed points, and
                convergence of the updates. For more general
                inhomogeneous models, we derive a set of
                sufficient conditions that ensure convergence, and
                provide estimates of rates. These theoretical
                results are complemented with experimental
                simulations on various classes of graphs.},
      URL = {http://www.truststc.org/pubs/234.html}
  }
  

Posted by Tanya Roosta on 22 Mar 2007.
For additional information, see the Publications FAQ or contact webmaster at www truststc org.