Universality of approximate message passing algorithms

Wei Kuo Chen; Wai-Kit Lam

doi:10.1214/21-EJP604

Universality of approximate message passing algorithms

Wei Kuo Chen
, Wai-Kit Lam

School of Mathematics

Research output: Contribution to journal › Article › peer-review

34 Scopus citations

Abstract

We consider a broad class of Approximate Message Passing (AMP) algorithms defined as a Lipschitzian functional iteration in terms of an n × n random symmetric matrix A. We establish universality in noise for this AMP in the n-limit and validate this behavior in a number of AMPs popularly adapted in compressed sensing, statistical inferences, and optimizations in spin glasses.

Original language	English (US)
Article number	36
Journal	Electronic Journal of Probability
Volume	26
DOIs	https://doi.org/10.1214/21-EJP604
State	Published - Mar 23 2021

Bibliographical note

Funding Information:
*University of Minnesota. Partially supported by NSF grant DMS-17-52184. E-mail: [email protected] †University of Minnesota. E-mail: [email protected]

Publisher Copyright:
© 2021, Institute of Mathematical Statistics. All rights reserved.

Keywords

Message passing
Spike recovery
Spiked random matrix
Universality

Publisher link

10.1214/21-EJP604

Find It

Find It at U of M Libraries

Cite this

@article{72ad7b38dbf140fa8161885e2d595688,

title = "Universality of approximate message passing algorithms",

abstract = "We consider a broad class of Approximate Message Passing (AMP) algorithms defined as a Lipschitzian functional iteration in terms of an n × n random symmetric matrix A. We establish universality in noise for this AMP in the n-limit and validate this behavior in a number of AMPs popularly adapted in compressed sensing, statistical inferences, and optimizations in spin glasses.",

keywords = "Message passing, Spike recovery, Spiked random matrix, Universality",

author = "Chen, \{Wei Kuo\} and Wai-Kit Lam",

note = "Funding Information: *University of Minnesota. Partially supported by NSF grant DMS-17-52184. E-mail: [email protected] †University of Minnesota. E-mail: [email protected] Publisher Copyright: {\textcopyright} 2021, Institute of Mathematical Statistics. All rights reserved.",

year = "2021",

month = mar,

day = "23",

doi = "10.1214/21-EJP604",

language = "English (US)",

volume = "26",

journal = "Electronic Journal of Probability",

issn = "1083-6489",

publisher = "Institute of Mathematical Statistics",

}

TY - JOUR

T1 - Universality of approximate message passing algorithms

AU - Chen, Wei Kuo

AU - Lam, Wai-Kit

N1 - Funding Information: *University of Minnesota. Partially supported by NSF grant DMS-17-52184. E-mail: [email protected] †University of Minnesota. E-mail: [email protected] Publisher Copyright: © 2021, Institute of Mathematical Statistics. All rights reserved.

PY - 2021/3/23

Y1 - 2021/3/23

N2 - We consider a broad class of Approximate Message Passing (AMP) algorithms defined as a Lipschitzian functional iteration in terms of an n × n random symmetric matrix A. We establish universality in noise for this AMP in the n-limit and validate this behavior in a number of AMPs popularly adapted in compressed sensing, statistical inferences, and optimizations in spin glasses.

AB - We consider a broad class of Approximate Message Passing (AMP) algorithms defined as a Lipschitzian functional iteration in terms of an n × n random symmetric matrix A. We establish universality in noise for this AMP in the n-limit and validate this behavior in a number of AMPs popularly adapted in compressed sensing, statistical inferences, and optimizations in spin glasses.

KW - Message passing

KW - Spike recovery

KW - Spiked random matrix

KW - Universality

UR - https://www.scopus.com/pages/publications/85106914762

UR - https://www.scopus.com/pages/publications/85106914762#tab=citedBy

U2 - 10.1214/21-EJP604

DO - 10.1214/21-EJP604

M3 - Article

AN - SCOPUS:85106914762

SN - 1083-6489

VL - 26

JO - Electronic Journal of Probability

JF - Electronic Journal of Probability

M1 - 36

ER -

Universality of approximate message passing algorithms

Abstract

Bibliographical note

Keywords

Publisher link

Find It

Other files and links

Fingerprint

Cite this