Arithmetic Complexity of Frequency-Domain Representations of Time-Computable Signals
Holger Boche, Yannik N. Bock · 2023
The duality between time- and frequency-domain representations of information-carrying signals is an established cornerstone of information theory. In terms of computability and signal processing, asymptotically-vanishing sequences are well-behaved in the time-domain, since they can be equipped with Banach-Space norms. It is then possible to define computable asymptotically-vanishing sequences, each of which is characterized by an effective global approximation procedure. In this paper, we investigate whether the time-frequency duality preserves these characteristics, i.e., whether the image of asymptotically-vanishing sequences under the Z-Transform yields a set of computationally well-behaved functions. In particular, we classify the associated radius of convergence into the arithmetical hierarchy of definable numbers by Zheng and Weihrauch, and, as a corollary, present that it may attain non-computable values. We then proceed to investigate the computability of upper and lower bounds on the radius of convergence, as well as several related decidability problems. Lastly, we subsume our insights into a collection of contemporary results on the fundamental limits of numerical techniques in signal processing and information theory.