De-noising by thresholding operator adapted wavelets

Abstract

Donoho and Johnstone (Ann Stat 26(3):879–921, 1998) proposed a method from reconstructing an unknown smooth function u from noisy data u+ζ by translating the empirical wavelet coefficients of u+ζ 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 Lu 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+ζ 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 O(NpolylogN) complexity and are localized both in space and eigenspace, the proposed method is of near-linear complexity and generalizable to nonhomogeneous noise.