Adaptive damping and mean removal for the generalized approximate message passing algorithm

Jeremy Vila; Philip Schniter; Sundeep Rangan; Florent Krzakala; Lenka Zdeborova

doi:10.1109/ICASSP.2015.7178325

Adaptive damping and mean removal for the generalized approximate message passing algorithm

Jeremy Vila, Philip Schniter, Sundeep Rangan, Florent Krzakala, Lenka Zdeborova

Electrical and Computer Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

The generalized approximate message passing (GAMP) algorithm is an efficient method of MAP or approximate-MMSE estimation of x observed from a noisy version of the transform coefficients z = Ax. In fact, for large zero-mean i.i.d sub-Gaussian A, GAMP is characterized by a state evolution whose fixed points, when unique, are optimal. For generic A, however, GAMP may diverge. In this paper, we propose adaptive-damping and mean-removal strategies that aim to prevent divergence. Numerical results demonstrate significantly enhanced robustness to non-zero-mean, rank-deficient, column-correlated, and ill-conditioned A.

Original language	English (US)
Title of host publication	2015 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2015 - Proceedings
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	2021-2025
Number of pages	5
ISBN (Electronic)	9781467369978
DOIs	https://doi.org/10.1109/ICASSP.2015.7178325
State	Published - Aug 4 2015
Event	40th IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2015 - Brisbane, Australia Duration: Apr 19 2014 → Apr 24 2014

Publication series

Name	ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings
Volume	2015-August
ISSN (Print)	1520-6149

Other

Other	40th IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2015
Country/Territory	Australia
City	Brisbane
Period	4/19/14 → 4/24/14

Keywords

Approximate message passing
belief propagation
compressed sensing

ASJC Scopus subject areas

Software
Signal Processing
Electrical and Electronic Engineering

Access to Document

10.1109/ICASSP.2015.7178325

Cite this

Vila, J., Schniter, P., Rangan, S., Krzakala, F., & Zdeborova, L. (2015). Adaptive damping and mean removal for the generalized approximate message passing algorithm. In 2015 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2015 - Proceedings (pp. 2021-2025). Article 7178325 (ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings; Vol. 2015-August). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ICASSP.2015.7178325

Adaptive damping and mean removal for the generalized approximate message passing algorithm. / Vila, Jeremy; Schniter, Philip; Rangan, Sundeep et al.
2015 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2015 - Proceedings. Institute of Electrical and Electronics Engineers Inc., 2015. p. 2021-2025 7178325 (ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings; Vol. 2015-August).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Vila, J, Schniter, P, Rangan, S, Krzakala, F & Zdeborova, L 2015, Adaptive damping and mean removal for the generalized approximate message passing algorithm. in 2015 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2015 - Proceedings., 7178325, ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings, vol. 2015-August, Institute of Electrical and Electronics Engineers Inc., pp. 2021-2025, 40th IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2015, Brisbane, Australia, 4/19/14. https://doi.org/10.1109/ICASSP.2015.7178325

Vila J, Schniter P, Rangan S, Krzakala F, Zdeborova L. Adaptive damping and mean removal for the generalized approximate message passing algorithm. In 2015 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2015 - Proceedings. Institute of Electrical and Electronics Engineers Inc. 2015. p. 2021-2025. 7178325. (ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings). doi: 10.1109/ICASSP.2015.7178325

Vila, Jeremy ; Schniter, Philip ; Rangan, Sundeep et al. / Adaptive damping and mean removal for the generalized approximate message passing algorithm. 2015 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2015 - Proceedings. Institute of Electrical and Electronics Engineers Inc., 2015. pp. 2021-2025 (ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings).

@inproceedings{6adfd33b504343ab930066d41aa8b749,

title = "Adaptive damping and mean removal for the generalized approximate message passing algorithm",

abstract = "The generalized approximate message passing (GAMP) algorithm is an efficient method of MAP or approximate-MMSE estimation of x observed from a noisy version of the transform coefficients z = Ax. In fact, for large zero-mean i.i.d sub-Gaussian A, GAMP is characterized by a state evolution whose fixed points, when unique, are optimal. For generic A, however, GAMP may diverge. In this paper, we propose adaptive-damping and mean-removal strategies that aim to prevent divergence. Numerical results demonstrate significantly enhanced robustness to non-zero-mean, rank-deficient, column-correlated, and ill-conditioned A.",

keywords = "Approximate message passing, belief propagation, compressed sensing",

author = "Jeremy Vila and Philip Schniter and Sundeep Rangan and Florent Krzakala and Lenka Zdeborova",

note = "Publisher Copyright: {\textcopyright} 2015 IEEE.; 40th IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2015 ; Conference date: 19-04-2014 Through 24-04-2014",

year = "2015",

month = aug,

day = "4",

doi = "10.1109/ICASSP.2015.7178325",

language = "English (US)",

series = "ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "2021--2025",

booktitle = "2015 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2015 - Proceedings",

}

TY - GEN

T1 - Adaptive damping and mean removal for the generalized approximate message passing algorithm

AU - Vila, Jeremy

AU - Schniter, Philip

AU - Rangan, Sundeep

AU - Krzakala, Florent

AU - Zdeborova, Lenka

PY - 2015/8/4

Y1 - 2015/8/4

N2 - The generalized approximate message passing (GAMP) algorithm is an efficient method of MAP or approximate-MMSE estimation of x observed from a noisy version of the transform coefficients z = Ax. In fact, for large zero-mean i.i.d sub-Gaussian A, GAMP is characterized by a state evolution whose fixed points, when unique, are optimal. For generic A, however, GAMP may diverge. In this paper, we propose adaptive-damping and mean-removal strategies that aim to prevent divergence. Numerical results demonstrate significantly enhanced robustness to non-zero-mean, rank-deficient, column-correlated, and ill-conditioned A.

AB - The generalized approximate message passing (GAMP) algorithm is an efficient method of MAP or approximate-MMSE estimation of x observed from a noisy version of the transform coefficients z = Ax. In fact, for large zero-mean i.i.d sub-Gaussian A, GAMP is characterized by a state evolution whose fixed points, when unique, are optimal. For generic A, however, GAMP may diverge. In this paper, we propose adaptive-damping and mean-removal strategies that aim to prevent divergence. Numerical results demonstrate significantly enhanced robustness to non-zero-mean, rank-deficient, column-correlated, and ill-conditioned A.

KW - Approximate message passing

KW - belief propagation

KW - compressed sensing

UR - http://www.scopus.com/inward/record.url?scp=84946019396&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84946019396&partnerID=8YFLogxK

U2 - 10.1109/ICASSP.2015.7178325

DO - 10.1109/ICASSP.2015.7178325

M3 - Conference contribution

AN - SCOPUS:84946019396

T3 - ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings

SP - 2021

EP - 2025

BT - 2015 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2015 - Proceedings

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 40th IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2015

Y2 - 19 April 2014 through 24 April 2014

ER -

Adaptive damping and mean removal for the generalized approximate message passing algorithm

Abstract

Publication series

Other

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this