I'm trying to express $\min(x_1,\ldots,x_n)$ function in terms of (not nested) ReLU functions relu(x):=max(x,0). The end result should be something like $\min(x_1,\ldots,x_n)=\sum_{i_1,\ldots,i_k}c_i\max(g_i(x_{i_1},\ldots,x_{i_k}),0)$, for some function $g$ (e.g., an addition), indices $i_1,\ldots,i_k\in\{1,\ldots, n\}$, and constants $c_i\in\mathbb{R}$.
Let's start:
From basic algebra (I assume henceforth $x,y\in\mathbb{R}$) we know that $|x|=\max(x,0)+\max(-x,0)$ and $x=\max(x,0)-\max(-x,0)$. I join this with $\min(x,y)=\frac 12 (x+y-|x-y|)$ to obtain $$ \min(x,y)=\frac 12 \left(\max(x+y,0)-\max(-x-y,0)-\max(x-y,0)-\max(-x+y,0)\right). $$
So far so good. By induction it holds that $\min(x_1,\ldots,x_n)=\min(x_1,\min(x_2,\ldots,x_n))$. The problem starts with $\min(x_1,x_2,x_3)$, as calculations get ugly: $$ \min(x_1,x_2,x_3)=\min(x_1,\min(x_2,x_3))=\frac 12 (\max(x_1+\max(x_2+x_3,0)-\max(-x_2-x_3,0)-\max(x_2-x_3,0)-\max(-x_2+x_3,0),0) - \text{3-other-terms-like-that}. $$ We can simplify $\max(x_1+\max(x_2+x_3,0))=\max(x_1+x_2+x_3,x_1)$, but it does not help much as in general it is not possibly (imho) to further simplify eq. of type $$ \max(\max(x_1+x_2+x_3,x_1)-\max(-x_2-x_3,0)-\max(x_2-x_3,0)-\max(-x_2+x_3,0),0) $$ into not nested max functions, not to mention ReLUs.
I also thought of writing it as a recurrent equation $$ f(x_1,\ldots,x_n)=\frac 12 (relu(x_1+f(x_2,\ldots,x_n))-relu(-x_1-f(x_2,\ldots,x_n)) - relu(x_1-f(x_2,\ldots,x_n)) - relu(-x_1+f(x_2,\ldots,x_n)) ) $$ with the initial condition $f(x_1)=x_1$, but so far couldn't figure out anything more from that. Mathematica was not useful either.
I would greatly appreciate any hints.
Thanks!
I am not sure what you meant by no recurrence since when you compute a summation, unless I am mistaken, you are practically using a recurrence especially when dealing with an arbitrary number of elements.
Now if you meant that you can’t use $min(x,y)$ in a recurrence and you are ok using the Relu function. In that case, @kurt gave a simpler use if the maximum function. Here it is broken down:
First we notice that $min(x_1,x_2,x_3,…)=-max(-x_1,-x_2,-x_3,…)$
So to make the answer easier to write, let $y_1=-x_1, y_2=-x_2, y_3=-x_3,…$
Knowing that $max(y_1,y_2)=y_2+max(y_1-y_2,0)$
We can recursively build the maximum of the $y_i$ by taking $z_1=y_1$ $z_2=y_2+max(y_2-z_1,0)$ . . . $z_n=y_n+max(y_n-z_{n-1})$
Finally, $min(x_1,x_2,x_3,…)=-z_n$