Kolmogorov–Arnold representation theorem

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.{{cite journal|first=David|last=Hilbert|authorlink=David Hilbert|title= Mathematical problems|journal=Bulletin of the American Mathematical Society|volume=8|issue=10|year=1902|pages=461–462|doi=10.1090/S0002-9904-1902-00923-3|doi-access=free}} 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\}+\backslash cdots\; +a\_\{0\}=0$

can be translated to the form $y^\{n\}+b\_\{n-4\}y^\{n-4\}+\backslash 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 and as a superposition of functions of $n-4$ variables if $n\backslash geq\; 7$. For $n=7$ the solution is a superposition of arithmetic operations, radicals, and the solution of the equation {{nowrap|$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.Jürgen Braun, On Kolmogorov's Superposition Theorem and Its Applications, SVH Verlag, 2010, 192 pp.

A variant of Kolmogorov's theorem that reduces the number of

outer functions $\backslash Phi\_\{q\}$ is due to George Lorentz.{{cite journal|first=G. G.|last=Lorentz|title=Metric entropy, widths, and superpositions of functions|journal=American Mathematical Monthly|volume=69 |issue=6|year=1962|pages=469–485 |doi=10.1080/00029890.1962.11989915}} He showed in 1962 that the outer functions $\backslash Phi\_\{q\}$ can be replaced by a single function $\backslash Phi$. More precisely, Lorentz proved the existence of functions $\backslash phi\; \_\{q,p\}$, $q=0,1,\backslash ldots,\; 2n$, $p=1,\backslash ldots,n,$ such that

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

David Sprecher {{cite journal | doi=10.2307/1994273 | jstor=1994273 | title=On the Structure of Continuous Functions of Several Variables | last1=Sprecher | first1=David A. | journal=Transactions of the American Mathematical Society | date=1965 | volume=115 | pages=340–355 }} replaced the inner functions $\backslash phi\_\{q,p\}$ by one single inner function with an appropriate shift in its argument. He proved that there exist real values $\backslash eta,\; \backslash lambda\_1,\backslash ldots,\backslash lambda\_n$, a continuous function $\backslash Phi\backslash colon\; \backslash mathbb\{R\}\; \backslash rightarrow\; \backslash R$, and a real increasing continuous function $\backslash phi\backslash colon\; [0,1]\; \backslash rightarrow\; [0,1]$ with $\backslash phi\; \backslash in\; \backslash operatorname\{Lip\}(\backslash ln\; 2/\backslash ln\; (2N+2))$, for $N\; \backslash geq\; n\; \backslash geq\; 2$, such that

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

Phillip A. Ostrand {{cite journal|first=Phillip A.|last= Ostrand|title=Dimension of metric spaces and Hilbert's problem 13|journal= Bulletin of the American Mathematical Society|volume= 71 |issue= 4|year=1965|pages= 619–622|doi=10.1090/s0002-9904-1965-11363-5|doi-access= free}} generalized the Kolmogorov superposition theorem to compact metric spaces. For $p=1,\backslash ldots,m$ let $X\_p$ be compact metric spaces of finite dimension $n\_p$ and let $n\; =\; \backslash sum\_\{p=1\}^\{m\}\; n\_p$. Then there exists continuous functions $\backslash phi\_\{q,p\}\backslash colon\; X\_p\; \backslash rightarrow\; [0,1],\; q=0,\backslash ldots,2n,\; p=1,\backslash ldots,m$ and continuous functions $G\_q\backslash colon\; [0,1]\; \backslash rightarrow\; \backslash R,\; q=0,\backslash ldots,2n$ such that any continuous function $f\backslash colon\; X\_1\; \backslash times\; \backslash dots\; \backslash times\; X\_m\; \backslash rightarrow\; \backslash mathbb\{R\}$ is representable in the form

:$f(x\_1,\backslash ldots,x\_m)\; =\; \backslash sum\_\{q=0\}^\{2n\}\; G\_\{q\}\backslash !\backslash left(\backslash sum\_\{p=1\}^\{m\}\; \backslash phi\_\{q,p\}(x\_\{p\})\backslash right).$

Kolmogorov–Arnold representation theorem and its aforementioned variants also hold for discontinuous multivariate functions.{{Cite journal |last=Ismailov |first=Vugar |year=2008|title=On the representation by linear superpositions |journal=Journal of Approximation Theory |language=en |volume=151 |issue=2 |pages=113–125 |doi=10.1016/j.jat.2007.09.003|arxiv=1501.05268 }}

In its classic form Kolmogorov–Arnold representation has two layers, where the first, called inner layer, is vector to vector mapping

:$s\_q\; =\; \backslash sum\_\{p=1\}^\{n\}\; \backslash phi\_\{q,p\}(x\_\{p\}),\; \backslash quad\; q=0,1,..,2n$

and the second, outer layer, is vector to scalar mapping

:$f(x\_1,\; ...\; ,\; x\_m)\; =\; \backslash sum\_\{q=0\}^\{2n\}\; \backslash Phi\_q\backslash left(s\_q\backslash right).$

The transition from discrete to continuous form for inner layer gives equation of Urysohn with 3D kernel

:$s(q)\; =\; \backslash int\_\{p\_1\}^\{p\_2\}\; F[x(p),p,q]dp,\; \backslash quad\; q\; \backslash in\; [q\_1,\; q\_2],$

same transition for the outer layer gives its particular case

:$f\; =\; \backslash int\_\{q\_1\}^\{q\_2\}\; G[s(q),q]dq.$

The generalization of Kolmogorov-Arnold representation known as Kolmogorov-Arnold network in continuous form

is a chain of Urysohn equations, where outer equation also may return function or a vector as multiple related targets.

Urysohn equation was introduced in 1924 for a different purpose, as function to function mapping with the problem

of finding function $x(p)$, provided $s(q)$ and $F[x(p),p,q]$.

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,{{cite journal | doi=10.1162/neco.1989.1.4.465 | title=Representation Properties of Networks: Kolmogorov's Theorem is Irrelevant | date=1989 | last1=Girosi | first1=Federico | last2=Poggio | first2=Tomaso | journal=Neural Computation | volume=1 | issue=4 | pages=465–469 }} although there is some debate on this.{{cite journal | doi=10.1162/neco.1991.3.4.617 | title=Kolmogorov's Theorem is Relevant | date=1991 | last1=Kůrková | first1=Věra | journal=Neural Computation | volume=3 | issue=4 | pages=617–622 | pmid=31167327 }}

In the field of machine learning, there have been various attempts to use neural networks modeled on the Kolmogorov–Arnold representation.{{cite journal |last1=Lin |first1=Ji-Nan |last2=Unbehauen |first2=Rolf |date=January 1993 |title=On the Realization of a Kolmogorov Network |journal=Neural Computation |volume=5 |pages=18–20 |doi=10.1162/neco.1993.5.1.18 |number=1}}{{cite book |last=Köppen |first=Mario |title=Artificial Neural Networks — ICANN 2002 |date=2022 |isbn=978-3-540-44074-1 |series=Lecture Notes in Computer Science |volume=2415 |pages=474–479 |chapter=On the Training of a Kolmogorov Network |doi=10.1007/3-540-46084-5_77 |chapter-url=https://link.springer.com/chapter/10.1007/3-540-46084-5_77}}KAN: Kolmogorov-Arnold Networks. (Ziming Liu et al.){{Cite news |author=Manon Bischoff |date=May 28, 2024 |title=An Alternative to Conventional Neural Networks Could Help Reveal What AI Is Doing behind the Scenes |url=https://www.scientificamerican.com/article/an-alternative-to-conventional-neural-networks-could-help-reveal-what-ai-is/ |archive-url=https://archive.today/20240529122452/https://www.scientificamerican.com/article/an-alternative-to-conventional-neural-networks-could-help-reveal-what-ai-is/ |archive-date=May 29, 2024 |access-date=May 29, 2024 |newspaper=Scientific American}}{{cite journal |last1=Ismayilova |first1=Aysu |last2=Ismailov |first2=Vugar |date=August 2024 |title=On the Kolmogorov Neural Networks |journal=Neural Networks |volume=176 | number=Article 106333 |doi=10.1016/j.neunet.2024.106333|pmid=38688072 |arxiv=2311.00049 }}{{Cite news |author=Steve Nadis |date=September 11, 2024 |title=Novel Architecture Makes Neural Networks More Understandable |url=https://www.quantamagazine.org/novel-architecture-makes-neural-networks-more-understandable-20240911/ |newspaper=Quanta Magazine}}{{cite journal |last1=Polar |first1=Andrew |last2=Poluektov |first2=Michael |date=March 2021 |title=A deep machine learning algorithm for construction of the Kolmogorov–Arnold representation |journal=Engineering Applications of Artificial Intelligence |volume=99 |doi=10.1016/j.engappai.2020.104137 |arxiv=2001.04652 }} In these works, the Kolmogorov–Arnold theorem plays a role analogous to that of the universal approximation theorem in the study of multilayer perceptrons.

Here one example is proved. This proof closely follows.{{Cite journal |last=Morris |first=Sidney |date=January 2021 |title=Hilbert 13: Are there any genuine continuous multivariate real-valued functions? |url=https://www.ams.org/journals/bull/2021-58-01/S0273-0979-2020-01698-8/ |journal=Bulletin of the American Mathematical Society |language=English |volume=58 |issue=1 |pages=107–118 |doi=10.1090/bull/1698 |issn=0273-0979|doi-access=free }} A proof for the case of functions depending on two variables is given, as the generalization is immediate.

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

We say that a 5-tuple $(\backslash phi\_1,\; \backslash dots,\; \backslash phi\_5)\; \backslash in\; C[I]^5$ is a Kolmogorov–Arnold tuple if and only if for any $f\; \backslash in\; C[I^2]$ there exists a continuous function $g:\; \backslash R\; \backslash to\; \backslash 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:

{{Math theorem|name=Theorem|note=|math_statement=

The Kolmogorov–Arnold tuples make up an open and dense subset of $C[I]^5$.

}}

Fix a $f\; \backslash in\; C[I^2]$. We show that a certain subset $U\_f\; \backslash subset\; C[I]^5$ is open and dense: There exists continuous $g$ such that , 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 $\backslash |f\backslash |\; =\; 1$ with no loss of generality.

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

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

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

• $\backslash phi\_1$ is constant on each of the intervals $[0/5N,\; 4/5N],\; [5/5N,\; 9/5N],\; \backslash dots,\; [1-5/5N,\; 1-1/5N]$.

• These values are different rational numbers.
• .

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

File:Kolmogorov-Arnold grid.svg

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

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

So, given any 5-tuple $(\backslash psi\_1,\; \backslash dots,\; \backslash psi\_5)$, we construct such a 5-tuple $(\backslash phi\_1,\; \backslash dots,\; \backslash phi\_5)$. These create 5 overlapping grid systems.

Enumerate the blocks as $R\_\{i,\; r\}$, where $R\_\{i,r\}$ is the $r$ -th block of the grid system created by $\backslash phi\_i$. The address of this block is $a\_\{i,\; r\}\; :=\; \backslash phi\_i(x)\; +\; t\; \backslash phi\_i(y)$, for any $(x,\; y)\; \backslash 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 $(\backslash phi\_1,\; \backslash dots,\; \backslash 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 $[0,\; 1]^2$ is contained in 3 to 5 blocks, and 2 to 0 streets.

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

For any $(x,\; y)\; \backslash in\; I^2$, we consider three cases.

If $f(x,\; y)\; \backslash in\; [1/7,\; 7/7]$, then by uniform continuity, $f\; >\; 0$ on every block $R\_\{i,\; r\}$ that contains the point $(x,\; y)$. This means that $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 $f(x,\; y)\; \backslash in\; [-7/7,\; -1/7]$.

If $f(x,\; y)\; \backslash in\; [-1/7,\; 1/7]$, then since $\backslash |g\backslash |\; \backslash 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]

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 $g\_1,\; g\_2,\; \backslash dots$ such that , , etc. This allows their sum to be defined: $g\; :=\; \backslash 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 $C[I^2]$ has a countable dense subset, we can apply the Baire category theorem again to obtain the full theorem.

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

Indeed, this is the best possible value.

{{Math theorem|name=Theorem|note=Sternfeld, 1985 {{Cite journal |last=Sternfeld |first=Y. |date=1985-03-01 |title=Dimension, superposition of functions and separation of points, in compact metric spaces |url=https://link.springer.com/article/10.1007/BF02761117 |journal=Israel Journal of Mathematics |language=en |volume=50 |issue=1 |pages=13–53 |doi=10.1007/BF02761117 |issn=1565-8511|url-access=subscription }}

|math_statement=

Let $X$ be a compact metric space with $\backslash operatorname\{dim\}\; X\; \backslash geq\; 2$, and let $X\; \backslash subset\; \backslash R^m$ be an embedding such that every $f\; \backslash in\; C[X]$ can be represented as

f\left(x_1, x_2, \ldots, x_m\right)=\sum_{i=1}^m g_i\left(x_i\right), \quad\left(x_1, x_2, \ldots, x_m\right) \in X, \quad g_i \in C[\R].

Then $m\; \backslash geq\; 2\; \backslash operatorname\{dim\}\; X+1$.

}}

A relatively short proof is given in {{Cite journal |last=Levin |first=Michael |date=1990-06-01 |title=Dimension and superposition of continuous functions |url=https://link.springer.com/article/10.1007/BF02807868 |journal=Israel Journal of Mathematics |language=en |volume=70 |issue=2 |pages=205–218 |doi=10.1007/BF02807868 |issn=1565-8511|url-access=subscription }} via dimension theory.

In another direction of generality, more conditions can be imposed on the Kolmogorov–Arnold tuples.

{{Math theorem|name=Theorem|note=

|math_statement=

There exists a Kolmogorov–Arnold tuple where each function is strictly monotonically increasing.

}}

The proof is given in.{{cite book |first=Torbjörn |last=Hedberg |chapter=Appendix 2: The Kolmogorov superposition theorem |title=Topics in Approximation Theory |editor-last=Shapiro |editor-first=Harold S. |series=Lecture Notes in Mathematics |publisher=Springer |volume=187 |orig-year=1971 |pages=267–275, (33– of PDF) |isbn=978-3-540-36497-9 |doi=10.1007/BFb0058976 |date=2006 |chapter-url=https://link.springer.com/content/pdf/bbm:978-3-540-36497-9/1}}

(Vituškin, 1954){{cite journal |first=A.G. |last=Vituškin |title=On Hilbert's Thirteenth Problem |language=ru |journal=Doklady Akad. Nauk SSSR |series=New Series |volume=95 |issue=4 |year=1954 |pages=701–4}} showed that the theorem is false if we require all functions $f,\; g,\backslash phi\_i$ to be continuously differentiable. The theorem remains true if we require all $\backslash phi\_i$ to be 1-Lipschitz continuous.

{{reflist}}

• 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: [https://bookstore.ams.org/view?ProductCode=TRANS2/17 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: [https://bookstore.ams.org/view?ProductCode=TRANS2/28 Amer. Math. Soc. Transl., "28: Sixteen Papers on Analysis" (1963)], pp. 51–54. [https://link.springer.com/chapter/10.1007/978-3-642-01742-1_2 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) [https://link.springer.com/chapter/10.1007/978-3-642-01742-1_6 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: [https://bookstore.ams.org/view?ProductCode=TRANS2/28 Amer. Math. Soc. Transl., "28: Sixteen Papers on Analysis" (1963)], [https://cs.uwaterloo.ca/~y328yu/classics/Kolmogorov57.pdf PDF]

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

{{DEFAULTSORT:Kolmogorov-Arnold representation theorem}}

Category:Theorems in real analysis

Category:Functions and mappings

Category:Theorems in approximation theory