Document Open Access Logo

Algorithmic Polarization for Hidden Markov Models

Authors Venkatesan Guruswami, Preetum Nakkiran, Madhu Sudan

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2019.39.pdf
  • Filesize: 0.62 MB
  • 19 pages

Document Identifiers

Author Details

Venkatesan Guruswami
  • Computer Science Department, Carnegie Mellon University, Pittsburgh, PA 15213, USA
Preetum Nakkiran
  • Harvard John A. Paulson School of Engineering and Applied Sciences, Harvard University, 33 Oxford Street, Cambridge, MA 02138, USA
Madhu Sudan
  • Harvard John A. Paulson School of Engineering and Applied Sciences, Harvard University, 33 Oxford Street, Cambridge, MA 02138, USA

Funding

  • Guruswami, Venkatesan: Most of this work was done when the author was visiting the Center for Mathematical Sciences and Applications, Harvard University, Cambridge, MA. Research supported in part by NSF grants CCF-1422045 and CCF-1814603.
  • Nakkiran, Preetum: Work supported in part by the NSF Graduate Research Fellowship Grant No. DGE1144152, and Madhu Sudan’s Simons Investigator Award and NSF Award CCF 1715187.
  • Sudan, Madhu: Work supported in part by a Simons Investigator Award and NSF Award CCF 1715187.

Cite As Get BibTex

Venkatesan Guruswami, Preetum Nakkiran, and Madhu Sudan. Algorithmic Polarization for Hidden Markov Models. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 39:1-39:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.ITCS.2019.39

Abstract

Using a mild variant of polar codes we design linear compression schemes compressing Hidden Markov sources (where the source is a Markov chain, but whose state is not necessarily observable from its output), and to decode from Hidden Markov channels (where the channel has a state and the error introduced depends on the state). We give the first polynomial time algorithms that manage to compress and decompress (or encode and decode) at input lengths that are polynomial both in the gap to capacity and the mixing time of the Markov chain. Prior work achieved capacity only asymptotically in the limit of large lengths, and polynomial bounds were not available with respect to either the gap to capacity or mixing time. Our results operate in the setting where the source (or the channel) is known. If the source is unknown then compression at such short lengths would lead to effective algorithms for learning parity with noise - thus our results are the first to suggest a separation between the complexity of the problem when the source is known versus when it is unknown.

Subject Classification

ACM Subject Classification
  • Theory of computation → Error-correcting codes
Keywords
  • polar codes
  • error-correcting codes
  • compression
  • hidden markov model

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Erdal Arıkan. Channel Polarization: A method for constructing capacity-achieving codes for symmetric binary-input memoryless channels. IEEE Transactions on Information Theory, pages 3051-3073, July 2009. Google Scholar
  2. Jarosław Błasiok, Venkatesan Guruswami, Preetum Nakkiran, Atri Rudra, and Madhu Sudan. General strong polarization. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 485-492. ACM, 2018. URL: http://arxiv.org/abs/1802.02718.
  3. Jaroslaw Blasiok, Venkatesan Guruswami, and Madhu Sudan. Polar Codes with Exponentially Small Error at Finite Block Length. In LIPIcs-Leibniz International Proceedings in Informatics, volume 116. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018. Google Scholar
  4. Eren Şaşoğlu. Polar coding theorems for discrete systems. PhD thesis, Ecole Polytechnique Fédérale de Lausanne, 2011. Google Scholar
  5. Venkatesan Guruswami and Patrick Xia. Polar Codes: Speed of Polarization and Polynomial Gap to Capacity. IEEE Trans. Information Theory, 61(1):3-16, 2015. Preliminary version in Proc. of FOCS 2013. Google Scholar
  6. Seyed Hamed Hassani, Kasra Alishahi, and Rüdiger L. Urbanke. Finite-Length Scaling for Polar Codes. IEEE Trans. Information Theory, 60(10):5875-5898, 2014. URL: http://dx.doi.org/10.1109/TIT.2014.2341919.
  7. Satish Babu Korada, Eren Sasoglu, and Rüdiger L. Urbanke. Polar Codes: Characterization of Exponent, Bounds, and Constructions. IEEE Transactions on Information Theory, 56(12):6253-6264, 2010. URL: http://dx.doi.org/10.1109/TIT.2010.2080990.
  8. Ramtin Pedarsani, Seyed Hamed Hassani, Ido Tal, and Emre Telatar. On the construction of polar codes. In Proceedings of 2011 IEEE International Symposium on Information Theory, pages 11-15, 2011. URL: http://dx.doi.org/10.1109/ISIT.2011.6033724.
  9. Eren Sasoglu and Ido Tal. Polar coding for processes with memory. In Proceedings of the IEEE International Symposium on Information Theory, pages 225-229, 2016. Google Scholar
  10. Boaz Shuval and Ido Tal. Fast Polarization for Processes with Memory. In Proceedings of the IEEE International Symposium on Information Theory, pages 851-855, 2018. Google Scholar
  11. Ido Tal and Alexander Vardy. How to Construct Polar Codes. IEEE Transactions on Information Theory, 59(10):6562-6582, October 2013. Google Scholar
  12. Runxin Wang, Junya Honda, Hirosuke Yamamoto, Rongke Liu, and Yi Hou. Construction of polar codes for channels with memory. In Proceedings of the 2015 IEEE Information Theory Workshop - Fall (ITW), pages 187-191, 2015. Google Scholar
  13. Runxin Wang, Rongke Liu, and Yi Hou. Joint Successive Cancellation Decoding of Polar Codes over Intersymbol Interference Channels. CoRR, 2014. URL: http://arxiv.org/abs/1404.3001.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact