Compressed sensing can be a valuable method with which to acquire high-resolution images, reducing the stored amount of information. This objective may be pursued without using any prior knowledge of the images, unlike the standard information compression algorithms do. Information compression can be obtained by a simple matrix multiplication, but the process of reconstructing the original image could be very expensive in terms of computation requirements. We are interested in comparing different reconstruction techniques for compressed air-to-air inverse synthetic aperture radar images, looking for a sensible compromise between performance results and complexity. In more detail, the compared algorithms are iterative thresholding, basis pursuit and convex optimization. Furthermore, particular attention has been devoted to a more appropriate way of splitting large-sized images in order to obtain smaller matrices with uniform sparseness for reducing the computational load.