A PAC-bound on the Channel Capacity of an Observed Discrete Memoryless Channel
Loading...
Links to Files
Author/Creator
Author/Creator ORCID
Date
2021-04-19
Type of Work
Department
Program
Citation of Original Publication
Tope, Michael A.; Morris, Joel M.; A PAC-bound on the Channel Capacity of an Observed Discrete Memoryless Channel; 2021 55th Annual Conference on Information Sciences and Systems (CISS); https://ieeexplore.ieee.org/document/9400323
Rights
This item is likely protected under Title 17 of the U.S. Copyright Law. Unless on a Creative Commons license, for uses protected by Copyright Law, contact the copyright holder or the author.
© 2021 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.
© 2021 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.
Subjects
Abstract
This paper presents a method to compute the channel capacity of an observed (partially known) discrete memoryless channel (DMC) using a probably approximately correct (PAC) bound. Given N independently and identically distributed (i.i.d.) input-output sample pairs, we define a compound DMC with convex sublevel-sets to constrain the channel output uncertainty with high probability. Then we numerically solve an ‘K-way’ convex optimization to determine an achievable information rate RL(N) across the channel that holds with a specified high probability. Our approach provides the non-asymptotic ‘worst-case’ convergence RL(N) to channel capacity C at the rate of O(√log(log(N))/N) .