Are there any simple examples of Kolmogorov-Arnold representation? 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.
 A: 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.
A: 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.
