Saddle Point in the Minimax Converse for Channel Coding
A minimax metaconverse has recently been proposed as a simultaneous generalization of a number of classical results and a tool for the nonasymptotic analysis. In this paper, it is shown that the order of optimizing the input and output distributions can be interchanged without affecting the bound. I...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute of Electrical and Electronics Engineers
2013
|
| Online Access: | http://hdl.handle.net/1721.1/79372 https://orcid.org/0000-0002-2109-0979 |
| _version_ | 1811074092375212032 |
|---|---|
| author | Polyanskiy, Yury |
| 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 Polyanskiy, Yury |
| author_sort | Polyanskiy, Yury |
| collection | MIT |
| description | A minimax metaconverse has recently been proposed as a simultaneous generalization of a number of classical results and a tool for the nonasymptotic analysis. In this paper, it is shown that the order of optimizing the input and output distributions can be interchanged without affecting the bound. In the course of the proof, a number of auxiliary results of separate interest are obtained. In particular, it is shown that the optimization problem is convex and can be solved in many cases by the symmetry considerations. As a consequence, it is demonstrated that in the latter cases, the (multiletter) input distribution in information-spectrum (Verdú-Han) converse bound can be taken to be a (memoryless) product of single-letter ones. A tight converse for the binary erasure channel is rederived by computing the optimal (nonproduct) output distribution. For discrete memoryless channels, a conjecture of Poor and Verdú regarding the tightness of the information spectrum bound on the error exponents is resolved in the negative. Concept of the channel symmetry group is established and relations with the definitions of symmetry by Gallager and Dobrushin are investigated. |
| first_indexed | 2024-09-23T09:43:02Z |
| format | Article |
| id | mit-1721.1/79372 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T09:43:02Z |
| publishDate | 2013 |
| publisher | Institute of Electrical and Electronics Engineers |
| record_format | dspace |
| spelling | mit-1721.1/793722022-09-30T16:22:40Z Saddle Point in the Minimax Converse for Channel Coding Polyanskiy, Yury Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Polyanskiy, Yury A minimax metaconverse has recently been proposed as a simultaneous generalization of a number of classical results and a tool for the nonasymptotic analysis. In this paper, it is shown that the order of optimizing the input and output distributions can be interchanged without affecting the bound. In the course of the proof, a number of auxiliary results of separate interest are obtained. In particular, it is shown that the optimization problem is convex and can be solved in many cases by the symmetry considerations. As a consequence, it is demonstrated that in the latter cases, the (multiletter) input distribution in information-spectrum (Verdú-Han) converse bound can be taken to be a (memoryless) product of single-letter ones. A tight converse for the binary erasure channel is rederived by computing the optimal (nonproduct) output distribution. For discrete memoryless channels, a conjecture of Poor and Verdú regarding the tightness of the information spectrum bound on the error exponents is resolved in the negative. Concept of the channel symmetry group is established and relations with the definitions of symmetry by Gallager and Dobrushin are investigated. National Science Foundation (U.S.) (Center for Science of Information, under Grant CCF-0939370) 2013-06-26T15:38:43Z 2013-06-26T15:38:43Z 2013-05 2012-12 Article http://purl.org/eprint/type/JournalArticle 0018-9448 1557-9654 INSPEC Accession Number: 13448776 http://hdl.handle.net/1721.1/79372 Polyanskiy, Yury. Saddle Point in the Minimax Converse for Channel Coding. IEEE Transactions on Information Theory 59, no. 5 (May 2013): 2576-2595. https://orcid.org/0000-0002-2109-0979 en_US http://dx.doi.org/10.1109/TIT.2012.2236382 IEEE Transactions on Information Theory Creative Commons Attribution-Noncommercial-Share Alike 3.0 http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf Institute of Electrical and Electronics Engineers Polyanskiy via Amy Stout |
| spellingShingle | Polyanskiy, Yury Saddle Point in the Minimax Converse for Channel Coding |
| title | Saddle Point in the Minimax Converse for Channel Coding |
| title_full | Saddle Point in the Minimax Converse for Channel Coding |
| title_fullStr | Saddle Point in the Minimax Converse for Channel Coding |
| title_full_unstemmed | Saddle Point in the Minimax Converse for Channel Coding |
| title_short | Saddle Point in the Minimax Converse for Channel Coding |
| title_sort | saddle point in the minimax converse for channel coding |
| url | http://hdl.handle.net/1721.1/79372 https://orcid.org/0000-0002-2109-0979 |
| work_keys_str_mv | AT polyanskiyyury saddlepointintheminimaxconverseforchannelcoding |