Lab Home | Phone | Search
Center for Nonlinear Studies  Center for Nonlinear Studies
 Colloquia Archive 
 Postdoc Seminars Archive 
 Quantum Lunch 
 CMS Colloquia 
 Q-Mat Seminars 
 Q-Mat Seminars Archive 
 Kac Lectures 
 Dist. Quant. Lecture 
 Ulam Scholar 
 Summer Research 
 Past Visitors 
 History of CNLS 
 Maps, Directions 
 CNLS Office 
Thursday, September 18, 2008
3:30 PM - 4:30 PM
CNLS Conference Room (TA-3, Bldg 1690)


Gaussian Belief Propagation for Solving Systems of Linear Equations: Theory and Application

Danny Bickson
IBM, Haifa

The canonical linear-algebraic problem of solving a system of linear equations arises in numerous contexts in the mathematical sciences and engineering. In this talk, we introduce an efficient Gaussian belief propagation (GaBP) solver that does not involve direct matrix inversion. The iterative nature of our approach allows for a distributed message-passing implementation of the solution algorithm. We discuss the properties of the GaBP solver, including convergence,exactness, computational complexity, message-passing efficiency and its relation to classical solution methods. The attractiveness of the proposed solver, in comparison to conventional iterative solution methods, is demonstrated using linear detection applications.

The talk is based on a joint work with Prof. Jack K. Wolf (UCSD), Prof. Paul H. Siegel (UCSD), Dr. Ori Shental (UCSD) and Prof. Danny Dolev (HUJI).

Host: Misha Chertkov, T-13