Approximate message passing algorithm for complex separable compressed imaging

We propose the approximate message passing (AMP) algorithm for complex separable compressed imaging. The standard formulation of compressed sensing uses one-dimensional signals while images are usually reshaped into such vectors by raster scan, which requires a huge matrix. In separable cases like discrete Fourier transform (DFT), however, sensing processes can be formulated using two moderate size matrices which are multiplied to images from the both sides. We exploit this formulation in our AMP algorithm. Since we suppose DFT for the sensing process, in which measurements are complex, our formulation applies to cases in which both target signals and measurements are complex. We show that the proposed algorithm perfectly reconstructs a 128×128 image, which could not be handled by the raster scan approach on the same computational environment. We also show that the compression rate of the proposed algorithm is mostly same as the so-called weak threshold.