Approximation of One-Dimensional Digital Signals under the l-Infinity Norm

Approximation of digital signals by means of continuous-time functions is often required in many tasks of digital to analog conversion, signal processing and coding. In many cases the approximation is performed based on an $l^2$ optimality criterion; in this paper we study approximations of one-dimensional signals under the $l^\infty$ norm. We first introduce approximations in linear spaces, for which linear programming methods are known. For the particular case of linear approximations (i.e. first order polynomials), we propose a geometric solution that is shown to be computationally more efficient than the linear programming approach. Then, we study the problem of piecewise approximations, i.e. dividing the domain into intervals and approximating the signal in linear spaces within every segment independently, so as to reach an optimal non continuous approximation. Given an error bound $\delta$, we establish a strategy to determine the minimum number k of segments for which the approximation is guaranteed to produce an error within $\delta$. We then show how to find the optimal partition that gives the piecewise $l^\infty$ optimal solution with k segments. The computational complexity of the algorithms is studied, showing that in many practical situations the number of operations is O(n), being n the number of samples