# 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. :) Jul 1, 2011 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, 2011 at 15:57
• Key phrase: Chebyshev approximation. (More to follow. The idea is to introduce an extra variable then turn objective into the constraints.) Jul 1, 2011 at 17:39
• @cardinal You mean this one :mathworld.wolfram.com/ChebyshevApproximationFormula.html It seems quite complicated. Jul 1, 2011 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. Jul 1, 2011 at 18:29

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.

• How would you find some measure of precision for the parameters and/or predictions? I ask because of the following recent question: mathematica.stackexchange.com/questions/214226/….
– JimB
Feb 6, 2020 at 16:44
• I've always wondered if this really gave the L∞ norm minimum point. When I experimented with this years ago, I found that sometimes the L2 norm minimum point gave me a smaller L∞ norm compared to what I got from LP solver. It could be that my LP problem formulation was incorrect though. Oct 11, 2021 at 5:40

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

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

• Unfortunatley, the link does not work anymore. Could you update it? Mar 2, 2019 at 10:30