Data Here are the three test images, at multiple levels of compression in either dictionary. (Note that 0% compression does not necessarily lead to full recovery - this is a problem inherent in the dct basis. It would likely take more than twice as much data to represent the original image nearly perfectly.) We decided to run our algorithms on the three images with a non-redundant basis, just to see how the compressions compared.

Data Analysis Based on preliminary tests, we concluded that orthogonal matching pursuit produced approximations very similar to those generated by basis pursuit in a fraction of the time. However, varying the basis in our over-complete basis produced dramatic changes in our compressions, as did the inherent visual characteristics of the source image. These observations suggest that a wide spectrum of interesting results from orthogonal matching pursuit can be obtained by varying both the dictionaries and the original image. Our results show that for the three images, the basis that give the best representation with the most compression is the DFT-DCT basis, although compression in this manner often results in an unfortunate spectral artifact on images that exhibit sharp changes in color, a product of the DFT basis. The Dirac basis seemed best suited to picking out "lines" in the image, as we predicted. Interestingly, and as shown by the following graphs, the DCT basis dominated both overcomplete dictionaries, accounting for a vast majority of the compressed image - but the DFT/Dirac based vectors, however few there were, managed to make very significant changes to the overall apprearance of the final image. We also analyzed how frequently vectors from either basis were being selected, ie which basis was the most influential. (4 = 98% compressed, 16 = 87%, 64 = 50%, 128 = 100%)