  We study the problem of estimating a rank one signal matrix from an observed
matrix generated by corrupting the signal with 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
exploit prior knowledge about the noise structure by applying a non-linear
matrix denoiser to the eigenvalues of the observed matrix and prior information
regarding the signal structure by applying a non-linear iterate denoiser to the
previous iterates generated by the algorithm. We exploit our result on the
dynamics of these algorithms to derive the optimal choices for the matrix and
iterate denoisers. We show that the resulting algorithm achieves the smallest
possible asymptotic estimation error among a broad class of iterative
algorithms under a fixed iteration budget.
