Bayesian approximate message passing (BAMP) is an efficient method in compressed sensing that is nearly optimal in the minimum mean squared error (MMSE) sense. Multiple measurement vector (MMV)-BAMP performs joint recovery of multiple vectors with identical support and accounts for correlations in the signal of interest and in the noise. In this paper, we show how to reduce the complexity of vector BAMP via a simple joint decorrelation (diagonalization) transform of the signal and noise vectors, which also facilitates the subsequent performance analysis. We prove that the corresponding state evolution is equivariant with respect to the joint decorrelation transform and preserves diagonality of the residual noise covariance for the Bernoulli–Gauss prior. We use these results to analyze the dynamics and the mean squared error (MSE) performance of BAMP via the replica method, and thereby understand the impact of signal correlation and number of jointly sparse signals. Finally, we evaluate an application of MMV-BAMP for single-pixel imaging with correlated color channels and thereby explore the performance gain of joint recovery compared to conventional BAMP reconstruction as well as group lasso.
@cite_18: 
@cite_7: Approximate message passing (AMP) is a class of efficient algorithms for solving high-dimensional linear regression tasks where one wishes to recover an unknown signal βο from noisy, linear measurements y = Αβ 0 + w. When applying a separable denoiser at each iteration, the performance of AMP (for example, the mean squared error of its estimates) can be accurately tracked by a simple, scalar iteration referred to as state evolution. Although separable denoisers are sufficient if the unknown signal has independent and identically distributed entries, in many real-world applications, like image or audio signal reconstruction, the unknown signal contains dependencies between entries. In these cases, a coordinate-wise independence structure is not a good approximation to the true prior of the unknown signal. In this paper we assume the unknown signal has dependent entries, and using a class of non-separable sliding-window denoisers, we prove that a new form of state evolution still accurately predicts AMP performance. This is an early step in understanding the role of non-separable denoisers within AMP, and will lead to a characterization of more general denoisers in problems including compressive image reconstruction.
@cite_28: 
@cite_39: Given a high-dimensional data matrix @math , Approximate Message Passing (AMP) algorithms construct sequences of vectors @math , @math , indexed by @math by iteratively applying @math or @math , and suitable non-linear functions, which depend on the specific application. Special instances of this approach have been developed --among other applications-- for compressed sensing reconstruction, robust regression, Bayesian estimation, low-rank matrix recovery, phase retrieval, and community detection in graphs. For certain classes of random matrices @math , AMP admits an asymptotically exact description in the high-dimensional limit @math , which goes under the name of state evolution.' Earlier work established state evolution for separable non-linearities (under certain regularity conditions). Nevertheless, empirical work demonstrated several important applications that require non-separable functions. In this paper we generalize state evolution to Lipschitz continuous non-separable nonlinearities, for Gaussian matrices @math . Our proof makes use of Bolthausen's conditioning technique along with several approximation arguments. In particular, we introduce a modified algorithm (called LAMP for Long AMP) which is of independent interest.
@cite_47: The standard linear regression (SLR) problem is to recover a vector x0 from noisy linear observations y = Ax0 + w. The approximate message passing (AMP) algorithm recently proposed by Donoho, Maleki, and Montanari is a computationally efficient iterative approach to SLR that has a remarkable property: for large i.i.d. sub-Gaussian matrices A, its periteration behavior is rigorously characterized by a scalar stateevolution whose fixed points, when unique, are Bayes optimal. AMP, however, is fragile in that even small deviations from the i.i.d. sub-Gaussian model can cause the algorithm to diverge. This paper considers a “vector AMP” (VAMP) algorithm and shows that VAMP has a rigorous scalar state-evolution that holds under a much broader class of large random matrices A: those that are right-rotationally invariant. After performing an initial singular value decomposition (SVD) of A, the per-iteration complexity of VAMP is similar to that of AMP. In addition, the fixed points of VAMP's state evolution are consistent with the replica prediction of the minimum mean-squared error recently derived by Tulino, Caire, Verdu, and Shamai.
@cite_16: In a recent paper, the authors proposed a new class of low-complexity iterative thresholding algorithms for reconstructing sparse signals from a small set of linear measurements [1]. The new algorithms are broadly referred to as AMP, for approximate message passing. This is the first of two conference papers describing the derivation of these algorithms, connection with the related literature, extensions of the original framework, and new empirical evidence. In particular, the present paper outlines the derivation of AMP from standard sum-product belief propagation, and its extension in several directions. We also discuss relations with formal calculations based on statistical mechanics methods.
@cite_17: The paper quantifies and compares the exact asymptotic performance of multiple measurement vector (MMV) and distributed sensing (DS) models. Both models assume multiple measurement instances yk = Akxk + wk, k = 1, 2, …, K. The difference is that MMV involves identical measurement matrices whereas DS allows different matrices for different measurement instances. It has been recognized that DS works better than MMV empirically. However, the quantification of the performance difference is not available in the literature. Our contribution is to quantify the asymptotic performance of MMV and DS in the asymptotic regime that the dimensions of the measurement matrices approach infinity proportionally but the number of measurement instances K remains a constant. The case study and numerical results justify the accuracy of the performance quantification. The analysis technique is based on the state evolution for approximate message passing.
The se formalism developed in @cite_16 @cite_18 @cite_28 analytically predicts the recovery performance of (B) amp algorithms. se was employed to analyze bamp for joint sparsity with a vector estimator and to point out the difference between the dcs and mmv scenarios in @cite_17 . Recent works rigorously prove the se for non-separable non-linearities @cite_39 and a class of sliding-window denoisers @cite_7 with Gaussian i.i.d. measurement matrices. Furthermore, the se of the Vector AMP has been derived for a large class of right orthogonally invariant random sensing matrices @cite_47 . (We highlight that the acronym Vector AMP should not to be confused with the vector-prior version of BAMP, considered in this paper for the MMV DCS problems.)