# Software package to solve L-infinity norm linear regression

Is there any software package to solve the linear regression with the objective of minimizing the L-infinity norm.

Short answer: Your problem can be formulated as a linear program (LP), leaving you to choose your favorite LP solver for the task. To see how to write the problem as an LP, read on.

This minimization problem is often referred to as Chebyshev approximation.

Let $\newcommand{\y}{\mathbf{y}}\newcommand{\X}{\mathbf{X}}\newcommand{\x}{\mathbf{x}}\newcommand{\b}{\mathbf{\beta}}\newcommand{\reals}{\mathbb{R}}\newcommand{\ones}{\mathbf{1}_n} \y = (y_i) \in \reals^n$, $\X \in \reals^{n \times p}$ with row $i$ denoted by $\x_i$ and $\b \in \reals^p$. Then we seek to minimize the function $f(\b) = \|\y - \X \b\|_\infty$ with respect to $\b$. Denote the optimal value by

The key to recasting this as an LP is to rewrite the problem in epigraph form. It is not difficult to convince oneself that, in fact,

Now, using the definition of the function $f$, we can rewrite the right-hand side above as

and so we see that minimizing the $\ell_\infty$ norm in a regression setting is equivalent to the LP

where the optimization is done over $(\b, t)$, and $\ones$ denotes a vector of ones of length $n$. I leave it as an (easy) exercise for the reader to recast the above LP in standard form.

Relationship to the $\ell_1$ (total variation) version of linear regression

It is interesting to note that something very similar can be done with the $\ell_1$ norm. Let $g(\b) = \|\y - \X \b \|_1$. Then, similar arguments lead one to conclude that

so that the corresponding LP is

Note here that $\t$ is now a vector of length $n$ instead of a scalar, as it was in the $\ell_\infty$ case.

The similarity in these two problems and the fact that they can both be cast as LPs is, of course, no accident. The two norms are related in that that they are the dual norms of each other.