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.

-
Well, any linear-programming package would work. That leaves you with a lot of options. :) –  cardinal Jul 1 '11 at 15:25
@Cardinal How would you recast this as a linear program? It's not evident how to do it even in trivial cases (such as two data points and one parameter): there are no constraints and the objective function is nonlinear. –  whuber Jul 1 '11 at 15:57
Key phrase: Chebyshev approximation. (More to follow. The idea is to introduce an extra variable then turn objective into the constraints.) –  cardinal Jul 1 '11 at 17:39
@cardinal You mean this one :mathworld.wolfram.com/ChebyshevApproximationFormula.html It seems quite complicated. –  Fan Zhang Jul 1 '11 at 18:18
Well, it's a bit related, but not germane to this problem. Your problem can be solved with a simple LP. As soon as I can get to a computer, I'll post an answer. –  cardinal Jul 1 '11 at 18:29
show 1 more comment

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.

-
+1 Nice exposition. Thanks. –  whuber Jul 2 '11 at 18:10
+1 Great Solution @cardinal. –  suncoolsu Jul 5 '11 at 4:39

@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.

-

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

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...

-
Thank you very much. –  Fan Zhang Oct 19 '11 at 13:11