Reconstruct with prior.
You can use random projections for dimension reduction.
Such reductions preserve a lot of basic structure and
geometric properties of the original data.
The sign flip,WHT random projection can be inverted by doing
a WHT and then the same sign flip again, allowing an
approximate reconstruction of the original data.
This can be improved by having some prior knowledge of
the original data, such as sparsity or smoothness.
In this case the original data is assumed to be invarient
under a 2d binomial smoothing filter.