  The Approximate Message Passing (AMP) algorithm efficiently reconstructs
signals which have been sampled with large i.i.d. sub-Gaussian sensing
matrices. Central to AMP is its "state evolution", which guarantees that the
difference between the current estimate and ground truth (the "aliasing") at
every iteration obeys a Gaussian distribution that can be fully characterized
by a scalar. However, when Fourier coefficients of a signal with non-uniform
spectral density are sampled, such as in Magnetic Resonance Imaging (MRI), the
aliasing is intrinsically colored, AMP's scalar state evolution is no longer
accurate and the algorithm encounters convergence problems. In response, we
propose the Variable Density Approximate Message Passing (VDAMP) algorithm,
which uses the wavelet domain to model the colored aliasing. We present
empirical evidence that VDAMP obeys a "colored state evolution", where the
aliasing obeys a Gaussian distribution that can be fully characterized with one
scalar per wavelet subband. A benefit of state evolution is that Stein's
Unbiased Risk Estimate (SURE) can be effectively implemented, yielding an
algorithm with subband-dependent thresholding that has no free parameters. We
empirically evaluate the effectiveness of VDAMP on three variations of Fast
Iterative Shrinkage-Thresholding (FISTA) and find that it converges in around
10 times fewer iterations on average than the next-fastest method, and to a
comparable mean-squared-error.
