Poset-Markov Channels: Capacity via Group Symmetry
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909687844175872 |
|---|---|
| author | Atay, Eray Unsal Levin, Eitan Chandrasekaran, Venkat Kostina, Victoria |
| author_facet | Atay, Eray Unsal Levin, Eitan Chandrasekaran, Venkat Kostina, Victoria |
| contents | Computing channel capacity is in general intractable because it is given by the limit of a sequence of optimization problems whose dimensionality grows to infinity. As a result, constant-sized characterizations of feedback or non-feedback capacity are known for only a few classes of channels with memory. This paper introduces poset-causal channels$\unicode{x2014}$a new formalism of a communication channel in which channel inputs and outputs are indexed by the elements of a partially ordered set (poset). We develop a novel methodology that allows us to establish a single-letter upper bound on the feedback capacity of a subclass of poset-causal channels whose memory structure exhibits a Markov property and symmetry. The methodology is based on symmetry reduction in optimization. We instantiate our method on two channel models: the Noisy Output is The STate (NOST) channel$\unicode{x2014}$for which the bound is tight$\unicode{x2014}$and a new two-dimensional extension of it. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_19305 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Poset-Markov Channels: Capacity via Group Symmetry Atay, Eray Unsal Levin, Eitan Chandrasekaran, Venkat Kostina, Victoria Information Theory Optimization and Control Computing channel capacity is in general intractable because it is given by the limit of a sequence of optimization problems whose dimensionality grows to infinity. As a result, constant-sized characterizations of feedback or non-feedback capacity are known for only a few classes of channels with memory. This paper introduces poset-causal channels$\unicode{x2014}$a new formalism of a communication channel in which channel inputs and outputs are indexed by the elements of a partially ordered set (poset). We develop a novel methodology that allows us to establish a single-letter upper bound on the feedback capacity of a subclass of poset-causal channels whose memory structure exhibits a Markov property and symmetry. The methodology is based on symmetry reduction in optimization. We instantiate our method on two channel models: the Noisy Output is The STate (NOST) channel$\unicode{x2014}$for which the bound is tight$\unicode{x2014}$and a new two-dimensional extension of it. |
| title | Poset-Markov Channels: Capacity via Group Symmetry |
| topic | Information Theory Optimization and Control |
| url | https://arxiv.org/abs/2506.19305 |