Kolmogorov Superposition Theorem and its application to wavelet image decompositions

International audienceThis paper deals with the decomposition of multivariate functions into sums and compositions of monovariate functions. The global purpose of this work is to find a suitable strategy to express complex multivariate functions using simpler functions that can be analyzed using well know techniques, instead of developing complex N-dimensional tools. More precisely, most of signal processing techniques are applied in 1D or 2D and cannot easily be extended to higher dimensions. We recall that such a decomposition exists in the Kolmogorov's superposition theorem. According to this theorem, any multivariate function can be decomposed into two types of univariate functions, that are called inner and external functions. Inner functions are associated to each dimension and linearly combined to construct a hash-function that associates every point of a multidimensional space to a value of the real interval [0,1]. Every inner function is the argument for one external function. The external functions associate real values in $[0,1]$ to the image by the multivariate function of the corresponding point of the multidimensional space. Sprecher, has proved that internal functions can be used to construct space filling curves, i.e. there exists a curve that sweeps the multidimensional space and uniquely matches corresponding values into $[0,1]$. Our goal is to obtain both a new decomposition algorithm for multivariate functions (at least bi-dimensional) and adaptive space filling curves. Two strategies can be applied. Either we construct fixed internal functions to obtain space filling curves, which allows us to construct an external function such that their sums and compositions exactly correspond to the multivariate function; or the internal function is constructed by the algorithm and is adapted to the multivariate function, providing different space filling curves for different multivariate functions. We present two of the most recent constructive algorithms of monovariate functions. The first method is due to Sprecher. We provide additional explanations to the existing algorithm and present several decomposition results for gray level images. We point out the main drawback of this method: all the function parameters are fixed, so the univariate functions cannot be modified; precisely, the inner function cannot be modified and so the space filling curve. The number of layers depends on the dimension of the decomposed function. The second algorithm, proposed by Igelnik, increases the parameters flexibility, but only approximates the monovariate functions: the number of layers is variable, a neural networks optimizes the monovariate functions and the weights associated to each layer to ensure convergence to the decomposed multivariate function. We have implemented both Sprecher's and Igelnik's algorithms and present the results of the decompositions of gray level images. There are artifacts in the reconstructed images, which leads us to apply the algorithm on wavelet decomposition images. We detail the reconstruction quality and the quantity of information contained in Igelnik's network