Inference for generalized linear models via alternating directions and bethe free energy minimization

Sundeep Rangan, Alyson K. Fletcher, Philip Schniter, Ulugbek S. Kamilov

Research output: Contribution to journalArticlepeer-review

Abstract

Generalized linear models, where a random vector x is observed through a noisy, possibly nonlinear, function of a linear transform z= A x, arise in a range of applications in nonlinear filtering and regression. Approximate message passing (AMP) methods, based on loopy belief propagation, are a promising class of approaches for approximate inference in these models. AMP methods are computationally simple, general, and admit precise analyses with testable conditions for optimality for large i.i.d. transforms A. However, the algorithms can diverge for general A. This paper presents a convergent approach to the generalized AMP (GAMP) algorithm based on direct minimization of a large-system limit approximation of the Bethe free energy (LSL-BFE). The proposed method uses a double-loop procedure, where the outer loop successively linearizes the LSL-BFE and the inner loop minimizes the linearized LSL-BFE using the alternating direction method of multipliers (ADMM). The proposed method, called ADMM-GAMP, is similar in structure to the original GAMP method, but with an additional least-squares minimization. It is shown that for strictly convex, smooth penalties, ADMM-GAMP is guaranteed to converge to a local minimum of the LSL-BFE, thus providing a convergent alternative to GAMP that is stable under arbitrary transforms. Simulations are also presented that demonstrate the robustness of the method for non-convex penalties as well.

Original languageEnglish (US)
Article number7600459
Pages (from-to)676-697
Number of pages22
JournalIEEE Transactions on Information Theory
Volume63
Issue number1
DOIs
StatePublished - Jan 2017

Keywords

  • ADMM
  • Belief propagation
  • generalized linear models
  • message passing
  • variational optimization

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences

Fingerprint Dive into the research topics of 'Inference for generalized linear models via alternating directions and bethe free energy minimization'. Together they form a unique fingerprint.

Cite this