a method and apparatus encode and decode a video that has been encoded with minimal computations . a first plurality of random measurements is taken for a first frame at an encoder . a subsequent plurality of random measurements is taken for each subsequent frame at the encoder such that the first plurality of random measurements is greater than each subsequent plurality of random measurements . each plurality of random measurements is encoded into a bitstream . the encoded bitstream , which includes a current input frame , is received at a decoder . a sparse recovery is performed on the current input frame to generate an initial version of a currently reconstructed frame based on the current input frame . at least one subsequent version of the currently reconstructed frame is generated based on a last version of the currently reconstructed frame , such that each subsequent version has a higher image quality than the last version .