Bocconi Team Proves Structured Matrices Can Replace Random Ones in AMP Algorithms
Four researchers prove a nearly 30-year-old conjecture about structured matrices and introduce a unified AMP iteration that works on random and deterministic inputs alike.
ProTakeaways
- New theoretical paper proves universality of first-order iterative methods on structured deterministic matrices.
- Resolves parts of a nearly 30-year-old conjecture from Marinari, Parisi, and Ritort about Fourier-type couplings.
- Analysis uses traffic distributions and diagrammatic expansions over cactus and treelike graphs.
- New treelike AMP iteration unifies Orthogonal AMP and Generalized AMP under one framework.
- Provides the first combinatorial interpretation of the Onsager correction term.
- Covers Walsh-Hadamard, discrete sine, and discrete cosine transform matrices, which are used in compressed sensing.
A team from Bocconi, UC Davis, Johns Hopkins, and ETH Zürich has released a lengthy theoretical paper that closes a long-standing gap in the analysis of iterative algorithms on structured matrices. The work proves that general first-order methods behave the same way on certain deterministic matrices (Walsh-Hadamard, discrete sine, discrete cosine transforms) as they do on random ones, and introduces a new approximate message passing (AMP) iteration that unifies several previous variants under a single combinatorial framework.
AMP-style algorithms are the workhorses behind many high-dimensional inference pipelines, compressed sensing decoders, and spin-glass optimizers. Their sharp asymptotic guarantees have historically been proved only for very specific random matrix models, which is why extending them to structured, deterministic inputs is a substantive advance.
GFOM and AMP in one page
General first-order methods (GFOM) are a flexible class of iterative algorithms that update a state vector by matrix-vector multiplications and entrywise nonlinearities. Think of them as a nonlinear power method: alternate between multiplying by a matrix and applying a coordinate-wise function. This structure captures many types of gradient descent and message passing procedures, and the alternation of linear and nonlinear steps also resembles the layer structure of a feedforward network.
Approximate message passing is the special case where the state vector stays asymptotically Gaussian as the dimension grows. That Gaussianity is what makes AMP so useful: it collapses the full high-dimensional dynamics into a small set of scalar equations called state evolution, giving practitioners exact predictions for mean-squared error, phase transitions, and optimal denoisers.