Technical Reports
HPL-2009-343
Click here for full text:
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 kM2k = 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 1/4 ), we derive concentration results for the original loss estimator and all channels.
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 kn 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 < kn than the sequence of DUDEs with parameter kn.
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]