IC Colloquium: OpAMP: Approximate Message Passing with Time-Varying Linear Operators
By: Bobak Nazer - Boston University
Abstract
Approximate message passing (AMP) is a powerful theoretical framework that provides precise characterizations of iterative inference algorithms in the high-dimensional regime, including generalized linear regression and low-rank matrix estimation as special cases. Implicitly, the AMP framework presumes that computations (e.g., matrix multiplications) are carried out in a centralized fashion. However, in practice, due to time or memory constraints, large-scale computations are often distributed across multiple servers, some of which may respond more slowly than others (i.e., stragglers). We demonstrate how to generalize AMP to allow for a time-varying linear operator to be applied to the data matrix at each iteration, capturing erasures due to missing partial computations as a special case. One surprising consequence is that, in certain applications, scheduling partial computations can be more efficient in terms of total matrix multiplications. We illustrate this phenomenon via a case study of power iteration applied to a spiked Wigner model. Joint work with Riccardo Rossetti and Galen Reeves.
Bio
Bobak Nazer is an Associate Professor in the Department of Electrical and Computer Engineering at Boston University, and is spending the 2026 - 2027 academic year on sabbatical at EPFL. He received the Ph.D. degree in 2009 and the M.S. degree in 2005 from the University of California, Berkeley, as well as the B.S. degree in 2003 from Rice University, all in electrical engineering. He is a past recipient of the IEEE Communications Society & Information Theory Society Joint Paper Award, the NSF CAREER Award, the Eli Jury Award, and the Gerald and Deanne Gitner Family Award for Innovation in Teaching with Technology.
More information
Abstract
Approximate message passing (AMP) is a powerful theoretical framework that provides precise characterizations of iterative inference algorithms in the high-dimensional regime, including generalized linear regression and low-rank matrix estimation as special cases. Implicitly, the AMP framework presumes that computations (e.g., matrix multiplications) are carried out in a centralized fashion. However, in practice, due to time or memory constraints, large-scale computations are often distributed across multiple servers, some of which may respond more slowly than others (i.e., stragglers). We demonstrate how to generalize AMP to allow for a time-varying linear operator to be applied to the data matrix at each iteration, capturing erasures due to missing partial computations as a special case. One surprising consequence is that, in certain applications, scheduling partial computations can be more efficient in terms of total matrix multiplications. We illustrate this phenomenon via a case study of power iteration applied to a spiked Wigner model. Joint work with Riccardo Rossetti and Galen Reeves.
Bio
Bobak Nazer is an Associate Professor in the Department of Electrical and Computer Engineering at Boston University, and is spending the 2026 - 2027 academic year on sabbatical at EPFL. He received the Ph.D. degree in 2009 and the M.S. degree in 2005 from the University of California, Berkeley, as well as the B.S. degree in 2003 from Rice University, all in electrical engineering. He is a past recipient of the IEEE Communications Society & Information Theory Society Joint Paper Award, the NSF CAREER Award, the Eli Jury Award, and the Gerald and Deanne Gitner Family Award for Innovation in Teaching with Technology.
More information
Practical information
- General public
- Free
Contact
- Host: Michael Gastpar