Generalized Approximate Survey Propagation for High-Dimensional Estimation
This addresses robustness issues in high-dimensional estimation for applications like phase retrieval, though it is incremental as it builds on existing GAMP methods.
The paper tackles the problem of signal estimation in Generalized Linear Estimation (GLE) when there is a mismatch between assumed and true models, proposing Generalized Approximate Survey Propagation (GASP) to improve performance, showing it reduces the reconstruction threshold and approaches Bayesian optimality in phase retrieval.
In Generalized Linear Estimation (GLE) problems, we seek to estimate a signal that is observed through a linear transform followed by a component-wise, possibly nonlinear and noisy, channel. In the Bayesian optimal setting, Generalized Approximate Message Passing (GAMP) is known to achieve optimal performance for GLE. However, its performance can significantly degrade whenever there is a mismatch between the assumed and the true generative model, a situation frequently encountered in practice. In this paper, we propose a new algorithm, named Generalized Approximate Survey Propagation (GASP), for solving GLE in the presence of prior or model mis-specifications. As a prototypical example, we consider the phase retrieval problem, where we show that GASP outperforms the corresponding GAMP, reducing the reconstruction threshold and, for certain choices of its parameters, approaching Bayesian optimal performance. Furthermore, we present a set of State Evolution equations that exactly characterize the dynamics of GASP in the high-dimensional limit.