linear approximation with respect to L1 norm

Question

I am trying to solve this problem: Find the best $L^1$ linear approximation of $e^x$ on [0,1] i.e. minimize $\int_0^1|e^x-\alpha-\beta x| dx$

any hints how to proceed

Answer 1

First convince yourself that an optimizer must intersect the graph of $e^x$ exactly twice in the interval $[0,1]$.

Then a better parametrization of the linear approximation is $$\ell(x) = (x - s) \cdot \frac{e^t - e^s}{t-s} + e^s$$ which intersects $e^x$ precisely at $x = s$ and $x = t$.

Then the integral being optimized is

$$ \int_0^s e^x - \ell(x) + \int_s^t \ell(x) - e^x + \int_t^1 e^x - \ell(x) $$ which we compute to be $$ e^1 - 2 e^t + 2e^s - e^0 + \frac{e^t - e^s}{2(t-s)} ( s^2 + 2(t-s)^2 - (1-s)^2) + e^s(-1 +2t - 2s) $$ The constant parts we don't really care about, the parts depending on $t,s$ we simplify, writing $u = t-s$ $$ 2 e^s( 1 - e^u) + \frac{1}{2u} e^s (e^u - 1)(2s - 1 + 2u^2) + e^s(2u-1) $$

Optimizing we get from taking $\partial_u$ $$ 0 = - \frac{1}{2u^2} (e^u - 1 - e^u u)(2s -1) - (e^u -1 - e^u u) $$ which requires either $$ 1-2s = 2u^2 \quad \text{or} \quad e^u - 1 - e^u u = 0 $$ The latter is satisfied when $ e^u = 1/(1-u) $ which only holds when $u = 0$ (noting that $u \leq 1$), which we observe corresponds to a local max. So we have $1 - 2s = 2 u^2$

The $\partial_s$ derivative gives $$ 0 = \frac{1}{2u}(e^u - 1)(2s + 1 + 2u^2 - 4u) + (2u-1)$$ plugging in from the previous equation we get $$ 0 = \frac{1}{u}(e^u - 1)(2u - 1) + (2u-1) $$ which only vanishes in $(0,1]$ with $u = \frac12$.

This implies $s = \frac14$.

So, in conclusion, the best linear approximation is $$ \ell(x) = (x - \frac14) 2 e^\frac14 (e^\frac12 - 1) + e^\frac14 $$

---

One can arrive at this answer slightly more geometrically. Consider $f_+$ the positive part of $e^x - \ell(x)$, and $f_-$ the negative part, where we write $$ \ell(x) = \beta (x - \frac12) + \alpha $$ The integral to optimise is $\int f_+ + f_-$.

We see that perturbing $\alpha$ positively decreases $\int f_+$ by exactly the amount $|\mathrm{supp} f_+|$ and increases $\int f_-$ by exactly $|\mathrm{supp} f_-|$. So the degree of freedom in perturbing $\alpha$ requires that the supports of $f_+$ and $f_-$ have the same measure. Since $\ell$ is linear this means the supports must have measure $\frac12$. (Corresponding to $u = \frac12$ above.)

From the convexity of $e^x$ we see that the support of $f_-$ is an interval of length $1/2$. The degree of freedom in $\beta$, which can be interpreted as rotating the line $\ell$ around the point $(\frac12, \alpha)$, can be easily seen to require that the support of $f_-$ is balanced around the point $x = 1/2$. This leads to the conclusion.