De-noising by thresholding operator adapted wavelets
Provides a theoretically grounded denoising method for functions with operator-based smoothness priors, enabling efficient recovery in PDE and graph settings.
The authors extend wavelet thresholding denoising to cases where prior information is about a linear operator applied to the function, showing near minimax optimality and energy norm bounds with near-linear complexity.
Donoho and Johnstone 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 $ Łu$ where $Ł$ 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 $\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.