Hay cualquier paquete de software para resolver la regresión lineal con el objetivo de minimizar la norma L-infinito.
Respuestas
¿Demasiados anuncios?
Respuesta corta: el problema puede ser formulado como un problema de programación lineal (LP), dejando para elegir a su favorito LP solver para la tarea. A ver cómo escribir el problema como un LP, leer.
Este problema de minimización, se refiere a menudo como la aproximación de Chebyshev.
Vamos $\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}$ con la fila $i$ denotado por $\x_i$$\b \in \reals^p$. A continuación, tratamos de minimizar la función de $f(\b) = \|\y - \X \b\|_\infty$ con respecto al $\b$. Indicar el valor óptimo por $$ f^\estrella = f(\b^\star) = \inf \{f (a\b): \b \in \reales^p \} \>. $$
La clave para la refundición esto como un LP es volver a escribir el problema en el epígrafe forma. No es difícil convencer a sí mismo que, de hecho, $$ f^\estrella = \inf\{t: f (a\b) \leq t, \;t \en \reales, \;\b \in \reales^p \} \> . $$
Ahora, usando la definición de la función $f$, podemos reescribir el lado derecho de arriba como $$ f^\estrella = \inf\{t: -t \leq y_i - \x_i \b \leq t, \;t \en \reales, \;\b \in \reales^p,\; 1 \leq i \leq n \} \>, $$ y así vemos que la minimización de la $\ell_\infty$ norma en una regresión de configuración es equivalente a la LP $$ \begin{array}{ll} \text{minimize} & t \\ \text{subject to} & \y-\X \b \leq t\ones \\ & \y - \X \b \geq - t \ones \>, \\ \end{array} $$ donde la optimización se lleva a cabo en $(\b, t)$, e $\ones$ denota un vector de unos de longitud $n$. Dejo como un (fácil) ejercicio para el lector de proceder a la refundición de la anterior LP en forma estándar.
Relación a la $\ell_1$ (la variación total), la versión de regresión lineal
Es interesante notar que algo muy similar se puede hacer con el $\ell_1$ norma. Deje $g(\b) = \|\y - \X \b \|_1$. Luego, argumentos similares llevan a la conclusión de que $$\newcommand{\t}{\mathbf{t}} g^\estrella = \inf\{\t^T \:- t_i \leq y_i - \x_i \b \leq t_i, \;\t = (t_i) \in \reales^n, \;\b \in \reales^p,\; 1 \leq i \leq n \} \>, $$ de modo que la correspondiente LP es $$ \begin{array}{ll} \text{minimize} & \t^T \ones \\ \text{subject to} & \y-\X \b \leq \t \\ & \y - \X \b \geq - \t \>. \\ \end{array} $$
Tenga en cuenta que $\t$ es ahora un vector de longitud $n$ en lugar de un escalar, como lo fue en el $\ell_\infty$ de los casos.
La similitud de estos dos problemas y el hecho de que ambos pueden ser emitidos como LPs es, por supuesto, no hubo ningún accidente. Las dos normas están relacionadas en la que ellos son el doble de las normas de cada uno de los otros.
Patrick
Puntos
183
Malab, puede hacer uso de cvx. para obtener el cvx (gratis):
En cvx, usted debería escribir de esta manera:
cvx_begin
variable x(n);
minimize( norm(A*x-b,Inf) );
cvx_end
(ver ejemplo en la página 12 del manual)
Existe una implementación de Python de CVX (aquí) pero los comandos son ligeramente diferentes...
christy
Puntos
51
@cardenal de la respuesta es bien establecido y ha sido aceptado, pero, por el bien de cerrar este hilo por completo voy a ofrecer las siguientes: La Numérica IMSL Bibliotecas contienen una rutina para la realización de L-infinito norma de regresión. La rutina está disponible en Fortran, C, Java, C# y Python. He utilizado el C y versiones de Python para que el método es llamada lnorm_regression, que también apoya el general $L_p$-norma de regresión, $p >= 1$.
Tenga en cuenta que estas son las librerías comerciales, pero las versiones de Python son gratis (como en la cerveza) para uso no comercial.
