9
$\begingroup$

I had never heard of the Kolmogorov-Arnold Representation Theorem before. It states roughly that any multivariable function can be represented by repeatedly adding a single variable function whose input is a sum of single variable functions for each of the variables (of course, that isn't a precise statement).

Here is the formula for a function of $x$ and $y$ (i.e. that $n=2$) using Theorem $2$ from this paper: $$f(x,y)=\sum_{k=1}^5 g(\phi_k(x)+\lambda \phi_k(y))$$

Note that this representation is a bit differently written. We have $k=q+1$ and $\phi(x+k\epsilon)=\phi_k(x).$

Are there any simple (and non-trivial) examples? I have searched around online and can only find what seems to be very complicated proofs of the theorem but no actual concrete examples.

How about $f(x,y)=x^2+y$ or $f(x,y)=xy^3$, etc.? I really don't see a simple way to construct such $g$ and $\phi_k$.

Also, I couldn't figure out which tags would be appropriate here.

$\endgroup$
14
  • $\begingroup$ You do not expect the approximating function to have this special form. $\endgroup$ – Hans Engler Nov 13 '17 at 18:25
  • $\begingroup$ @HansEngler, What do you mean? Do you mean that I have made an error in my interpretation of the Kolmogorov-Arnold representation theorem? Or do you mean that the functions $\phi_k$ will generally not have such a 'nice' closed form. $\endgroup$ – jdods Dec 2 '17 at 15:43
  • $\begingroup$ It should be $f(x,y)=\sum_{k=1}^5 g_k(\phi_k(x)+\psi_k(y))$. And that is obviously possible. $\endgroup$ – Hans Engler Dec 2 '17 at 19:07
  • $\begingroup$ @HansEngler, see theorem 2 in sciencedirect.com/science/article/pii/0022247X72901291 I think the way I have written it is valid. $\endgroup$ – jdods Dec 2 '17 at 21:07
  • 2
    $\begingroup$ I was looking for the same answer. In "Kolmogorov's Theorem and Multilayer Neural Networks", the author Vera Kurkova says that "However, possessing even fractal graphs, the functions $\psi_q$ and $\phi$ are highly nonsmooth" (page 503, 3rd paragraph). Here $\psi_q$ is your $\phi_k$, and $\phi$ is your $g$: thus, I would say that there are no such simple examples. $\endgroup$ – Maurizio Parton Aug 26 '18 at 17:04
1
$\begingroup$

There are some nice examples I found here, although admittedly the representation is not exactly what you are asking for:

$$ f(x,y) = xy = \operatorname{exp}(\operatorname{log}x + \operatorname{log}y) $$

and

$$ f(x,y,z) = x^yz = \operatorname{exp}(\operatorname{exp}(\operatorname{log}y+\operatorname{log} \operatorname{log}x)+(−\operatorname{log}z)) $$

If you follow the link you will see that their constructive proof of the representation you give is `not nice', in the sense that it relies on getting an approximation with an $\epsilon$-bound error and then repeating the approximation to show that the error tends to zero. This recursive trick means that valid choices for $g_k$ can be pretty ugly and need not have a closed form. Of course this does not exclude the existence of simple examples for simple nontrivial functions, but frankly I am not hopeful.

$\endgroup$
0
$\begingroup$

In general, it is very difficult to write any multivariate function in this simpler (where I mean summations of univariate functions) form. To give a simple example, I first define the original representation theorem:

Let $f:[0,1]^{d}\rightarrow\mathbb{R}$ be continuous. There exists univariate continuous functions $g_{q},\psi_{p,q}$ such that $f(x_{1},\ldots,x_{d})=\sum_{q=0}^{2d}g_{q}\left(\sum_{p=1}^{d}\psi_{p,q}(x_{p})\right)$.

Nowadays there are better representations just as the one you state. The main reasons why there are no explicit formulas for $g_{q},\psi_{p,q}$ are that the proofs of these theorems are non-constructive. Secondly, the outer function $g_{q}$ highly depends on $f$ so we can't just choose one and lastly, the inner-function $\psi_{p,q}$ is continuous. However, it is a very rough function which makes it even more difficult to find explicit forms. The theorem only states existents of these functions. There is still a lot of research regarding this topic, since this form has similarities with a 2-layered Neural Network but this is highly debated. If you want to find more on this topic, look up Kolmogorov-Arnold representation and Neural Networks.

There are of course easy examples, Sebastiaan stated a few. In your case, the function $f_{1}(x_{1},x_{2})=x_{1}^{2}+x_{2}$ can be decomposed as in the theorem since it is a summation of continuous univariate functions. Let $g_{1}(x)=x$, $\psi_{1,1}(x_{1})=x_{1}^{2}$, $\psi_{2,1}(x_{2})=x_{2}$ and all other functions you set $g_{q}=\psi_{p,q}=0$.

More general, any form as $f_{1}$ can be written in this representation. Of course, the most trivial one is $f(x_{1},\ldots,x_{d})=0$. For $f_{2}(x,y)=x_{1}x_{2}^{3}$ it is more difficult and we run in the problems I stated above. Finally, note that $(x,y)\in[0,1]^{2}$, so we don't need to find functions for the whole domain. I hope this helps.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.