On the Solvability of the Peak Value Problem for Bandlimited Signals with Applications

In this paper we study from an algorithmic perspective the problem of finding the peak value of a bandlimited signal. This problem plays an important role in the design and optimization of communication systems. We show that the peak value problem, i.e., computing the peak value of a bandlimited signal from its samples, can be solved algorithmically if oversampling is used. Without oversampling this is not possible. There exist bandlimited signals, for which the sequence of samples is computable, but the signal itself is not. This problem is directly related to the question whether there is a link between computability in the digital domain and the analog domain, and hence to a fundamental signal processing problem. We show that there is an asymmetry between continuous-time and discrete-time computability. Further, we study the decay behavior of computable bandlimited signals, which describes the concentration of the signals in the time domain, and, for locally computable bandlimited signals, we analyze if it is always possible to decide algorithmically whether the peak value is smaller than a given threshold.