
HP Labs Technical Reports
Click here for full text:
Hierarchical Guessing with a Fidelity Criterion
Merhav, Neri; Roth, Ron M.; Arikan, Erdal
HPL9709
Keyword(s): ratedistortion theory; successive refinement; guessing; source coding; error exponent
Abstract: In an earlier paper, we studied the problem of guessing a random vector X within distortion D, and characterized the best attainable exponent E(D,rho) of the rhoth moment of the number of required guesses G(X) until the guessing error falls below D. In this paper, we extend these results to a multistage, hierarchical guessing model, which allows for a faster search of a codeword vector at the encoder of a ratedistortion codebook. In the twostage case of this model, if the target distortion level is D (sub 2), the guesser first makes guesses, directs the subsequent guesses w.r.t. (a higher) distortion level D (sub 1), and then, upon his/her first success, directs the subsequent guesses to distortion D (sub 2). As in the above mentioned earlier paper, we provide a singleletter characterization of the best attainable guessing exponent, which relies heavily on wellknown results on the successive refinement problem. We also relate this guessing exponent function to the source coding error exponent function of the twostep coding process.
Back to Index
