†Anybody Technology A/S

We consider the problem of lossy compression of images using sparse representations from overcomplete dictionaries. This prob-lem is in principle easy to solve using standard algorithms for convex programming, but often the large dimensions render such an approach intractable. We present a highly efficient method based on recently developed first-order methods, which enables us to com-pute sparse approximations of entire images with modest time and memory consumption. Index Terms — Basis pursuit, sparse approximations, image compression, convex optimization, first-order optimization algo-rithms. 1