  Donoho and Johnstone proposed a method from reconstructing an unknown smooth
function $u$ from noisy data $u+\zeta$ by translating the empirical wavelet
coefficients of $u+\zeta$ towards zero. We consider the situation where the
prior information on the unknown function $u$ may not be the regularity of $u$
but that of $ \L u$ where $\L$ is a linear operator (such as a PDE or a graph
Laplacian). We show that the approximation of $u$ obtained by thresholding the
gamblet (operator adapted wavelet) coefficients of $u+\zeta$ is near minimax
optimal (up to a multiplicative constant), and with high probability, its
energy norm (defined by the operator) is bounded by that of $u$ up to a
constant depending on the amplitude of the noise. Since gamblets can be
computed in $\mathcal{O}(N \operatorname{polylog} N)$ complexity and are
localized both in space and eigenspace, the proposed method is of near-linear
complexity and generalizable to non-homogeneous noise.
