6
$\begingroup$

I was wondering if such statements are known like "any piecewise linear function from $\mathbb{R}^d \rightarrow \mathbb{R}$ can be written as $\sum_{i=1}^k \alpha_i (\text{ some $2$ piece linear function})$" (for some positive integer $k$ that depends on the given function and some real numbers $\alpha_i$ and maybe the $2$ piece function is different for each $i$).


Is there something in the theory of ``tropical varieties/geometry" which relates to such a thing?

$\endgroup$
4
  • 1
    $\begingroup$ I assume your piecewise linear functions are supposed to be patched together from linear maps on finitely many simplices (since otherwise they are unlikely to be finite sums of anything reasonable). For a given simplex $S$ and a given $i \in \left\{1,2,\ldots,n\right\}$, you can define a function which sends every $s \in S$ to the $i$-th coordinate of $s$ and every $s \notin S$ to $0$. This is a (non-continuous) pointwise-linear function. Every piecewise linear function is a finite linear combination of such beasts (provided that my assumption in the first sentence holds). $\endgroup$ Commented Sep 12, 2016 at 17:52
  • 2
    $\begingroup$ On the other hand, if you are talking of continuous piecewise linear functions, then this becomes a much more interesting problem. $\endgroup$ Commented Sep 12, 2016 at 17:53
  • $\begingroup$ ^what is a good reference to read to look for technologies to answer this? $\endgroup$ Commented Jun 17, 2017 at 18:42
  • $\begingroup$ Piecewise continuous linear (and more generally bounded-degree polynomial) functions are also of interest in the theory of multivariate splines. One classic paper is this one by Billera "Homology of smooth splines": ams.org/journals/tran/1988-310-01/S0002-9947-1988-0965757-9 $\endgroup$
    – j.c.
    Commented Oct 27, 2017 at 18:09

1 Answer 1

6
$\begingroup$

If you weren't assuming the piecewise linear function $f: \mathbb R^d \to \mathbb R$ is continuous, then I think this is true: we can just choose functions $$ f_i = \begin{cases} \text{(some linear piece of $f$)} & \text{if in domain of linear piece} \\ 0 & \text{otherwise}, \end{cases}$$ and choose all coefficients $\alpha_i = 1$, so $f = \sum_i f_i$.


If you were assuming that the function $f$ is continuous, and you want to write it as a sum of continuous two-piece linear functions, then this is false when $d\geq 2$.

Note that if $f_i$ is a two-piece linear function which is continuous, then the set of points where $f_i$ is discontinuous (i.e. the ''break locus'' of $f_i$) must be a hyperplane in $\mathbb R^d$. Thus if we take a finite sum $\displaystyle\sum_{1\leq i\leq k} \alpha_i f_i$ over such functions, the points of discontinuity will form a hyperplane arrangement in $\mathbb R^d$ with at most $k$ hyperplanes. (If ''cancellation'' occurs in the locus of discontinuity, it will happen along the whole hyperplane.)

However, when $d\geq 2$ there are many possible piecewise linear continuous functions $f:\mathbb R^d \to \mathbb R$ whose break locus is not a hyperplane arrangement. The simplest example is probably $$f(x,y) = \max\{0,x,y\} : \mathbb R^2 \to \mathbb R,$$ whose break locus is the tropical line: enter image description here

[image from Frank Sottile's website ]


If we only consider the case $d = 1$, then it is true that any piecewise linear continuous function may be expressed as a sum of two-piece such functions.

In light of the above counterexample it may be tempting to conjecture that the correct generalization is that a function $\mathbb R^d \to \mathbb R$ may be expressed as a sum of $(d+1)$-piece functions, but this is not true either, e.g. for the plane conic in $\mathbb R^2$ cut out by

$$f(x,y) = \max\{ 0, 1+x, 1+y, 1+x+y, 2x, 2y\}.$$

To explain this behavior there is a perfect analogy with polynomials over complex numbers (or any algebraically closed field), via tropical geometry / algebra:

The fundamental theorem of algebra states that any polynomial $f \in \mathbb C[x]$ may be factored as a product of linear polynomials, but it is not true that any polynomial $f \in \mathbb C[x_1,\ldots,x_d]$ has a factorization into linear polynomials when $d\geq 2$.

$\endgroup$
3
  • $\begingroup$ Thanks for the reply! My thoughts have now changed in the months intervening since I first wrote this question. Now I think what I really look for is to understand this : fix a positive integer $k$ and consider functions $f : \mathbb{R}^n \rightarrow \mathbb{R}$ given as, $\vec{x} \mapsto \sum_{i} \max \{ A_{i_1},..,A_{i_k}\}$ where each $A$ is an affine function of $\vec{x}$ and there are finite number of terms in the sum. $\endgroup$ Commented Oct 27, 2017 at 15:40
  • $\begingroup$ Now is there some way to understand how "succinctly" (choose whatever meaning seems convenient!) can this $(n,k)$ family of functions be represented in say the ``max-plus" algebra. One notion of "succinct" is allowing for the least number of nestings of "max". $\endgroup$ Commented Oct 27, 2017 at 15:41
  • $\begingroup$ To make sure I understand the question: how many nestings of "max" are there in the original expression you wrote? just one? $\endgroup$ Commented Oct 28, 2017 at 2:38

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .