Paquete de software para resolver la regresión lineal de la norma L-infinito

¿Existe algún paquete de software para resolver la regresión lineal con el objetivo de minimizar la norma L-infinito?

Respuesta corta : su problema puede formularse como un programa lineal (LP), lo que le permite elegir su solucionador de LP favorito para la tarea. Para ver cómo escribir el problema como un LP, sigue leyendo.

Este problema de minimización a menudo se denomina aproximación de Chebyshev .

Deje , con la fila denotada por y . Luego buscamos minimizar la función con respecto a . Denote el valor óptimo con $\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}$$i$$\x_i$$\b \in \reals^p$$f(\b) = \|\y - \X \b\|_\infty$$\b$

$$f^\star = f(\b^\star) = \inf \{f(\b): \b \in \reals^p \} \>.$$

La clave para refundir esto como un LP es reescribir el problema en forma de epígrafe . No es difícil convencerse de que, de hecho,

$$f^\star = \inf\{t: f(\b) \leq t, \;t \in \reals, \;\b \in \reals^p \} \> .$$

Ahora, usando la definición de la función , podemos reescribir el lado derecho de arriba como y así vemos que minimizar la en una configuración de regresión es equivalente a LP donde se realiza la optimización over y denota un vector de unos de longitud . Lo dejo como un ejercicio (fácil) para que el lector reformule el LP anterior en forma estándar.$f$

$$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 \} \>,$$ $\ell_\infty$ $$\begin{array}{ll} \text{minimize} & t \\ \text{subject to} & \y-\X \b \leq t\ones \\ & \y - \X \b \geq - t \ones \>, \\ \end{array}$$ $(\b, t)$$\ones$$n$

Relación con la (variación total) de regresión lineal$\ell_1$

Es interesante observar que se puede hacer algo muy similar con la norma . Deje . Luego, argumentos similares conducen a la conclusión de que modo que el LP correspondiente sea $\ell_1$$g(\b) = \|\y - \X \b \|_1$

$$\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 \} \>,$$ $$\begin{array}{ll} \text{minimize} & \t^T \ones \\ \text{subject to} & \y-\X \b \leq \t \\ & \y - \X \b \geq - \t \>. \\ \end{array}$$

Observe aquí que ahora es un vector de longitud lugar de un escalar, como lo fue en el caso .$\t$$n$$\ell_\infty$

La similitud en estos dos problemas y el hecho de que ambos pueden ser lanzados como LP no es, por supuesto, un accidente. Las dos normas están relacionadas en el sentido de que son las normas duales entre sí.

Malab puede hacerlo, usando cvx. para obtener cvx (gratis):

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

En cvx, lo escribirías de esta manera:

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

(ver ejemplo página 12 del manual )

Hay una implementación Python de CVX ( aquí ) pero los comandos son ligeramente diferentes ...

La respuesta de @ cardinal está bien establecida y ha sido aceptada, pero, en aras de cerrar este hilo completamente, ofreceré lo siguiente: Las bibliotecas numéricas de IMSL contienen una rutina para realizar la regresión de la norma L-infinito. La rutina está disponible en Fortran, C, Java, C # y Python. He usado las versiones C y Python para las cuales el método se llama lnorm_regression, que también admite la regresión general -norm, .$L_p$$p >= 1$

Tenga en cuenta que estas son bibliotecas comerciales, pero las versiones de Python son gratuitas (como en cerveza) para uso no comercial.