A Theory of Solving TAP Equations for Ising Models with General Invariant Random Matrices

Abstract

We consider the problem of solving TAP mean field equations by iteration for Ising model with coupling matrices that are drawn at random from general invariant ensembles. We develop an analysis of iterative algorithms using a dynamical functional approach that in the thermodynamic limit yields an effective dynamics of a single variable trajectory. Our main novel contribution is the expression for the implicit memory term of the dynamics for general invariant ensembles. By subtracting these terms, that depend on magnetizations at previous time steps, the implicit memory terms cancel making the iteration dependent on a Gaussian distributed field only. The TAP magnetizations are stable fixed points if an AT stability criterion is fulfilled. We illustrate our method explicitly for coupling matrices drawn from the random orthogonal ensemble.

arXiv comment27 pages, 6 Figures Published in Journal of Physics A: Mathematical and Theoretical, Volume 49, Number 11, 2016

References in corpus (10)

• Message Passing Algorithms for Compressed Sensing
• Expectation Propagation for approximate Bayesian inference
• The dynamics of message passing on dense graphs, with applications to compressed sensing
• Integration with respect to the Haar measure on unitary, orthogonal and symplectic group
• On the Out of Equilibrium Relaxation of the Sherrington - Kirkpatrick model
• Universality in polytope phase transitions and message passing algorithms
• Replica Field Theory for Deterministic Models (II): A Non-Random Spin Glass with Glassy Behavior
• Probabilistic Reconstruction in Compressed Sensing: Algorithms, Phase Diagrams, and Threshold Achieving Matrices
• Mean-Field Equations for Spin Models with Orthogonal Interaction Matrices
• On some properties of orthogonal Weingarten functions

Cited by in corpus (26)

• Statistical physics of inference: Thresholds and algorithms
• Analysis of Regularized LS Reconstruction and Random Matrix Ensembles in Compressed Sensing
• High-temperature Expansions and Message Passing Algorithms
• Mean-field inference methods for neural networks
• Generalized Turbo Signal Recovery for Nonlinear Measurements and Orthogonal Sensing Matrices
• Mean-field theory of graph neural networks in graph partitioning
• Perturbative construction of mean-field equations in extensive-rank matrix factorization and denoising
• Memory-free dynamics for the TAP equations of Ising models with arbitrary rotation invariant ensembles of random coupling matrices
• PCA Initialization for Approximate Message Passing in Rotationally Invariant Models
• A statistical physics approach to learning curves for the Inverse Ising problem
• A Dynamical Mean-Field Theory for Learning in Restricted Boltzmann Machines
• Macroscopic Analysis of Vector Approximate Message Passing in a Model Mismatch Setting
• The replica-symmetric free energy for Ising spin glasses with orthogonally invariant couplings
• Approximate Message Passing for orthogonally invariant ensembles: Multivariate non-linearities and spectral initialization
• Self-Averaging Expectation Propagation
• Gardner formula for Ising perceptron models at small densities
• Exact solution to the random sequential dynamics of a message passing algorithm
• Analysis of Bayesian Inference Algorithms by the Dynamical Functional Approach
• Memory Approximate Message Passing
• Dynamical mean field approach to associative memory model with non-monotonic transfer functions
• Bayes-Optimal Convolutional AMP
• Approximate cross-validation formula for Bayesian linear regression
• Statistical physics of deep learning: Optimal learning of a multi-layer perceptron near interpolation
• Statistical mechanics of extensive-width Bayesian neural networks near interpolation
• Optimal generalisation and learning transition in extensive-width shallow neural networks near interpolation
• Linear Operator Approximate Message Passing (OpAMP)