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

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

\text{minimize} & t \\
\text{subject to} & \y-\X \b \leq t\ones \\
& \y – \X \b \geq – t \ones \>, \\

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

\text{minimize} & \t^T \ones \\
\text{subject to} & \y-\X \b \leq \t \\
& \y – \X \b \geq – \t \>. \\

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.

Source : Link , Question Author : Fan Zhang , Answer Author : cardinal

Leave a Comment