TY - GEN

T1 - Random sparse linear systems observed via arbitrary channels

T2 - 2007 IEEE International Symposium on Information Theory, ISIT 2007

AU - Guo, Dongning

AU - Wang, Chih Chun

PY - 2007

Y1 - 2007

N2 - This paper studies the problem of estimating the vector input to a sparse linear transformation based on the observation of the output vector through a bank of arbitrary independent channels. The linear transformation is drawn randomly from an ensemble with mild regularity conditions. The central result is a decoupling principle in the large-system limit. That is, the optimal estimation of each individual symbol in the input vector is asymptotically equivalent to estimating the same symbol through a scalar additive Gaussian channel, where the aggregate effect of the interfering symbols is tantamount to a degradation in the signal-to-noise ratio. The degradation is determined from a recursive formula related to the score function of the conditional probability distribution of the noisy channel. A sufficient condition is provided for belief propagation (BP) to asymptotically produce the a posteriori probability distribution of each input symbol given the output. This paper extends the authors' previous decoupling result for Gaussian channels to arbitrary channels, which was based on an earlier work of Montanari and Tse. Moreover, a rigorous justification is provided for the generalization of some results obtained via statical physics methods.

AB - This paper studies the problem of estimating the vector input to a sparse linear transformation based on the observation of the output vector through a bank of arbitrary independent channels. The linear transformation is drawn randomly from an ensemble with mild regularity conditions. The central result is a decoupling principle in the large-system limit. That is, the optimal estimation of each individual symbol in the input vector is asymptotically equivalent to estimating the same symbol through a scalar additive Gaussian channel, where the aggregate effect of the interfering symbols is tantamount to a degradation in the signal-to-noise ratio. The degradation is determined from a recursive formula related to the score function of the conditional probability distribution of the noisy channel. A sufficient condition is provided for belief propagation (BP) to asymptotically produce the a posteriori probability distribution of each input symbol given the output. This paper extends the authors' previous decoupling result for Gaussian channels to arbitrary channels, which was based on an earlier work of Montanari and Tse. Moreover, a rigorous justification is provided for the generalization of some results obtained via statical physics methods.

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

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

U2 - 10.1109/ISIT.2007.4557346

DO - 10.1109/ISIT.2007.4557346

M3 - Conference contribution

AN - SCOPUS:51649102816

SN - 1424414296

SN - 9781424414291

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 946

EP - 950

BT - Proceedings - 2007 IEEE International Symposium on Information Theory, ISIT 2007

Y2 - 24 June 2007 through 29 June 2007

ER -