Isn't this a case where entropy shows it isn't possible? Once you degrade the quality/quantity of the information, you can't get it back. You can find a clever way to hide what you did, but this doesn't add information, you're just interpolating. This isn't bad however, as we normally don't use all data we could (do you look at your pictures with 400% zoom factor?), and a rescaled image can highlight some detail you would have missed.

By the way, those bazillion dollars aren't wasted, because if you take the image, don't throw away pixels, but do as if it were a bigger image which had lost pixels, you can get something useful out of it.