  Approximate Message Passing (AMP) algorithms have seen widespread use across
a variety of applications. However, the precise forms for their Onsager
corrections and state evolutions depend on properties of the underlying random
matrix ensemble, limiting the extent to which AMP algorithms derived for white
noise may be applicable to data matrices that arise in practice.
  In this work, we study more general AMP algorithms for random matrices $W$
that satisfy orthogonal rotational invariance in law, where $W$ may have a
spectral distribution that is different from the semicircle and Marcenko-Pastur
laws characteristic of white noise. The Onsager corrections and state
evolutions in these algorithms are defined by the free cumulants or rectangular
free cumulants of the spectral distribution of $W$. Their forms were derived
previously by Opper, \c{C}akmak, and Winther using non-rigorous dynamic
functional theory techniques, and we provide rigorous proofs.
  Our motivating application is a Bayes-AMP algorithm for Principal Components
Analysis, when there is prior structure for the principal components (PCs) and
possibly non-white noise. For sufficiently large signal strengths and any
non-Gaussian prior distributions for the PCs, we show that this algorithm
provably achieves higher estimation accuracy than the sample PCs.
