mattdm's statement "that blur is largely reversible if you do the exact same thing in reverse" raised the question in my mind. The rotation is a geometric transformation of the image that consist of a spatial transformation of the coordinates, and an intensity interpolation. If the rotation is not a multiple of 90 degrees then the interpolation algorithm plays a crucial role.
In such cases, if we use an averaging interpolation algorithm (e.g., bicubic) the operation is lossy*. But can we use a different approach (e.g., nearest neightbor interpolation) instead and have our rotated image "un-rotated"?
(*) It is only my feeling (I still cannot support it with a mathematical proof): as we cannot know for sure which pixel contributed to wich value, we cannot reverse the averaging. But I'm not confident that we cannot use probabilistic methods to accurately estimate the original values.
While I lack the required math skills, I have performed some tests myself (with gimp), but after anti-rotating, the images differ:
Test 1
Figure 1 - Source image (256x256)
Figure 2 - From left to right: a) image rotated 9,5 degrees clockwise; b) image rotated again 9,5 degrees anti-clockwise; and c) difference between images. For these operations I have used nearest neightbor interpolation. The images are downscaled after the operations to better fit this website layout.
Figure 3 - From left to right: a) image rotated 9,5 degrees clockwise; b) image rotated again 9,5 degrees anti-clockwise; and c) difference between images. For these operations I have used bicubic interpolation. The images are downscaled after the operations to better fit this website layout.
Test 2
Following @unapiedra's sugestion, I did a simpler test: rotating a 2x2 matrix. This case is uninteresting because depending upon the angle either all cells are rotated by the same angle, or no cell is rotated. That is, the rotation is always lossless.
So I tried again with a 3x3 matrix and a 30 degrees rotation:
Figure 4 - From left to right: a) source image; b) image rotated 30 degrees clockwise; c) image rotated 30 degrees anti-clockwise; d) difference. The images are upscaled to fit this website.
In this case, the differences are evident. The rotation is clearly lossy... But what happens if I upscale before the rotation?
Test 3
Figure 5 - From left to right: a) source image; b) image upscaled by a 6x factor; c) upscaled image rotated 30 degrees clockwise; d) image rotated 30 degrees anti-clockwise; e) downscaled transformed image; and f) diference (no difference). The images are upscaled to fit this website.
In this case, I'm upscaling by a 6x factor. Reasoning for choosing this factor (unfortunately incorrect as I have seen with a counter-example):
A 30-degrees rotated pixel has coordinates bottom-left to top-right: [0,0]-[0.3660, 1.3660]. That is, the shortest projected side has a 0.36 pixels length. The sampling theorem requires that we sample at a double rate.
Thus, to accurately sample a 30 degrees rotated image, I must sample each 0.17 pixels, yielding a x5.88 resizing factor; 3 x 5.88 = 17,64, thus I resample the source image to a 18x18 image.