
Click here for full text:
Universally Attainable ErrorExponents for Rate Constrained Denoising of Noisy Sources
Weissman, Tsachy
HPL2002214
Keyword(s): achievable exponents; competitive minimax; compound source; denoising; error exponents; Marton's exponent; NeymanPearson; noisy source coding; universal schemes
Abstract: Consider the problem of rateconstrained reconstruction of a finitealphabet discrete memoryless signal X(superscript n) =(X subscript 1), ..., X (subscript n), based on a noisecorrupted observation sequence Z(superscript n), which is the finitealphabet output of a Discrete Memoryless Channel (DMC) whose input is X(superscript n). Suppose that there is some uncertainty in the source distribution, in the channel characteristics, or in both. Equivalently, suppose that the distribution of the pairs (X(subscript i,), Z(subscript i), rather than completely being known, is only known to belong to a set Theta. Suppose further that the relevant performance criterion is the probability of excess distortion, i.e., letting X(superscript n) (Z(superscript n) denote the reconstruction, we are interested in the behavior of P(subscript theta) rho (X(superscript n), {X}^n(Z(superscript n)) > d theta), where rho is a (normalized) block distortion induced by a singleletter distortion measure and P theta denotes the probability measure corresponding to the case where (X(subscript i), Z (subscript i)) sim theta, theta in Theta. Since typically this probability will either not decay at all or do so at an exponential rate, it is the rate of this decay which we focus on. More concretely, for a given rate R greater than or equal to 0 and a family of distortion levels {d theta} theta in Theta, we are interested in families of exponential levels {I theta} theta in Theta which are achievable in the sense that for large n there exist rateR schemes satisfying  1/n log P theta (rho (X(superscript n, X^n (Z(superscript n) ) > d theta greater than or equal to I theta for all theta in Theta. Our main result is a complete ``single letter'' characterization of achievable levels {I theta} theta in Theta per any given triple (Theta, R, {d theta} theta in Theta. Equipped with this result, we later turn to addressing the question of the ``right'' choice of {I theta} theta in Theta. Relying on methodology recently put forth by Feder and Merhav in the context of the composite hypothesis testing problem, we propose a competitive minimax approach for the choice of these levels and apply our main result for characterizing the associated key quantities. Subsequently, we apply the main result to characterize optimal performance in a NeymanPearsonlike setting, where there are two possible noisecorrupted signals. In this problem, the goal of the observer of the noisy signal, rather than having to determine which of the two it is (as in the hypothesis testing problem), is to reproduce the underlying clean signal with as high a fidelity as possible (e.g., lowest number of symbol errors when distortion measure is Hamming), under the assumption that one source is active, while operating at a limited information rate R and subject to a constraint on the fidelity of reconstruction when the other source is active. Finally, we apply our result to characterize a sufficient condition for the source class, Theta, to be universally encodable in the sense of the existence of schemes attaining the optimal distributiondependent exponent, simultaneously for all sources in the class. This condition was shown in an earlier work to suffice for universality in expectation. Notes: This abstract contains mathematical formulae which cannot be represented here.
30 Pages
Back to Index
