Differentiable learning of sparse lossless Fourier filters

Abstract

Purpose. The Fourier transform-bounded Kolmogorov complexity proposed in the study by Terry-Jack [J. Software Eng. Appl. 15(10), 359 (2022)], as well as in that by Terry-Jack and O’Keefe [Physica D 453, 133824 (2023)], relies on finding the minimal subset of frequency coefficients that can exactly reconstruct the original image. However, we show that finding this minimal subset of coefficients is a combinatorial optimization problem that becomes computationally intractable for large images. As such, naive solutions such as greedy search are impractical at scale, limiting the feasibility and application of Fourier transform bounded Kolmogorov complexity. Methods. We reformulate the hard combinatorial problem as a differentiable optimization task via the introduction of smooth surrogates for non-differentiable components such as the quantization step and use a straight-through estimator (STE) to learn sparse binary masks (frequency filters) that allow for exact reconstruction of the original image via gradient-descent. Results. Experiments on elementary cellular automata, QR codes, a natural binary image, and random noise demonstrate that sparse Fourier masks capable of bit-exact reconstruction can be learned efficiently at scales that are impractical for a combinatorial or greedy search. Although the problem admits a linear LASSO reformulation that enables classical sparse-recovery methods, experiments against a FISTA baseline demonstrate the advantages of directly optimizing the original nonlinear objective via an STE. Conclusion. This work provides the first practical framework for learning lossless Fourier-domain filters at scale by reframing a hard combinatorial problem as a differentiable learning task.