Vector Approximate Survey Propagation

Approximate Message Passing (AMP), originally designed to solve high-dimensional linear inverse problems, has found broad applications in signal processing and statistical inference. Among its key variants, Vector Approximate Message Passing (VAMP) and Generalized Approximate Survey Propagation (GASP) have demonstrated effectiveness even in scenarios where the assumed generative models differ from the true models. However, the maximum a posteriori (MAP) versions of VAMP and GASP have limitations: VAMP is restricted to differentiable priors and likelihoods, while GASP requires the elements of measurement matrix be independent identically distributed (i.i.d.). To overcome these limitations, this paper introduces Vector Approximate Survey Propagation (VASP), a new algorithm that utilizes survey propagation to handle non-differentiable priors and likelihoods and employs vector-form messages to account for correlations among the measurement matrix elements. Simulations reveal that VASP significantly surpasses VAMP and GASP in estimation accuracy, particularly when the assumed prior is discrete-supported and the measurement matrix is non-i.i.d. Additionally, a set of state evolution (SE) recursion, derived heuristically, accurately reflects the per-iteration mean squared error (MSE) of the VASP. A comparison between this SE and the free energy computed by Takahashi and Kabashima under the one-step replica symmetry breaking (1RSB) ansatz shows that the SE’s fixed point equations are exactly the same as the free energy’s saddle point equations, thus suggesting in the large system limits, VASP can efficiently approximate the postulated MAP estimator (which is computationally NP-hard in the worst case) with only cubic complexity, provided that the 1RSB ansatz of the free energy is valid.