Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2501.10609 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913655564533760 |
|---|---|
| author | Yan, Pumiao Jeong, Jiwon Sagan, Naomi Weissman, Tsachy |
| author_facet | Yan, Pumiao Jeong, Jiwon Sagan, Naomi Weissman, Tsachy |
| contents | We consider the universal discrete filtering problem, where an input sequence generated by an unknown source passes through a discrete memoryless channel, and the goal is to estimate its components based on the output sequence with limited lookahead or delay. We propose and establish the universality of a family of schemes for this setting. These schemes are induced by universal Sequential Probability Assignments (SPAs), and inherit their computational properties. We show that the schemes induced by LZ78 are practically implementable and well-suited for scenarios with limited computational resources and latency constraints. In passing, we use some of the intermediate results to obtain upper and lower bounds that appear to be new, in the purely Bayesian setting, on the optimal filtering performance in terms, respectively, of the mutual information between the noise-free and noisy sequence, and the entropy of the noise-free sequence causally conditioned on the noisy one. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_10609 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Universal Discrete Filtering with Lookahead or Delay Yan, Pumiao Jeong, Jiwon Sagan, Naomi Weissman, Tsachy Signal Processing Information Theory We consider the universal discrete filtering problem, where an input sequence generated by an unknown source passes through a discrete memoryless channel, and the goal is to estimate its components based on the output sequence with limited lookahead or delay. We propose and establish the universality of a family of schemes for this setting. These schemes are induced by universal Sequential Probability Assignments (SPAs), and inherit their computational properties. We show that the schemes induced by LZ78 are practically implementable and well-suited for scenarios with limited computational resources and latency constraints. In passing, we use some of the intermediate results to obtain upper and lower bounds that appear to be new, in the purely Bayesian setting, on the optimal filtering performance in terms, respectively, of the mutual information between the noise-free and noisy sequence, and the entropy of the noise-free sequence causally conditioned on the noisy one. |
| title | Universal Discrete Filtering with Lookahead or Delay |
| topic | Signal Processing Information Theory |
| url | https://arxiv.org/abs/2501.10609 |