We consider the problem of decoding a discrete signal of categorical
variables from the observation of several histograms of pooled subsets of it.
We present an Approximate Message Passing (AMP) algorithm for recovering the
signal in the random dense setting where each observed histogram involves a
random subset of entries of size proportional to n. We characterize the
performance of the algorithm in the asymptotic regime where the number of
observations $m$ tends to infinity proportionally to n, by deriving the
corresponding State Evolution (SE) equations and studying their dynamics. We
initiate the analysis of the multi-dimensional SE dynamics by proving their
convergence to a fixed point, along with some further properties of the
iterates. The analysis reveals sharp phase transition phenomena where the
behavior of AMP changes from exact recovery to weak correlation with the signal
as m/n crosses a threshold. We derive formulae for the threshold in some
special cases and show that they accurately match experimental behavior.

该研究利用近似信息传递算法和状态演化方程分析多维度动态，研究从多个汇总子集的直方图中恢复分类变量离散信号的问题，并揭示了 AMP 行为从精确恢复到弱相关与信号的锐利相变现象，通过一些特殊情况的公式推导，准确地展示了它们与实验行为的匹配。