A system and method for image and video compression using compressive sensing is provided. An embodiment method for compressing an image having a plurality of image blocks includes selecting an image block from the plurality of image blocks to compress, computing a sum of sinusoidal signals at different frequencies and amplitudes representation for the selected image block, quantizing the amplitudes of the sinusoidal signals at different frequencies, and saving the quantized amplitudes as a first compressed image block. The method also includes truncating the quantized amplitudes, thereby producing truncated quantized amplitudes, saving the truncated quantized amplitudes as a second compressed image block, and selecting either the first compressed image block or the second compressed image block as a final compressed image block. The selecting is based on a measure of the quality of the first compressed image block and the second compressed image block.