turbo-GAMP joint channel-estimation/equalization/decoding

outline of the work:

• Generalized Approximate Message Passing (GAMP) is a powerful method to estimate an unknown i.i.d non-Gaussian vector from a (known) linear transformation of that vector observed through i.i.d probabilistic measurement channels. The algorithm was recently proposed by Sundeep Rangan, building on the Relaxed Belief Propagation (RBP) algorithm of Dongning Guo and Chih-Chun Wang, as well as on the AMP algorithm proposed by David Donoho, Arian Maleki, and Andrea Montanari and rigorously analyzed by Mohsen Bayati and Andrea Montanari.
  • S. Rangan, ``Generalized Approximate Message Passing for Estimation with Random Linear Mixing [arxiv],'' posted on arXiv 25 Oct. 2010.
  • M. Bayati and A. Montanari, ``The dynamics of message passing on dense graphs, with applications to compressed sensing [IEEExplore],'' IEEE Transactions on Information Theory, vol. 57, no. 2, pp. 764-785, Feb. 2011.
  • D. Donoho, A. Maleki, and A. Montanari, ``Message Passing Algorithms for Compressed Sensing [arXiv],'' Proc. Natl. Acad. Sci., 2009.
  • D. Guo and C.-C. Wang, ``Random sparse linear systems observed via arbitrary channels: A decoupling principle [IEEExplore],'' Proc. IEEE International Symposium on Information Theory, (Nice, France), June 2007.

• turbo-(G)AMP, proposed by the author, is a framework that extends (G)AMP to problems with non-identical non-independent (e.g., "structured sparse") signals and non-identical non-independent probabilistic measurement channels.
  • P. Schniter, ``Turbo-AMP: A Graphical-Models Approach to Compressive Inference [slides],'' presented at Stanford University, Dec. 2010.
  • P. Schniter, ``Turbo Reconstruction of Structured Sparse Signals [pdf with typos corrected],'' Proc. Conf. on Information Sciences and Systems, (Princeton, NJ), Mar. 2010. [slides]
  • S. Som, L. C. Potter, and P. Schniter, ``On Approximate Message Passing for Reconstruction of Non-Uniformly Sparse Signals [pdf],'' Proc. National Aerospace and Electronics Conf., (Dayton, OH), July 2010.

• One very successful application of turbo-(G)AMP is joint channel-estimation/equalization/decoding of BICM-OFDM signals transmitted over channels with clustered-sparse impulse responses. The factor graph for this problem is shown below (for a toy problem size), along with an example of clustered-sparse channel-tap-magnitudes generated according to the method specified in the IEEE 802.15.4a UWB standard. This work has been detailed in:
  • P. Schniter, ``A Message-Passing Receiver for BICM-OFDM over Unknown Clustered-Sparse Channels [pdf][arxiv],'' IEEE Journal of Selected Topics in Signal Processing: Special Issue on Soft Detection for Wireless Transmission, vol. 5, no. 8, pp. 1462-1474, Dec. 2011.
  • P. Schniter, ``A Message-Passing Receiver for BICM-OFDM over Unknown Clustered-Sparse Channels [pdf],'' in Proc. IEEE Workshop on Signal Processing Advances in Wireless Communications, (San Francisco, CA), June 2011. [slides]

• In related work with Arun Pachai Kannu, we have derived fundamental information-theoretic limits of communication across sparse channels, In particular, we have established that, for an L-length S-sparse N-block-fading channel, the prelog factor of the high-SNR ergodic capacity equals 1-S/N. Since this depends on the sparsity S and not the length L, the effect of channel sparsity on link performance becomes clear.
  • A. P. Kannu and P. Schniter, ``On Communication over Unknown Sparse Frequency-Selective Block-Fading Channels [pdf][arxiv],'' IEEE Transactions on Information Theory, vol. 57, no. 10, pp. 6619-6632, Oct. 2011.
  • A. P. Kannu and P. Schniter, ``On Communication over Unknown Sparse Frequency-Selective Block-Fading Channels [pdf],'' in Proc. IEEE Symposium on Information Theory, (Saint-Petersburg, Russia), Aug. 2011.

• Subsequently, we demonstrated (empirically) that turbo-RBP/GAMP attains the aforementioned optimal pre-log factor, unlike any other sparse-channel-reconstruction approach of which we are aware. (In the published work, we used RBP, since GAMP had not yet been proposed at the time of writing. Subsequently, however, we have verified that GAMP works equally well, while being faster than RBP.)
  • P. Schniter, ``Belief-propagation-based joint channel estimation and decoding for spectrally efficient communication over unknown sparse channels [arxiv].'' Physical Communication: Special Issue in Compressive Sensing in Communications (Elsevier), doi:10.1016/j.phycom.2011.09.004, Oct. 2011.
  • P. Schniter, ``Achieving the Noncoherent Sparse-Channel's Capacity Prelog Factor: A Graphical-Model Approach [pdf],'' presented at the Workshop on Information Theory and Applications (ITA), (La Jolla, CA), Feb. 2011. (Invited.) [slides]
  • P. Schniter, ``Joint Estimation and Decoding for Sparse Channels via Relaxed Belief Propagation [pdf],'' Proc. Asilomar Conf. on Signals, Systems, and Computers (Pacific Grove, CA), Nov. 2010. (Invited.) [slides]

• We are currently working on extensions to the above methods, such as to time-varying channels with slowly varying support and amplitudes:
  • P. Schniter and D. Meng, ``A Message-Passing Receiver for BICM-OFDM over Unknown Time-Varying Sparse Channels,'' presented at the Allerton Conf. on Communication, Control, and Computing, (Monticello, IL), Sep. 2011. (Invited.) [slides]

• Another extension that we've recently investigated is joint channel-estimation/equalization/decoding of BICM-OFDM signals transmitted over channels with clustered-sparse impulsive noise, as occurs in power-line communications.
  • M. Nassar, P. Schniter, and B. Evans, ``A Factor-Graph Approach to Joint OFDM Channel Estimation and Decoding in Impulsive Noise Environments [arxiv],'' to appear in IEEE Transactions on Signal Processing.
  • M. Nassar, P. Schniter, and B. Evans, ``A Factor-Graph Approach to Joint OFDM Channel Estimation and Decoding in Impulsive Channels [arxiv],'' to appear in Proc. Asilomar Conf. on Signals, Systems, and Computers (Pacific Grove, CA), Nov. 2013.

matlab code:

• Matlab routines for turbo-GAMP for joint channel-estimation/equalization/decoding of BICM-OFDM signals transmitted over channels with clustered-sparse impulse responses are available here. (Before running this code for the first time, you must compile two .c files to .mex.) Our v2 release (10 Nov 2011) supports both 32-bit and 64-bit versions of Matlab!
• To run the turbo-GAMP code with the LASSO option enabled, you'll also need to download van den Berg and Friedlander's SPGL1 matlab code.

acknowledgements:

• This material is based upon work supported by the National Science Foundation under Grant Numbers CCF-1018368 and CCF-1218754.

back to phil's home page...