Aspects of the subject matter described herein relate to image restoration for compressed images. In aspects, image restoration is accomplished by recovering spectral information from data corresponding to a compressed image. The spectral information is recovered using an algorithm to search through a solution space of possible solutions while constraints are imposed on the solution space to trim undesirable solutions from the space. An algorithm described herein may be iteratively applied to improve the quality of the recovered image.