Software package to solve L-infinity norm linear regression

Question

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

Answer 1

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 $$ f^\star = f(\b^\star) = \inf \{f(\b): \b \in \reals^p \} \>. $$

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, $$ f^\star = \inf\{t: f(\b) \leq t, \;t \in \reals, \;\b \in \reals^p \} \> . $$

Now, using the definition of the function $f$, we can rewrite the right-hand side above as $$ f^\star = \inf\{t: -t \leq y_i - \x_i \b \leq t, \;t \in \reals, \;\b \in \reals^p,\; 1 \leq i \leq n \} \>, $$ and so we see that minimizing the $\ell_\infty$ norm in a regression setting is equivalent to the LP $$ \begin{array}{ll} \text{minimize} & t \\ \text{subject to} & \y-\X \b \leq t\ones \\ & \y - \X \b \geq - t \ones \>, \\ \end{array} $$ 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 $$\newcommand{\t}{\mathbf{t}} g^\star = \inf\{\t^T \ones : -t_i \leq y_i - \x_i \b \leq t_i, \;\t = (t_i) \in \reals^n, \;\b \in \reals^p,\; 1 \leq i \leq n \} \>, $$ so that the corresponding LP is $$ \begin{array}{ll} \text{minimize} & \t^T \ones \\ \text{subject to} & \y-\X \b \leq \t \\ & \y - \X \b \geq - \t \>. \\ \end{array} $$

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.

Answer 2

@cardinal's answer is well-stated and has been accepted, but, for the sake of closing this thread completely I'll offer the following: The IMSL Numerical Libraries contain a routine for performing L-infinity norm regression. The routine is available in Fortran, C, Java, C# and Python. I have used the C and Python versions for which the method is call lnorm_regression, which also supports general $L_p$-norm regression, $p >= 1$.

Note that these are commercial libraries but the Python versions are free (as in beer) for non-commercial use.

Answer 3

Malab can do it, using cvx. to get cvx (free):

http://cvxr.com/cvx/download/

In cvx, you would write it this way:

cvx_begin
   variable x(n);
   minimize( norm(A*x-b,Inf) );
cvx_end

(check example page 12 of the manual)

There is a Python implementation of CVX (here) but the commands are slightly different...