Abstract
In compressed sensing, we wish to reconstruct a sparse sig- nal x from observed data y . In sparse coding, on the other hand, we wish to find a representation of an observed signal y as a sparse linear combination, with coefficients x, of elements from an overcomplete dic- tionary. While many algorithms are competitive at both problems when x is very sparse, it can be challenging to recover x when it is less sparse. We present the Difference Map, which excels at sparse recovery when sparseness is lower. The Difference Map out-performs the state of the art with reconstruction from random measurements and natural image reconstruction via sparse coding.