Optimality of approximate message passing for spiked matrix models with rotationally invariant noise

We study the problem of estimating a rank-one signal matrix from a noisy observed matrix corrupted by additive rotationally invariant noise. We develop a new class of approximate message passing algorithms for this problem and provide a simple and concise characterization of their dynamics in the high-dimensional limit. At each iteration, these algorithms leverage prior knowledge about the noise structure by applying a nonlinear matrix denoiser to the eigenvalues of the observed matrix, and utilize prior information regarding the signal structure by applying a nonlinear iterate denoiser to the previous iterates generated by the algorithm. We derive the optimal choices for both the matrix and iterate denoisers and demonstrate that the resulting algorithm achieves the lowest possible asymptotic estimation error among a broad class of iterative algorithms under a fixed iteration budget.