Approximate Message Passing for the Matrix Tensor Product Model
This work addresses a generalization of spiked matrix models for multi-type data, with applications in contextual models like covariate-assisted clustering, but it is incremental as it builds on existing AMP frameworks.
The paper tackles the problem of recovering latent variables from multiple types of pairwise observations in the matrix tensor product model by proposing an approximate message passing algorithm with optimal weighting, proving state evolution for non-separable functions to describe performance asymptotically and providing necessary and sufficient conditions for signal recovery based on singular values of a generalized signal-to-noise ratio operator.
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.