Log-squared computation and communication cost for Pareto-optimal MP-AMP

Let $T$ be the number of MP-AMP iterations, let $R_{agg}$ be the aggregate coding rate, and let $\text{MSE}$ and $\text{MMSE}$ denote the mean squared error and minimum mean squared error, respectively. Define the excess MSE by

$$\text{EMSE}^*=\text{MSE}^*-\text{MMSE}.$$

MP-AMP cost conjecture. The total computation and communication cost scales as

$$O\left(\log^2\left(1/\text{EMSE}^*\right)\right).$$

This conjecture follows the proposed geometric decay of the quantization error and Pareto-optimal excess MSE with the iteration number, together with the aggregate-rate definition. The paper presents this as an asymptotic prediction for MP-AMP as the MSE approaches the MMSE and does not provide a proof.