Approximate Message Passing for the Matrix Tensor Product Model
Riccardo Rossetti Galen Reeves
We propose and analyze an approximate message passing (AMP) algorithm for the
matrix tensor product model, which is a generalization of the standard spiked
matrix models that allows for multiple types of pairwise observations over a
collection of latent variables. A key innovation for this algorithm is a method
for optimally weighing and combining multiple estimates in each iteration.
Building upon an AMP convergence theorem for non-separable functions, we prove
a state evolution for non-separable functions that provides an asymptotically
exact description of its performance in the high-dimensional limit. We leverage
this state evolution result to provide necessary and sufficient conditions for
recovery of the signal of interest. Such conditions depend on the singular
values of a linear operator derived from an appropriate generalization of a
signal-to-noise ratio for our model. Our results recover as special cases a
number of recently proposed methods for contextual models (e.g., covariate
assisted clustering) as well as inhomogeneous noise models.