Here is a question that occurred to me while learning about neural networks. For $t\in\mathbb{R}$ put $t\_+=\max(0,t)$, so $t\_+=t$ if $t\geq 0$ and $t\_+=0$ if $t\leq 0$. (This is RELU=rectified linear unit in neural network language.) Note that $t=t\_+-(-t)\_+$ and $|t|=t\_++(-t)\_+$.


For the maximum of two variables we have
\begin{align\*}
 \max(x,y) &= x + (y-x)\_+ \\
 &= \left(x+y+(x-y)\_++(y-x)\_+\right) /2 \\
 &= \left((x+y)\_+-(-x-y)\_++(x-y)\_++(y-x)\_+\right)/2
\end{align\*}
Is there a similar expression for $\max(x,y,z)$ as a linear combination of terms $\phi(x,y,z)\_+$ with $\phi$ linear? I suspect not, but I have not found a proof. More generally, is there a nice characterisation of the functions of several variables that do admit such a representation?



RELU representation of $\max(x,y,z)$
There's indeed no such way to write $\max(x,y,z)$.


**Lemma.** Consider on $\mathbf{R}^n$ a function $f(x)=\sum\_{i\in I}^m t\_iL\_i(x)\_+$ where the $L\_i$ are nonzero, pairwise non-positively-collinear linear forms, $t\_i$ are nonzero scalars. Suppose that
for some $i$, $f$ is locally linear at $x\_0$ with $x\_0\in\mathrm{Ker}(L\_i)$. Then there exists $j$ (unique) such that $t\_iL\_i-t\_jL\_j=0$.


[So $L\_j=\frac{t\_i}{t\_j}L\_i$; since these are not positively collinear, necessarily $t\_i$ and $t\_j$ have distinct signs and in particular $j\neq i$. This also proves uniqueness. Thus the contribution $t\_iL\_i(x)\_++t\_jL\_j(x)\_+$ is linear, namely equal to $t\_iL\_i(x)$.]


*Proof.* Induction on $n$. For $n=1$, necessarily $m\le 2$. We can suppose $i=1$. We can rescale to assume $L\_1(x)=x$. So $\mathrm{Ker}(L\_1)=\{0\}$. So $f(x)=x\_++t(ax)\_+$ with $a\le 0$, for all $x$. The only possibility to get $f$ smooth at $0$ is to have $a=-1$.


For $n=2$, if no $L\_j$, $j\neq i$, is collinear to $L\_i$, then all such $L\_j$ are smooth at $x\_0$, and we get a contradiction. So for some $j$, $L\_j$ is collinear to $L\_i$, and we see that the only possibility for scalars is $t\_iL\_i=t\_jL\_j$.


For $n\ge 3$. Fix $i$ as in the lemma; up to rescale, we can suppose $t\_i=1$. Let $P$ be any hyperplane passing through $x\_0$. By induction, there exist $j\_P$ such that in restriction to $P$ we have $L\_i=t\_{j\_P}L\_{j\_P}$.


Suppose by contradiction that $L\_i-t\_jL\_j$ is nonzero for all $j\neq i$. Then there exists $x$ such that $L\_i(x)-t\_jL\_j(x)\neq 0$ for all $j$. Let $P$ be a hyperplane passing through $x\_0$ and $x$. Then we get a contradiction.


**Corollary.** There is no function of the form $x\mapsto\sum\_j t\_jL\_j(x)\_+$ ($L\_j$ linear) on $\mathbf{R}^3$ that equals $f:(x,y,z)\mapsto \max(x,y,z)$.


*Proof.* Write it as $x\mapsto\sum\_k L\_k(x)\_++a\_kL\_k(-x)\_+$, where the $L\_k$ are nonzero and pairwise non-collinear. When $\mathrm{Ker}(L\_k)$ is not one of the hyperplanes $x\_i=x\_j$, there is an element in this kernel at which $f$ is locally linear (namely any point with three distinct coordinates). Then the lemma ensures that $a\_k=-1$, so that the contribution $L\_k(x)\_+-L\_k(-x)\_+$ is linear. So we can rewrite the given map as
$$f(x)(=\max(x\_1,x\_2,x\_3))=L(x)+ \sum\_{1\le i\neq j\le 3}a\_{ij}(x\_i-x\_j)\_+$$
with $L$ linear. Write $L(x)=\sum\_{i=1}^3a\_ix\_i$.


Since $f$ is symmetric, we have $f(x\_1,x\_2,x\_3)=\frac16\sum\_{\sigma\in\mathfrak{S}\_3}f(x\_{\sigma(1)},x\_{\sigma(2)},x\_{\sigma(3)})$. Hence we can suppose that the $a\_i$ and $a\_{ij}$ are symmetric too, which means that $a\_i=b$ for some $b$ and $a\_{ij}=c$ for some $c$. Thus
$$f(x)=b(x\_1+x\_2+x\_3)+c\left(\sum\_{1\le i\neq j\le 3}(x\_i-x\_j)\_+\right)$$
for all $x$.
Evaluation at $x=(1,1,1)$ yields $b=1/3$. Evaluation at $x=(0,0,1)$ yields $1=b+2c$, so $c=1/3$, and evaluation at $x=(0,0,-1)$ yields $0=-b+4c$, and this is a contradiction.


