Polynomial interpolation to LP How I can convert next program to LP (linear programming) or to get some direction how to do this (references).
The problem is :

I want to find a polynomial $P$ of degree at most $d$ that $||P(x)-y||_1$ is minimal.
  Where $x, y$ vectors in $\mathbb{R}^n$ and $P$ is vector of $(p(x_1), \ldots, p(x_n))$

 A: Let $A$ be the Vandermonde Matrix of $x_1,x_2,...$ then if $z$ is the Vector of polynomial coefficients $z=(a_0,a_1,...)^t$ it is $P(x)=Az$.
For $\textrm{min }||Az-y||_2$ the solution is $z=(A^tA)^{-1}A^ty$.
The problem $\textrm{min }||Az-y||_1$ is equivalent to the LP
minimize $\sum \lambda_i$
subject to 
$+Az-I\lambda<=+y$
and
$-Az-I\lambda<=-y$
with $\lambda:=(\lambda_1,...)$
In the following change $||Az-y||$ to $||Ax-b||$
Here's some matlab code that does polynomial regression
This is the output from the code:

A: Here is the 'trick' you need. Suppose you wish to solve $\min_{x \in C} \|x\|_1$ where $C \subset \mathbb{R}^n$, then you can rewrite the problem as $\min_{\alpha \in \mathbb{R}^n,x \in C} \{ \alpha_1+\cdots \alpha_n | x_i \leq \alpha_i, -x_i \leq \alpha_i, \forall i\}$.
A: I suppose that if you want to find $P$, this means that $x$ and $y$ are known vectors. If you also know $d$, than your polynomial becomes $p(x) = \sum_{k=1}^d a_k x^k$. You can formulate your linear programming problem as :
$$\min z = \sum_{i = 1}^n p_i + n_i$$
subject to
$$ p_i - n_i + p(x_i) - y_i, \forall i=1\dots n$$
$$ 0 \le p_i, d_i < \infty$$
$$ -\infty \le a_k < \infty$$
In this formulation,you can take $p_i$ and $n_i$ as the positive and negative parts of the absolute value. If $p(x_i) - y_i>0$, then $p_i >0$ and $n_i = 0$, and conversly.
Hope this helps.
