Estimation with random linear mixing, belief propagation and compressed sensing

Sundeep Rangan

doi:10.1109/CISS.2010.5464768

Estimation with random linear mixing, belief propagation and compressed sensing

Sundeep Rangan

Electrical and Computer Engineering

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

Abstract

We apply Guo and Wang's relaxed belief propagation (BP) method to the estimation of a random vector from linear measurements followed by a componentwise probabilistic measurement channel. The relaxed BP method is a Gaussian approximation of standard BP that offers significant computational savings for dense measurement matrices. The main contribution of this paper is to extend Guo and Wang's relaxed BP method and analysis to general (non-AWGN) output channels. Specifically, we present detailed equations for implementing relaxed BP for general channels and show that the relaxed BP has an identical asymptotic large sparse limit behavior as standard BP as predicted by the Guo and Wang's state evolution (SE) equations. Applications are presented to compressed sensing and estimation with bounded noise.

Original language	English (US)
Title of host publication	2010 44th Annual Conference on Information Sciences and Systems, CISS 2010
DOIs	https://doi.org/10.1109/CISS.2010.5464768
State	Published - 2010
Event	44th Annual Conference on Information Sciences and Systems, CISS 2010 - Princeton, NJ, United States Duration: Mar 17 2010 → Mar 19 2010

Publication series

Name	2010 44th Annual Conference on Information Sciences and Systems, CISS 2010

Other

Other	44th Annual Conference on Information Sciences and Systems, CISS 2010
Country/Territory	United States
City	Princeton, NJ
Period	3/17/10 → 3/19/10

Keywords

Belief propagation
Bounded noise
Compressed sensing
Density evolution
Non-Gaussian estimation
Sparsity

ASJC Scopus subject areas

Information Systems
Information Systems and Management

Access to Document

10.1109/CISS.2010.5464768

Cite this

Rangan, S 2010, Estimation with random linear mixing, belief propagation and compressed sensing. in 2010 44th Annual Conference on Information Sciences and Systems, CISS 2010., 5464768, 2010 44th Annual Conference on Information Sciences and Systems, CISS 2010, 44th Annual Conference on Information Sciences and Systems, CISS 2010, Princeton, NJ, United States, 3/17/10. https://doi.org/10.1109/CISS.2010.5464768

@inproceedings{a6b6a7ad21664231898b29d27fca48bd,

title = "Estimation with random linear mixing, belief propagation and compressed sensing",

abstract = "We apply Guo and Wang's relaxed belief propagation (BP) method to the estimation of a random vector from linear measurements followed by a componentwise probabilistic measurement channel. The relaxed BP method is a Gaussian approximation of standard BP that offers significant computational savings for dense measurement matrices. The main contribution of this paper is to extend Guo and Wang's relaxed BP method and analysis to general (non-AWGN) output channels. Specifically, we present detailed equations for implementing relaxed BP for general channels and show that the relaxed BP has an identical asymptotic large sparse limit behavior as standard BP as predicted by the Guo and Wang's state evolution (SE) equations. Applications are presented to compressed sensing and estimation with bounded noise.",

keywords = "Belief propagation, Bounded noise, Compressed sensing, Density evolution, Non-Gaussian estimation, Sparsity",

author = "Sundeep Rangan",

year = "2010",

doi = "10.1109/CISS.2010.5464768",

language = "English (US)",

isbn = "9781424474172",

series = "2010 44th Annual Conference on Information Sciences and Systems, CISS 2010",

booktitle = "2010 44th Annual Conference on Information Sciences and Systems, CISS 2010",

}

TY - GEN

T1 - Estimation with random linear mixing, belief propagation and compressed sensing

AU - Rangan, Sundeep

PY - 2010

Y1 - 2010

N2 - We apply Guo and Wang's relaxed belief propagation (BP) method to the estimation of a random vector from linear measurements followed by a componentwise probabilistic measurement channel. The relaxed BP method is a Gaussian approximation of standard BP that offers significant computational savings for dense measurement matrices. The main contribution of this paper is to extend Guo and Wang's relaxed BP method and analysis to general (non-AWGN) output channels. Specifically, we present detailed equations for implementing relaxed BP for general channels and show that the relaxed BP has an identical asymptotic large sparse limit behavior as standard BP as predicted by the Guo and Wang's state evolution (SE) equations. Applications are presented to compressed sensing and estimation with bounded noise.

AB - We apply Guo and Wang's relaxed belief propagation (BP) method to the estimation of a random vector from linear measurements followed by a componentwise probabilistic measurement channel. The relaxed BP method is a Gaussian approximation of standard BP that offers significant computational savings for dense measurement matrices. The main contribution of this paper is to extend Guo and Wang's relaxed BP method and analysis to general (non-AWGN) output channels. Specifically, we present detailed equations for implementing relaxed BP for general channels and show that the relaxed BP has an identical asymptotic large sparse limit behavior as standard BP as predicted by the Guo and Wang's state evolution (SE) equations. Applications are presented to compressed sensing and estimation with bounded noise.

KW - Belief propagation

KW - Bounded noise

KW - Compressed sensing

KW - Density evolution

KW - Non-Gaussian estimation

KW - Sparsity

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

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

U2 - 10.1109/CISS.2010.5464768

DO - 10.1109/CISS.2010.5464768

M3 - Conference contribution

AN - SCOPUS:77953688837

SN - 9781424474172

T3 - 2010 44th Annual Conference on Information Sciences and Systems, CISS 2010

BT - 2010 44th Annual Conference on Information Sciences and Systems, CISS 2010

T2 - 44th Annual Conference on Information Sciences and Systems, CISS 2010

Y2 - 17 March 2010 through 19 March 2010

ER -

Estimation with random linear mixing, belief propagation and compressed sensing

Abstract

Publication series

Other

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this