Lipschitz regression

lipschitz

![stuff](http://i.imgur.com/a9bAYas.png)

We have a sequence $a_1,\ldots,a_n$ and $\epsilon$. We want to output $x_1,\ldots,x_n$ such that $|a_i-x_i|\leq \epsilon$ for all $i$ and $\sum_{i=1}^n |a_i-x_i|$ is minimized.

**Claim:** We can solve the problem in $O(n\log^2 n)$ time.

**Reduction**
We reduce the problem to min-cost circulation in a outerplanar graph.

Vertices: $\{s,v_0,\ldots,v_n\}$.
Edges:
1. symmetric edges $v_iv_{i+1}$. (symmetric edge is the same as two antiparallel directed edges.)
2. directed edge $(v_i,v_{i+1})$.
3. symmetric edges $sv_i$ for all $1\leq i\leq n-1$.
4. directed edges $(s,v_0)$ and $(v_n,s)$.

Edge Costs:
1. Symmetric edges $v_iv_{i+1}$ has cost $1$.
2. All other edges have cost 0.

Edge Capacity:
1. Symmetric edges $sv_i$ $1\leq i\leq n$ has upper bound $\epsilon$ and lower bound $0$.
2. Asymmetric edge $(v_i,v_{i+1})$ has upper and lower bound of $a_{i+1}$.
3. All other edges have upper bound $\infty$ and lower bound $0$.

**Proof**
After we solve the min-cost circulation, we get a flow $f$. Let $f(u,v)$ be the total flow from $u$ to $v$. (account parallel edges and directions). Then $x_i = f(v_{i-1},v_i)$. 

Note the cost of the flow is precisely $\sum_{i=1}^n |a_i-x_i|$.

Note that $x_i-x_{i+1} = f(v_{i-1},v_i)+f(s,v_{i-1})=f(v_i,v_{i+1})$, this shows the difference is $f(s,v_{i-1})$, which has absolute value at most $\epsilon$. This shows $x_i-x_{i+1}\leq \epsilon$.

The graph is clearly outerplanar.