Robust Sparse Coding and Compressed Sensing with the Difference Map

Will Landecker^{1, 2}, Rick Chartrand³, and Simon DeDeo^{2, 4}

¹Portland State University, USA

²Santa Fe Institute, USA

³Los Alamos National Laboratory, USA

⁴Indiana University, USA

Abstract. In compressed sensing, we wish to reconstruct a sparse signal 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 dictionary. 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.

Keywords: Sparse coding, compressed sensing

LNCS 8691, p. 315 ff.

Full article in PDF | BibTeX

lncs@springer.com
© Springer International Publishing Switzerland 2014