Orthogonal AMP for compressed sensing with unitarily-invariant matrices

Approximate message passing (AMP) is a low-cost iterative signal recovery algorithm for compressed sensing. For sensing matrices with independent identically distributed (IID) Gaussian entries, the performance of AMP can be asymptotically characterized by a simple scaler recursion called state evolution (SE). SE analysis shows that AMP can potentially approach the optimal minimum mean squared-error (MMSE) limit. However, SE may become unreliable for other matrix ensembles, especially for ill-conditioned ones. In this paper, we propose an orthogonal AMP (OAMP) algorithm based on de-correlated linear estimation (LE) and divergence-free non-linear estimation (NLE). The Onsager term in standard AMP vanishes as a result of the divergence-free constraint on NLE. We develop an SE procedure for OAMP and show numerically that the SE for OAMP is accurate for a wide range of sensing matrices, including IID Gaussian matrices, partial orthogonal matrices, and general unitarily-invariant matrices. We further derive optimized options for OAMP and show that the corresponding SE fixed point coincides with the optimal performance obtained via the replica method.