Variable-Length Compression Allowing Errors
This paper studies the fundamental limits of the minimum average length of lossless and lossy variable-length compression, allowing a nonzero error probability ε, for lossless compression. We give nonasymptotic bounds on the minimum average length in terms of Erokhin's rate-distortion function...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Institute of Electrical and Electronics Engineers (IEEE)
2019
|
| Online Access: | https://hdl.handle.net/1721.1/121939 |
| _version_ | 1826217661733797888 |
|---|---|
| author | Kostina, Victoria Polyanskiy, Yury Verdu, Sergio |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Kostina, Victoria Polyanskiy, Yury Verdu, Sergio |
| author_sort | Kostina, Victoria |
| collection | MIT |
| description | This paper studies the fundamental limits of the minimum average length of lossless and lossy variable-length compression, allowing a nonzero error probability ε, for lossless compression. We give nonasymptotic bounds on the minimum average length in terms of Erokhin's rate-distortion function and we use those bounds to obtain a Gaussian approximation on the speed of approach to the limit, which is quite accurate for all but small blocklengths: (1 - ε) k H(S) - ((V(S)/2π))1/2 exp[-((Q-1 (ε))2/2)], where Q-1(·) is the functional inverse of the standard Gaussian complementary cumulative distribution function, and V(S) is the source dispersion. A nonzero error probability thus not only reduces the asymptotically achievable rate by a factor of 1 - ε, but this asymptotic limit is approached from below, i.e., larger source dispersions and shorter blocklengths are beneficial. Variable-length lossy compression under an excess distortion constraint is shown to exhibit similar properties. |
| first_indexed | 2024-09-23T17:07:15Z |
| format | Article |
| id | mit-1721.1/121939 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T17:07:15Z |
| publishDate | 2019 |
| publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| record_format | dspace |
| spelling | mit-1721.1/1219392022-09-29T23:49:22Z Variable-Length Compression Allowing Errors Kostina, Victoria Polyanskiy, Yury Verdu, Sergio Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Laboratory for Information and Decision Systems This paper studies the fundamental limits of the minimum average length of lossless and lossy variable-length compression, allowing a nonzero error probability ε, for lossless compression. We give nonasymptotic bounds on the minimum average length in terms of Erokhin's rate-distortion function and we use those bounds to obtain a Gaussian approximation on the speed of approach to the limit, which is quite accurate for all but small blocklengths: (1 - ε) k H(S) - ((V(S)/2π))1/2 exp[-((Q-1 (ε))2/2)], where Q-1(·) is the functional inverse of the standard Gaussian complementary cumulative distribution function, and V(S) is the source dispersion. A nonzero error probability thus not only reduces the asymptotically achievable rate by a factor of 1 - ε, but this asymptotic limit is approached from below, i.e., larger source dispersions and shorter blocklengths are beneficial. Variable-length lossy compression under an excess distortion constraint is shown to exhibit similar properties. National Science Foundation (U.S.). Center for Science of Information (Grant CCF-0939370) 2019-07-23T20:11:58Z 2019-07-23T20:11:58Z 2015-08 2015-10 2019-07-01T16:42:13Z Article http://purl.org/eprint/type/JournalArticle 0018-9448 1557-9654 https://hdl.handle.net/1721.1/121939 Kostina, Victoria, Yury Polyanskiy and Sergio Verdú. "Variable-Length Compression Allowing Errors." IEEE Transactions on Information Theory 61, no. 8 (August 2015): pp. 4316-4330. en 10.1109/tit.2015.2438831 IEEE Transactions on Information Theory Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Institute of Electrical and Electronics Engineers (IEEE) arXiv |
| spellingShingle | Kostina, Victoria Polyanskiy, Yury Verdu, Sergio Variable-Length Compression Allowing Errors |
| title | Variable-Length Compression Allowing Errors |
| title_full | Variable-Length Compression Allowing Errors |
| title_fullStr | Variable-Length Compression Allowing Errors |
| title_full_unstemmed | Variable-Length Compression Allowing Errors |
| title_short | Variable-Length Compression Allowing Errors |
| title_sort | variable length compression allowing errors |
| url | https://hdl.handle.net/1721.1/121939 |
| work_keys_str_mv | AT kostinavictoria variablelengthcompressionallowingerrors AT polyanskiyyury variablelengthcompressionallowingerrors AT verdusergio variablelengthcompressionallowingerrors |