Strong Successive Refinability and Rate-Distortion-Complexity Tradeoff

DOI10.1109/TIT.2016.2549540zbMATH Open1359.94144arXiv1506.03407OpenAlexW2963522419MaRDI QIDQ2976809FDOQ2976809

Amir Ingber, Albert No, Tsachy Weissman

Publication date: 28 April 2017

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Abstract: We investigate the second order asymptotics (source dispersion) of the successive refinement problem. Similarly to the classical definition of a successively refinable source, we say that a source is strongly successively refinable if successive refinement coding can achieve the second order optimum rate (including the dispersion terms) at both decoders. We establish a sufficient condition for strong successive refinability. We show that any discrete source under Hamming distortion and the Gaussian source under quadratic distortion are strongly successively refinable. We also demonstrate how successive refinement ideas can be used in point-to-point lossy compression problems in order to reduce complexity. We give two examples, the binary-Hamming and Gaussian-quadratic cases, in which a layered code construction results in a low complexity scheme that attains optimal performance. For example, when the number of layers grows with the block length $n$, we show how to design an $O(n^{log(n)})$ algorithm that asymptotically achieves the rate-distortion bound.

Full work available at URL: https://arxiv.org/abs/1506.03407

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Cited In (1)

• Finite Blocklength Lossy Source Coding for Discrete Memoryless Sources

   Recommendations

• Strong universal source coding subject to a rate-distortion constraint 👍 👎
• Successive refinement of information: characterization of the achievable rates 👍 👎
• Refinement of the Random Coding Bound 👍 👎
• Semidefinite Programming Approach to Gaussian Sequential Rate-Distortion Trade-Offs 👍 👎
• Successive Refinement With Decoder Cooperation and Its Channel Coding Duals 👍 👎
• Strong converses in source coding relative to a fidelity criterion 👍 👎
• Bounds on Data Compression Ratio with a Given Tolerable Error Probability 👍 👎
• The strong converse for source coding with a fidelity criterion 👍 👎
• A strong version of the redundancy-capacity theorem of universal coding 👍 👎

This page was built for publication: Strong Successive Refinability and Rate-Distortion-Complexity Tradeoff

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2976809)