In recent years, it has come to light that many signal estimation and detection problems in
engineering, science, and statistics are significantly aided by modeling the signal as sparse
or compressible in some basis. By now, a relatively comprehensive theory has been
constructed for such signal models, yielding algorithms that give provably good performance
even when sampling far below the Nyquist rate. The structure of real-world signals often
goes beyond simple sparsity, though. For example, the wavelet coefficients of natural scenes
are not only sparse, but also show persistence across scales of a wavelet decomposition.
Similarly, the impulse responses of wideband communication channels are not only sparse, but
show clustering among dominant paths. Likewise, a cardiac MRI sequence shows both sparsity
and temporal coherence among frames. While recent work has shown some success in exploiting
such structures, we demonstrate that there is room for significant improvement. In fact, the
modeling of such structure is a somewhat delicate matter: if too little is assumed apriori,
the estimates will succumb to measurement uncertainties, but if too much is assumed apriori,
the resulting estimates can become severely biased. Also, many of the existing strategies
for structured-sparse signal recovery return only point estimates, whereas interval estimates
are required when the estimator output is used for, e.g., decision-making or classification
or control.
In this talk, we present a new Bayesian graphical-model framework for compressive inference
that we refer to as "turbo approximate message passing". Our approach builds on the recent
approximate message passing (AMP) algorithms of Donoho, Maleki, and Montanari, which yield a
state-of-the-art solution to the unstructured-sparse reconstruction problem. In particular,
we show that many structured compressive inference problems can be efficiently represented by
a large and densely connected factor graph that can be partitioned into several sub-graphs,
each of which can be treated individually by soft-input soft-output (SISO) inference
algorithms like AMP. By passing messages among these SISO blocks, in a scheme reminiscent of
turbo decoding, inference on the larger factor graph can be performed very efficiently. We
detail three example applications of turbo-AMP: 1) compressive imaging that exploits
persistence-across-scales, 2) compressive tracking of slowly time-varying signals, and 3)
joint estimation and decoding for communication over sparse channels. In all cases, the
turbo-AMP approach achieves state-of-the-art performance with very low implementational
complexity.