Lower Limits of Discrete Universal Denoising
| Autor: | Erik Ordentlich, Krishnamurthy Viswanathan |
|---|---|
| Rok vydání: | 2009 |
| Předmět: |
Discrete mathematics
Independent and identically distributed random variables Sequence Mathematical optimization Noise measurement Stochastic process Noise reduction Multiplicative function Function (mathematics) Library and Information Sciences Upper and lower bounds Computer Science Applications Computer Science::Computer Vision and Pattern Recognition Constant (mathematics) Random variable Data compression Communication channel Computer Science::Information Theory Information Systems Mathematics |
| Zdroj: | ISIT |
| ISSN: | 0018-9448 |
| DOI: | 10.1109/tit.2008.2011429 |
| Popis: | In the spirit of results on universal compression, we compare the performance of universal denoisers on discrete memoryless channels to that of the best performance obtained by an omniscient kth-order sliding-window denoiser, namely, one that is tuned to the transmitted noiseless sequence. We show that the additional loss incurred in the worst case by any universal denoiser on a length- n sequence grows at least like Omega(ck/radicn) , where c is a constant depending on the channel parameters and the loss function. This shows that for fixed k the additional loss incurred by the Discrete Universal Denoiser (DUDE) is no larger than a constant multiplicative factor of the best possible. Furthermore, we compare universal denoisers to denoisers that are aware of the distribution of the transmitted noiseless sequence. We show that, even for this weaker target loss, for any universal denoiser there exists some distribution for the noiseless sequence corresponding to a sequence of independent and identically distributed (i.i.d.) random variables whose optimum expected loss is lower than that incurred by the universal denoiser by Omega(1/radicn). |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|