Kolmogorov famously proved that multivariate continuous functions can be represented as a superposition of a small number of univariate continuous functions, $$ f(x_1,dots,x_n) = sum_{q=0}^{2n+1} chi^q left( sum_{p=1}^n psi^{pq}(x_p) right).$$ Fridman cite{fridman} posed the best smoothness bound for the functions $psi^{pq}$, that such functions can be constructed to be Lipschitz continuous with constant 1. Previous algorithms to describe these inner functions have only been Holder continuous, such as those proposed by Koppen and Braun and Griebel. This is problematic, as pointed out by Griebel, in that non-smooth functions have very high storage/evaluation complexity, and this makes Kolmogorovs representation (KR) impractical using the standard definition of the inner functions. To date, no one has presented a method to compute a Lipschitz continuous inner function. In this paper, we revisit Kolmogorovs theorem along with Fridmans result. We examine a simple Lipschitz function which appear to satisfy the necessary criteria for Kolmogorovs representation, but fails in the limit. We then present a full solution to the problem, including an algorithm that computes such a Lipschitz function.
Download