# Technical Reports

## HPL-2009-343

**Denoiser-loss estimators and twice-universal denoising**

* Ordentlich, Erik; Viswanathan, Krishnamurthy; Weinberger, Marcelo J.*

HP Laboratories

HPL-2009-343

**Keyword(s):** Universal denoising, concentration inequalities, universal data compression

**Abstract:** We study the concentration of denoiser loss estimators, with application to the selection of denoiser parameters for a given observed sequence (in particular, the window size *k* of the DUDE algorithm [1]) via minimization of the estimated loss. We show that for a loss estimator proposed earlier [2], it is not possible to derive strong concentration results for certain pathological input sequences. By modifying the estimator slightly we obtain a loss estimator for which the DUDE's estimated loss strongly concentrates around the true loss provided *kM ^{2k} = o(n)*, where

*M*is the size of the alphabet and

*n*the sequence length. We also show that for certain channels, it is possible to estimate the best

*k*using a combination of the two loss estimators. Moreover, for non-pathological sequences and

*k = o(n*, we derive concentration results for the original loss estimator and all channels.

^{1/4})
In a second set of results, we extend the notion of twice universality from universal data compression theory to the sliding window denoising setting. Given a sequence length *n* and a denoiser, we define the *k*-dependent twice-universality penalty of the denoiser as the worst case excess denoising loss relative to sliding window denoisers with window length *k above and beyond* the worst case excess loss of DUDE with parameter *k*. Given an increasing sequence of window parameters *k _{n}* in the data sequence length

*n*, we use loss estimators and results from the analysis mentioned above to construct a sequence of (twice) universal denoisers that achieves a much smaller twice universality penalty for

*k < k*than the sequence of DUDEs with parameter

_{n}*k*.

_{n}8 Pages

Additional Publication Information: Presented at IEEE International Symposium on Information Theory, June-July 2009.

External Posting Date: October 21, 2009 [Fulltext]. Approved for External Publication

Internal Posting Date: October 21, 2009 [Fulltext]