Generalized Approximate Survey Propagation for High-Dimensional Estimation

Abstract

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.

References in corpus (20)

• Message Passing Algorithms for Compressed Sensing
• Phase Retrieval via Wirtinger Flow: Theory and Algorithms
• The dynamics of message passing on dense graphs, with applications to compressed sensing
• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• The structural glass transition and the entropy of the metastable states
• Glass and Jamming Transitions: From Exact Results to Finite-Dimensional Descriptions
• Compressive Phase Retrieval via Generalized Approximate Message Passing
• Optimal Errors and Phase Transitions in High-Dimensional Generalized Linear Models
• A Geometric Analysis of Phase Retrieval
• Phase transitions and sample complexity in Bayes-optimal matrix factorization
• Mean-field message-passing equations in the Hopfield model and its generalizations
• Optimal Spectral Initialization for Signal Recovery with Applications to Phase Retrieval
• Complex energy landscapes in spiked-tensor and simple glassy models: ruggedness, arrangements of local minima and phase transitions
• Typology of phase transitions in Bayesian inference problems
• Glassy nature of the hard phase in inference problems
• Statistical Mechanics of High-Dimensional Inference
• Approximate Survey Propagation for Statistical Inference
• Phase Retrieval From Binary Measurements
• Approximate Message Passing for Amplitude Based Optimization
• Fundamental Limits of PhaseMax for Phase Retrieval: A Replica Analysis