Approximate Message Passing With Consistent Parameter Estimation and Applications to Sparse Learning
- 19 March 2014
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 60 (5) , 2969-2985
Abstract
We consider the estimation of an independent and identically distributed (i.i.d.) (possibly non-Gaussian) vector x ∈ R n from measurements y ∈ R m obtained by a general cascade model consisting of a known linear transform followed by a probabilistic componentwise (possibly nonlinear) measurement channel. A novel method, called adaptive generalized approximate message passing (adaptive GAMP) is presented. It enables the joint learning of the statistics of the prior and measurement channel along with estimation of the unknown vector x. We prove that, for large i.i.d. Gaussian transform matrices, the asymptotic componentwise behavior of the adaptive GAMP is predicted by a simple set of scalar state evolution equations. In addition, we show that the adaptive GAMP yields asymptotically consistent parameter estimates, when a certain maximum-likelihood estimation can be performed in each step. This implies that the algorithm achieves a reconstruction quality equivalent to the oracle algorithm that knows the correct parameter values. Remarkably, this result applies to essentially arbitrary parametrizations of the unknown distributions, including nonlinear and non-Gaussian ones. The adaptive GAMP methodology thus provides a systematic, general and computationally efficient method applicable to a large range of linear-nonlinear models with provable guarantees.Keywords
All Related Versions
This publication has 36 references indexed in Scilit:
- Message-passing algorithms for compressed sensingProceedings of the National Academy of Sciences, 2009
- An Interior-Point Method for Large-Scale -Regularized Least SquaresIEEE Journal of Selected Topics in Signal Processing, 2007
- Spike-triggered neural characterizationJournal of Vision, 2006
- Randomly Spread CDMA: Asymptotics Via Statistical PhysicsIEEE Transactions on Information Theory, 2005
- Approximate Belief Propagation, Density Evolution, and Statistical Neurodynamics for CDMA Multiuser DetectionIEEE Transactions on Information Theory, 2005
- Sparse Bayesian Learning for Basis SelectionIEEE Transactions on Signal Processing, 2004
- A statistical-mechanics approach to large-system analysis of CDMA multiuser detectorsIEEE Transactions on Information Theory, 2002
- Iterative multiuser joint decoding: unified framework and asymptotic analysisIEEE Transactions on Information Theory, 2002
- Minimax risk overl p -balls forl p -errorProbability Theory and Related Fields, 1994
- DISTRIBUTION OF EIGENVALUES FOR SOME SETS OF RANDOM MATRICESMathematics of the USSR-Sbornik, 1967