Neural polar codes improve data compression without explicit source models
Neural Polar Codes for Source Coding
Information Theory
Summary
Compressing data efficiently often requires knowing the exact source or pattern of the data, which can be hard or slow for complex sources. This paper introduces a way to train neural networks to mimic how polar codes compress data, without needing to know the data’s detailed model. These learned systems can handle complicated data like genetic sequences and still compress it well, sometimes better than traditional methods. This approach works for both perfect compression and controlled information loss, as well as cases where extra information is available only to the decompressor.
What this means in practice
- •For data compression engineers: Design compression systems for unknown or complex data sources without explicit source models using neural polar decoders.
- •For bioinformatics developers: Compress genomic data efficiently leveraging learned polar codes that handle memory and large alphabets where classical methods struggle.
Authors
Bashar Huleihel, Ziv Aharoni, Haim H. Permuter
Abstract
This paper presents a data-driven approach to lossless and lossy source compression using polar codes. Classical polar source coding achieves fundamental limits with low complexity for binary memoryless sources. However, for unknown q-ary sources with memory, successive-cancellation (SC) decoding requires an explicit source model and can be computationally prohibitive. We present analytical SC recursions and show that exact implementations scale quadratically with alphabet size and cubically with state-space size. To overcome these limitations, we develop neural polar decoders trained directly from data to approximate conditional distributions of synthetic polar coordinates without requiring an explicit source model. These learned distributions enable estimation of entropy rates, mutual information, and rate-distortion functions, and support explicit polar compression schemes. For lossless compression, we identify high-entropy polarized coordinates and reconstruct the remaining coordinates using the learned SC recursion. For lossy compression, we combine neural polar decoders with a neural test channel to estimate and optimize the mutual information-distortion tradeoff and construct an explicit lossy polar code. We also extend the framework to Wyner-Ziv compression with decoder side information by learning conditional polarized distributions and a reconstruction mapping. Experiments on memoryless sources, sources with memory, and real genomic data show that the learned decoders closely match analytical SC decoders when available and remain applicable when conventional methods are computationally infeasible or the source model is unavailable.