Kolmogorov–Arnold representation theorem

In real analysis and approximation theory, the Kolmogorov–Arnold representation theorem (or superposition theorem) states that every multivariate continuous function $f\colon [0,1]^{n}\to \mathbb {R}$ can be represented as a superposition of continuous single-variable functions.

The works of Vladimir Arnold and Andrey Kolmogorov established that if f is a multivariate continuous function, then f can be written as a finite composition of continuous functions of a single variable and the binary operation of addition. More specifically,

$f(\mathbf {x} )=f(x_{1},\ldots ,x_{n})=\sum _{q=0}^{2n}\Phi _{q}\!\left(\sum _{p=1}^{n}\phi _{q,p}(x_{p})\right)$.

where $\phi _{q,p}\colon [0,1]\to \mathbb {R}$ and $\Phi _{q}\colon \mathbb {R} \to \mathbb {R}$.

There are proofs with specific constructions.

It solved a more constrained form of Hilbert's thirteenth problem, so the original Hilbert's thirteenth problem is a corollary. In a sense, they showed that the only true multivariate function is the sum, since every other function can be written using univariate functions and summing.

History

The Kolmogorov–Arnold representation theorem is closely related to Hilbert's 13th problem. In his Paris lecture at the International Congress of Mathematicians in 1900, David Hilbert formulated 23 problems which in his opinion were important for the further development of mathematics. The 13th of these problems dealt with the solution of general equations of higher degrees. It is known that for algebraic equations of degree 4 the solution can be computed by formulae that only contain radicals and arithmetic operations. For higher orders, Galois theory shows us that the solutions of algebraic equations cannot be expressed in terms of basic algebraic operations. It follows from the so called Tschirnhaus transformation that the general algebraic equation

$x^{n}+a_{n-1}x^{n-1}+\cdots +a_{0}=0$

can be translated to the form $y^{n}+b_{n-4}y^{n-4}+\cdots +b_{1}y+1=0$. The Tschirnhaus transformation is given by a formula containing only radicals and arithmetic operations and transforms. Therefore, the solution of an algebraic equation of degree $n$ can be represented as a superposition of functions of two variables if $n<7$ and as a superposition of functions of $n-4$ variables if $n\geq 7$. For $n=7$ the solution is a superposition of arithmetic operations, radicals, and the solution of the equation $y^{7}+b_{3}y^{3}+b_{2}y^{2}+b_{1}y+1=0$.

A further simplification with algebraic transformations seems to be impossible which led to Hilbert's conjecture that "A solution of the general equation of degree 7 cannot be represented as a superposition of continuous functions of two variables". This explains the relation of Hilbert's thirteenth problem to the representation of a higher-dimensional function as superposition of lower-dimensional functions. In this context, it has stimulated many studies in the theory of functions and other related problems by different authors.

Variants

A variant of Kolmogorov's theorem that reduces the number of outer functions $\Phi _{q}$ is due to George Lorentz. He showed in 1962 that the outer functions $\Phi _{q}$ can be replaced by a single function $\Phi$. More precisely, Lorentz proved the existence of functions $\phi _{q,p}$, $q=0,1,\ldots ,2n$, $p=1,\ldots ,n,$ such that

$f(\mathbf {x} )=\sum _{q=0}^{2n}\Phi \!\left(\sum _{p=1}^{n}\phi _{q,p}(x_{p})\right).$

David Sprecher replaced the inner functions $\phi _{q,p}$ by one single inner function with an appropriate shift in its argument. He proved that there exist real values $\eta ,\lambda _{1},\ldots ,\lambda _{n}$, a continuous function $\Phi \colon \mathbb {R} \rightarrow \mathbb {R}$, and a real increasing continuous function $\phi \colon [0,1]\rightarrow [0,1]$ with $\phi \in \operatorname {Lip} (\ln 2/\ln(2N+2))$, for $N\geq n\geq 2$, such that

$f(\mathbf {x} )=\sum _{q=0}^{2n}\Phi \!\left(\sum _{p=1}^{n}\lambda _{p}\phi (x_{p}+\eta q)+q\right).$

Phillip A. Ostrand generalized the Kolmogorov superposition theorem to compact metric spaces. For $p=1,\ldots ,m$ let $X_{p}$ be compact metric spaces of finite dimension $n_{p}$ and let $n=\sum _{p=1}^{m}n_{p}$. Then there exists continuous functions $\phi _{q,p}\colon X_{p}\rightarrow [0,1],q=0,\ldots ,2n,p=1,\ldots ,m$ and continuous functions $G_{q}\colon [0,1]\rightarrow \mathbb {R} ,q=0,\ldots ,2n$ such that any continuous function $f\colon X_{1}\times \dots \times X_{m}\rightarrow \mathbb {R}$ is representable in the form

$f(x_{1},\ldots ,x_{m})=\sum _{q=0}^{2n}G_{q}\!\left(\sum _{p=1}^{m}\phi _{q,p}(x_{p})\right).$

Limitations

The theorem does not hold in general for complex multi-variate functions, as discussed here. Furthermore, the non-smoothness of the inner functions and their "wild behavior" has limited the practical use of the representation, although there is some debate on this.

Applications

In the field of machine learning, there have been various attempts to use neural networks modeled on the Kolmogorov–Arnold representation. In these works, the Kolmogorov–Arnold theorem plays a role analogous to that of the universal approximation theorem in the study of multilayer perceptrons.

Proof

Here we prove one example. This proof closely follows . We prove the case of functions depending on two variables, as the generalization is immediate.

Setup

• Let ${\textstyle I}$ be the unit interval ${\textstyle [0,1]}$.
• Let ${\textstyle C[I]}$ be the set of continuous functions of type ${\textstyle [0,1]\to \mathbb {R} }$. It is a function space with supremum norm (it is a Banach space).
• Let ${\textstyle f}$ be a continuous function of type ${\textstyle [0,1]^{2}\to \mathbb {R} }$, and let ${\textstyle \|f\|}$ be the supremum of it on ${\textstyle [0,1]^{2}}$.
• Let ${\textstyle t}$ be a positive irrational number. Its exact value is irrelevant.

We say that a 5-tuple ${\textstyle (\phi _{1},\dots ,\phi _{5})\in C[I]^{5}}$ is a Kolmogorov-Arnold tuple if and only if any ${\textstyle f\in C[I^{2}]}$ there exists a continuous function ${\textstyle g:\mathbb {R} \to \mathbb {R} }$, such that $$f(x,y)=\sum _{i=1}^{5}g(\phi _{i}(x)+t\phi _{i}(y))$$In the notation, we have the following:

Theorem — The Kolmogorov-Arnold tuples make up an open and dense subset of ${\textstyle C[I]^{5}}$.

Proof

Fix a ${\textstyle f\in C[I^{2}]}$. We show that a certain subset ${\textstyle U_{f}\subset C[I]^{5}}$ is open and dense: There exists continuous ${\textstyle g}$ such that ${\textstyle \|g\|<{\frac {1.01}{7}}\|f\|}$, and $${\Big \|}f(x,y)-\sum _{i=1}^{5}g(\phi _{i}(x)+t\phi _{i}(y)){\Big \|}<{\frac {6.01}{7}}\|f\|$$We can assume that ${\textstyle \|f\|=1}$ with no loss of generality.

By continuity, the set of such 5-tuples is open in ${\textstyle C[I]^{5}}$. It remains to prove that they are dense.

The key idea is to divide ${\textstyle [0,1]^{2}}$ into an overlapping system of small squares, each with a unique address, and define ${\textstyle g}$ to have the appropriate value at each address.

Grid system

Let ${\textstyle \psi _{1}\in C[I]}$. For any ${\textstyle \epsilon >0}$, for all large ${\textstyle N}$, we can discretize ${\textstyle \psi _{1}}$ into a continuous function ${\textstyle \phi _{1}}$ satisfying the following properties:

• ${\textstyle \phi _{1}}$ is constant on each of the intervals ${\textstyle [0/5N,4/5N],[5/5N,9/5N],\dots ,[1-5/5N,1-1/5N]}$.

• These values are different rational numbers.
• ${\textstyle \|\psi _{1}-\phi _{1}\|<\epsilon }$.

This function ${\textstyle \phi _{1}}$ creates a grid address system on ${\textstyle [0,1]^{2}}$, divided into streets and blocks. The blocks are of form ${\textstyle [0/5N,4/5N]\times [0/5N,4/5N],[0/5N,4/5N]\times [5/5N,9/5N],\dots }$.

An example construction of $\phi$ and the corresponding grid system.

Since ${\textstyle f}$ is continuous on ${\textstyle [0,1]^{2}}$, it is uniformly continuous. Thus, we can take ${\textstyle N}$ large enough, so that ${\textstyle f}$ varies by less than ${\textstyle 1/7}$ on any block.

On each block, ${\textstyle \phi _{1}(x)+t\phi _{1}(y)}$ has a constant value. The key property is that, because ${\textstyle t}$ is irrational, and ${\textstyle \phi _{1}}$ is rational on the blocks, each block has a different value of ${\textstyle \phi _{1}(x)+t\phi _{1}(y)}$.

So, given any 5-tuple ${\textstyle (\psi _{1},\dots ,\psi _{5})}$, we construct such a 5-tuple ${\textstyle (\phi _{1},\dots ,\phi _{5})}$. These create 5 overlapping grid systems.

Enumerate the blocks as ${\textstyle R_{i,r}}$, where ${\textstyle R_{i,r}}$ is the ${\textstyle r}$ -th block of the grid system created by ${\textstyle \phi _{i}}$. The address of this block is ${\textstyle a_{i,r}:=\phi _{i}(x)+t\phi _{i}(y)}$, for any ${\textstyle (x,y)\in R_{i,r}}$. By adding a small and linearly independent irrational number (the construction is similar to that of the Hamel basis) to each of ${\textstyle (\phi _{1},\dots ,\phi _{5})}$, we can ensure that every block has a unique address.

By plotting out the entire grid system, one can see that every point in ${\textstyle [0,1]^{2}}$ is contained in 3 to 5 blocks, and 2 to 0 streets.

Construction of g

For each block ${\textstyle R_{i,r}}$, if ${\textstyle f>0}$ on all of ${\textstyle R_{i,r}}$ then define ${\textstyle g(a_{i,r})=+1/7}$; if ${\textstyle f<0}$ on all of ${\textstyle R_{i,r}}$ then define ${\textstyle g(a_{i,r})=-1/7}$. Now, linearly interpolate ${\textstyle g}$ between these defined values. It remains to show this construction has the desired properties.

For any ${\textstyle (x,y)\in I^{2}}$, we consider three cases.

If ${\textstyle f(x,y)\in [1/7,7/7]}$, then by uniform continuity, ${\textstyle f>0}$ on every block ${\textstyle R_{i,r}}$ that contains the point ${\textstyle (x,y)}$. This means that ${\textstyle g=1/7}$ on 3 to 5 of the blocks, and have an unknown value on 2 to 0 of the streets. Thus, we have $$\sum _{i=1}^{5}g(\phi _{i}(x)+t\phi _{i}(y))\in [1/7,5/7]$$ giving$${\Big |}f(x,y)-\sum _{i=1}^{5}g(\phi _{i}(x)+t\phi _{i}(y)){\Big |}\in [0,6/7]$$Similarly for ${\textstyle f(x,y)\in [-7/7,-1/7]}$.

If ${\textstyle f(x,y)\in [-1/7,1/7]}$, then since ${\textstyle \|g\|\leq 1/7}$, we still have $${\Big |}f(x,y)-\sum _{i=1}^{5}g(\phi _{i}(x)+t\phi _{i}(y)){\Big |}\in [0,6/7]$$

Baire category theorem

Iterating the above construction, then applying the Baire category theorem, we find that the following kind of 5-tuples are open and dense in $C[I]^{5}$: There exists a sequence of ${\textstyle g_{1},g_{2},\dots }$ such that ${\textstyle \|g_{1}\|<{\frac {1.01}{7}}\|f\|}$, ${\textstyle \|g_{2}\|<{\frac {1.01}{7}}{\frac {6.01}{7}}\|f\|}$, etc. This allows allows their sum to be defined: ${\textstyle g:=\sum _{n}g_{n}}$, which is still continuous and bounded, and it satisfies $$f(x,y)=\sum _{i=1}^{5}g(\phi _{i}(x)+t\phi _{i}(y))$$Since ${\textstyle C[I^{2}]}$ has a countable dense subset, we can apply the Baire category theorem again to obtain the full theorem.

Extensions

The above proof generalizes for ${\textstyle n}$-dimensions: Divide the cube ${\textstyle [0,1]^{n}}$ into ${\textstyle (2n+1)}$ interlocking grid systems, such that each point in the cube is on ${\textstyle (n+1)}$ to ${\textstyle (2n+1)}$ blocks, and ${\textstyle 0}$ to ${\textstyle n}$ streets. Now, since ${\textstyle (n+1)>n}$, the above construction works.

Indeed, this is the best possible value. We cannot reduce it to ${\textstyle 2n}$ (Sternfeld, 1985 ), with a relatively short proof given in via dimension theory.

Theorem. One can pick such a tuple to be strictly monotonically increasing.

Sources

• Andrey Kolmogorov, "On the representation of continuous functions of several variables by superpositions of continuous functions of a smaller number of variables", Proceedings of the USSR Academy of Sciences, 108 (1956), pp. 179–182; English translation: Amer. Math. Soc. Transl., "17: Twelve Papers on Algebra and Real Functions" (1961), pp. 369–373.
• Vladimir Arnold, "On functions of three variables", Proceedings of the USSR Academy of Sciences, 114 (1957), pp. 679–681; English translation: Amer. Math. Soc. Transl., "28: Sixteen Papers on Analysis" (1963), pp. 51–54. SpringerLink
• Vladimir Arnold, "On the representation of continuous functions of three variables as superpositions of continuous functions of two variables", Dokl. Akad. Nauk. SSSR 114:4 (1957), pp. 679–681 (in Russian) SpringerLink
• Andrey Kolmogorov, "On the representation of continuous functions of several variables as superpositions of continuous functions of one variable and addition", (1957); English translation: Amer. Math. Soc. Transl., "28: Sixteen Papers on Analysis" (1963), PDF

Further reading

• S. Ya. Khavinson, Best Approximation by Linear Superpositions (Approximate Nomography), AMS Translations of Mathematical Monographs (1997)