Losslessness of Laplacian Pyramid I was just reading up on the Gaussian pyramid and the Laplacian pyramid, used in compression applications of image. The source is here - Carnegie Mellon 16-385 Computer Vision - Spring 2019, Lecture 3 - Image Pyramids and Frequency Domain.

The slide claims that during Laplacian Pyramid based compression, the original image can be reconstructed back perfectly, because of saving the residuals images.

My understanding of the process is as follows


Convolve original scale image with a Gaussian 
Compute the residual image, and save it 
Downsample the convolved image,
dropping alternate row and column to get to the next level (lower
size image). 
Repeat process at this scale, till you reach lowest resolution desired.


Now, it says that given the lowest size image, and the residuals, we can reconstruct back the highest size image.

However, since we are dropping alternate  rows and columns while downsampling, isn't this information lost? How can the reconstruction be perfect?
Actually the down sampling has no role here.
It is all based on a real simple equation:

$$ I = A + B $$

It is always enough to keep 2 terms of the 3 to restore completely and perfectly the information.

So let's look on this:

$$ {I}_{0} = \left( \left( {I}_{0} \downarrow \right) \uparrow \right) + {R}_{0} $$

So if we keep $ {R}_{0} $ and we have $ \left( \left( {I}_{0} \downarrow \right) \uparrow \right) $ we can recover $ {I}_{0} $ right?
But we can fully recover $ \left( \left( {I}_{0} \downarrow \right) \uparrow \right) $ form $ \left( {I}_{0} \downarrow \right) $ as it is deterministic known operation (Up sampling) right?

So instead of $ {I}_{0} $ we will keep $ {I}_{1} = \left( {I}_{0} \downarrow \right) $ and $ {R}_{0} $.  

We now can repeat the same trick for $ {I}_{1} $:

$$ {I}_{1} = \left( \left( {I}_{1} \downarrow \right) \uparrow \right) + {R}_{1} $$

So instead of keeping $ {I}_{1} $ we can again keep $ {I}_{2} = \left( {I}_{1} \downarrow \right) $ and $ {R}_{1} $.
So in order to resotre $ {I}_{1} $ perfectly all we need is $ {I}_{2} $, $ {R}_{1} $ and $ {R}_{0} $.

Keep doing this and you will get the Laplacian Pyramid which says keep the residual of each level and the Low Pass image of the last image.

The trick here isn't the accurate definition of $ \downarrow $ or $ \uparrow $ but being able to get the same result every time you use them. Namley:

$$ \left( \left( \left( \left( I \downarrow \right) \uparrow \right) \downarrow \right) \uparrow \right) = \left( \left( I \downarrow \right) \uparrow \right) $$