1301.0901 (Florent Krzakala et al.)

Compressed Sensing under Matrix Uncertainty: Optimum Thresholds and
Robust Approximate Message Passing    [PDF]

Florent Krzakala, Marc Mézard, Lenka Zdeborová

In compressed sensing one measures sparse signals directly in a compressed form via a linear transform and then reconstructs the original signal. However, it is often the case that the linear transform itself is known only approximately, a situation called matrix uncertainty, and that the measurement process is noisy. Here we present two contributions to this problem: first, we use the replica method to determine the mean-squared error of the Bayes-optimal reconstruction of sparse signals under matrix uncertainty. Second, we consider a robust variant of the approximate message passing algorithm and demonstrate numerically that in the limit of large systems, this algorithm matches the optimal performance in a large region of parameters.

View original: http://arxiv.org/abs/1301.0901