MultiD-AMP: match up Accuracy and Fast Computation by Dynamically Denoising Data

Denoising-AMP (D-AMP) can be viewed as an iterative algorithm where at each iteration a non-linear denoising function is applied to the signal estimate. D-AMP algorithm has been analysed in terms of inferential accuracy without considering computational complexity. This is an important missing aspect since the denoising is often the computational bottleneck in the D-AMP reconstruction. The approach that it is proposed in this work is different; we aim to design a mechanism for leveraging a hierarchy denoising models (MultiD-AMP) in order to minimize the overall complexity given the expected risk, i.e. the estimation error. The intuition comes from the observation that at earlier iteration, when the estimate is far according to some distance to the true signal, the algorithm does not need a complicated denoiser, since the structure of the signal is poor, but faster denoisers and this leads to the idea of defining a family/hierarchy of denoisers of increased complexity.
The main challenge is to define a switching scheme which is based on the empirical finding that in MultiD-AMP we can predict exactly, in the large system limit, the evolution of the Mean Square Error. We can exploit the State Evolution, evaluated on a set of training images, to find a proper switching strategy. The proposed framework has been tested on i.i.d. random Gaussian measurements with Gaussian noise and for deconvolution problem. The results show the effectiveness of the proposed reconstruction algorithm.