Graph-based Approximate Message Passing Iterations
This work provides a foundational framework for high-dimensional statistical inference, benefiting researchers by simplifying the analysis and development of new AMP iterations, though it is incremental in building upon existing AMP theory.
The paper tackles the problem of unifying various approximate message passing (AMP) algorithms under a common framework and providing a modular proof for their state evolution equations, showing that AMP instances can be indexed by an oriented graph and extending the reach of previous proofs to include non-separable functions and recent heuristic derivations.
Approximate-message passing (AMP) algorithms have become an important element of high-dimensional statistical inference, mostly due to their adaptability and concentration properties, the state evolution (SE) equations. This is demonstrated by the growing number of new iterations proposed for increasingly complex problems, ranging from multi-layer inference to low-rank matrix estimation with elaborate priors. In this paper, we address the following questions: is there a structure underlying all AMP iterations that unifies them in a common framework? Can we use such a structure to give a modular proof of state evolution equations, adaptable to new AMP iterations without reproducing each time the full argument ? We propose an answer to both questions, showing that AMP instances can be generically indexed by an oriented graph. This enables to give a unified interpretation of these iterations, independent from the problem they solve, and a way of composing them arbitrarily. We then show that all AMP iterations indexed by such a graph admit rigorous SE equations, extending the reach of previous proofs, and proving a number of recent heuristic derivations of those equations. Our proof naturally includes non-separable functions and we show how existing refinements, such as spatial coupling or matrix-valued variables, can be combined with our framework.