Signal estimation with additive error metrics in compressed sensing

Compressed sensing typically deals with the estimation of a system input from its noise-corrupted linear mea-surements, where the number of measurements is smaller than the number of input components. The performance of the estimation process is usually quantified by some standard error metric such as squared error or support set error. In this correspondence, we consider a noisy compressed sensing problem with any additive error metric. Under the assumption that the relaxed belief propagation method matches Tanaka’s fixed point equation, we propose a general algorithm that estimates the original signal by minimizing the additive error metric defined by the user. The algorithm is a pointwise estimation process, and thus simple and fast. We verify that our algorithm is asymptotically optimal, and we describe a general method to compute the fundamental information-theoretic performance limit for any additive error metric. We provide several example metrics, and give the theoretical performance limits for these cases. Experimental results show that our algorithm outperforms methods such as relaxed belief propagation (relaxed BP) and compressive sampling matching pursuit (CoSaMP), and reaches the suggested theoretical limits for our example metrics