We consider lossy compression of image sequences using l1-compression with overcomplete dictionaries. As a fidelity measure for the reconstruction quality, we incorporate the recently proposed structural similarity index measure, and we show that this leads to problem formulations that are very similar to conventional l1 compression algorithms. In addition, we develop efficient large-scale algorithms used for joint encoding of multiple image frames.