Name
Abstract | ||
|---|---|---|
Consider approximate (lossy) matching of a source string ~P, with a random codebook generated from reproduction distribution Q, at a specified distortion d. Previous work determined the minimum coding rate R1=R(P, Q, d) for this setting. We observe that for a large word length and with high probability, the matching codeword is typical with a distribution Q1 which is different from Q. If a new random codebook is generated ~Q1, then the source string will favor codewords which are typical with a new distribution Q2, resulting in a minimum coding rate R2=R(P, Q1, d), and so on. We show that the sequences of distributions Q1, Q 2,... and rates R1, R2,..., generated by this procedure, converge to an optimum reproduction distribution Q*, and the rate-distortion function R(P, d), respectively. We also derive a fixed rate-distortion slope version of this natural type selection process. In the latter case, an iteration of the process stochastically simulates an iteration of the Blahut-Arimoto (1972) algorithm for rate-distortion function computation (without recourse to prior knowledge of the underlying source distribution). To strengthen these limit statements, we also characterize the steady-state error of these procedures when iterating at a finite string length. Implications of the main results provide fresh insights into the workings of lossy variants of the Lempel-Ziv algorithm for adaptive compression |
Year | DOI | Venue |
|---|---|---|
2001 | 10.1109/18.904515 | IEEE Transactions on Information Theory |
Keywords | Field | DocType |
underlying source distribution,adaptive lossy compression,reproduction distribution q,fixed rate-distortion slope version,natural type selection,finite string length,distributions q1,new distribution q2,rate-distortion function r,source string,optimum reproduction distribution,distribution q1,lossy compression,frequency,steady state,adaptive signal processing,stochastic simulation,speech,databases,distributed computing,probability,data compression,computational modeling,rate distortion theory,iteration,information theory,statistics | Discrete mathematics,Combinatorics,Code rate,Lossy compression,Code word,Adaptive filter,Data compression,Distortion,Rate–distortion theory,Mathematics,Codebook | Journal |
Volume | Issue | ISSN |
47 | 1 | 0018-9448 |
Citations | PageRank | References |
29 | 1.44 | 18 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Zamir, R. | 1 | 1496 | 141.87 |
| Kenneth Rose | 2 | 1261 | 119.38 |