# De-Nesting Absolute Value Function into Linear Combination of Absolute Value Functions

Context: In formulating problems for secondary school mathematics teachers (and students) about absolute value functions, which we define as functions $$\mathbb{R} \rightarrow \mathbb{R}$$ that send $$x \mapsto a|x-h|+k$$ for fixed parameters $$a, h, k \in \mathbb{R}$$, I was able to rewrite the nested absolute value function

$$f(x) = \Big||x|-1\Big|$$

as a linear combination of absolute value functions,

$$g(x) = |x+1| + |x-1| - (|x|+1)$$

(You can view the graphs of $$f$$ and $$g$$ here; although not delved into in this post, my colleagues enjoyed finding similar relationships even when there is a quadratic $$x$$ term, for example, in the graphs/functions depicted here.)

My question is twofold (although the follow-up question depends on the first answer):

1. Is it true that every nested absolute value function (NAVF) or linear combination of NAVFs can be written as a linear combination of AVFs?

2a. If not, what is a counterexample, and what criteria must be satisfied for de-nesting to be possible?

2b. If so, is there an algorithm for de-nesting, i.e., rewriting an arbitrary NAVF as a linear combination of AVFs?

Pointers to related literature/references would be welcome, even if they do not explicitly answer the questions above. Please edit the questions, title, or tags if you believe it will improve clarity.

$\newcommand{\al}{\alpha} \newcommand{\de}{\delta} \newcommand{\De}{\Delta} \newcommand{\ep}{\varepsilon} \newcommand{\ga}{\gamma} \newcommand{\Ga}{\Gamma} \newcommand{\la}{\lambda} \newcommand{\Si}{\Sigma} \newcommand{\thh}{\theta} \newcommand{\om}{\omega} \newcommand{\R}{\mathbb{R}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\F}{\mathcal{F}} \newcommand{\E}{\operatorname{\mathsf E}} \renewcommand{\P}{\operatorname{\mathsf P}} \newcommand{\ii}{\operatorname{\mathsf I}\{#1\}} \newcommand{\tf}{\widetilde{f}}$

Lemma 3 in Explicit additive decomposition of norms (which is Lemma 1.2 in the arXiv version of that note) states the following:

Suppose that $f\colon\R\to\R$ is a convex function such that for some real $k$ there exist finite limits \begin{equation*} d_+:=d_{f,k;+}:=\lim_{u\to\infty}[f(u)-ku]\quad\text{and}\quad d_-:=d_{f,k;-}:=\lim_{u\to-\infty}[f(u)+ku]. \end{equation*} Then for all $x\in\R$ \begin{equation*} f(x)=\frac{d_++d_-}2+\frac12\,\int_\R|x-t|\,d f'(t). \tag{1} \end{equation*}

As is clear from the short proof, this lemma holds for any absolutely continuous function $f$ with (possibly infinite) limits $\lim_{x\to\pm\infty}f'(x)$. So, it is easy to see by induction on the nesting depth that the lemma holds for any nested absolute value function.

For a finite nesting depth, the function $f$ is piecewise-affine: \begin{multline*} f(x)=(a_1+b_1 x)\ii{x\le t_1}+(a_2+b_2 x)\ii{t_1<x\le t_2}+\dots \\ +(a_n+b_n x)\ii{t_{n-1}<x\le t_n} +(a_{n+1}+b_{n+1} x)\ii{x>t_n} \end{multline*} for some natural $n$, some real "switch points" $t_1<\dots<t_n$, some real $a_i$ and $b_i$'s, and all real $x$, where $\ii\cdot$ denotes the the indicator. So, the integral in the lemma reduces to a sum: \begin{equation*} f(x)=\frac{d_++d_-}2+\frac12\,\sum_1^n|x-t_i|\,\De f'(t_i) \tag{2} \end{equation*} for all real $x$, where $\De f'(t):=f'(t+)-f'(t-)$, the "jump" of $f'$ at $t$, so that $\De f'(t_i):=b_{i+1}-b_i$ for all $i=1,\dots,n$.
• Could you describe how to use the algorithm in your mentioned proof to de-nest a function such as $$f(x) = \Big|\big|3|x|-1\big| - 4\big|x-1\big|\Big|$$? I know that it is possible as can be seen here; but, I am not sure how your Lemma 1.2 could accomplish this. Thanks! Jun 1 '18 at 0:16
• This is great! It looks like you input an example from an earlier comment (which had mismatched absolute value signs) rather than the $f(x)$ above, but your updated answer is clarifying. (Here is the function you addressed with its input and output.) Thanks! Jun 1 '18 at 10:18