De-noising by thresholding operator adapted wavelets

摘要

Donoho and Johnstone (Ann Stat 26(3):879-921, 1998) 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 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 + 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 O(N polylog N) complexity and are localized both in space and eigenspace, the proposed method is of near-linear complexity and generalizable to nonhomogeneous noise.