  A common goal in many research areas is to reconstruct an unknown signal x
from noisy linear measurements. Approximate message passing (AMP) is a class of
low-complexity algorithms that can be used for efficiently solving such
high-dimensional regression tasks. Often, it is the case that side information
(SI) is available during reconstruction. For this reason, a novel algorithmic
framework that incorporates SI into AMP, referred to as approximate message
passing with side information (AMP-SI), has been recently introduced. In this
work, we provide rigorous performance guarantees for AMP-SI when there are
statistical dependencies between the signal and SI pairs and the entries of the
measurement matrix are independent and identically distributed Gaussian. The
AMP-SI performance is shown to be provably tracked by a scalar iteration
referred to as state evolution. Moreover, we provide numerical examples that
demonstrate empirically that the SE can predict the AMP-SI mean square error
accurately.
