Mínimos cuadrados reponderados iterativamente

El método de mínimos cuadrados iterativamente reponderados ( IRLS ) se utiliza para resolver ciertos problemas de optimización con funciones objetivo de la forma de una p -norma :

$${\displaystyle \mathop {\operatorname {arg\,min} } _{\boldsymbol {\beta }}\sum _{i=1}^{n}{\big |}y_{i}-f_{i}({\boldsymbol {\beta }}){\big |}^{p},}$$

mediante un método iterativo en el que cada paso implica resolver un problema de mínimos cuadrados ponderados de la forma: ^[1]

$${\displaystyle {\boldsymbol {\beta }}^{(t+1)}={\underset {\boldsymbol {\beta }}{\operatorname {arg\,min} }}\sum _{i=1}^{n}w_{i}({\boldsymbol {\beta }}^{(t)}){\big |}y_{i}-f_{i}({\boldsymbol {\beta }}){\big |}^{2}.}$$

IRLS se utiliza para encontrar las estimaciones de máxima verosimilitud de un modelo lineal generalizado y, en regresión robusta , para encontrar un estimador M , como una forma de mitigar la influencia de valores atípicos en un conjunto de datos distribuido normalmente, por ejemplo, minimizando los errores absolutos mínimos en lugar de los errores de mínimos cuadrados .

Una de las ventajas de IRLS sobre la programación lineal y la programación convexa es que se puede utilizar con los algoritmos numéricos de Gauss-Newton y Levenberg-Marquardt .

El IRLS se puede utilizar para la minimización de ℓ ₁ y la minimización suavizada de ℓ _p , p  < 1, en problemas de detección comprimida . Se ha demostrado que el algoritmo tiene una tasa de convergencia lineal para la norma ℓ ₁ y superlineal para ℓ _t con t  < 1, bajo la propiedad de isometría restringida , que generalmente es una condición suficiente para soluciones dispersas. ^{[2] [3]}

Para encontrar los parámetros β  = ( β ₁ , …, β _k ) ^T que minimizan la norma L ^p para el problema de regresión lineal ,

$${\displaystyle {\underset {\boldsymbol {\beta }}{\operatorname {arg\,min} }}{\big \|}\mathbf {y} -X{\boldsymbol {\beta }}\|_{p}={\underset {\boldsymbol {\beta }}{\operatorname {arg\,min} }}\sum _{i=1}^{n}\left|y_{i}-X_{i}{\boldsymbol {\beta }}\right|^{p},}$$

El algoritmo IRLS en el paso t  + 1 implica resolver el problema de mínimos cuadrados lineales ponderados : ^[4]

$${\displaystyle {\boldsymbol {\beta }}^{(t+1)}={\underset {\boldsymbol {\beta }}{\operatorname {arg\,min} }}\sum _{i=1}^{n}w_{i}^{(t)}\left|y_{i}-X_{i}{\boldsymbol {\beta }}\right|^{2}=(X^{\rm {T}}W^{(t)}X)^{-1}X^{\rm {T}}W^{(t)}\mathbf {y} ,}$$

donde W ^{( t )} es la matriz diagonal de pesos, generalmente con todos los elementos establecidos inicialmente en:

$${\displaystyle w_{i}^{(0)}=1}$$

y se actualiza después de cada iteración a:

$${\displaystyle w_{i}^{(t)}={\big |}y_{i}-X_{i}{\boldsymbol {\beta }}^{(t)}{\big |}^{p-2}.}$$

En el caso p  = 1, esto corresponde a la regresión de desviación mínima absoluta (en este caso, el problema se abordaría mejor mediante el uso de métodos de programación lineal , ^[5] por lo que el resultado sería exacto) y la fórmula es:

$${\displaystyle w_{i}^{(t)}={\frac {1}{{\big |}y_{i}-X_{i}{\boldsymbol {\beta }}^{(t)}{\big |}}}.}$$

Para evitar dividir por cero se debe realizar una regularización , por lo que en la práctica la fórmula es:

$${\displaystyle w_{i}^{(t)}={\frac {1}{\max \left\{\delta ,\left|y_{i}-X_{i}{\boldsymbol {\beta }}^{(t)}\right|\right\}}}.}$$

donde es un valor pequeño, como 0,0001. ^[5] Nótese que el uso de en la función de ponderación es equivalente a la función de pérdida de Huber en la estimación robusta. ^[6]${\displaystyle \delta }$${\displaystyle \delta }$

• Mínimos cuadrados generalizados factibles
• Algoritmo de Weiszfeld (para aproximar la mediana geométrica ), que puede considerarse un caso especial de IRLS

• Métodos numéricos para problemas de mínimos cuadrados por Åke Björck (Capítulo 4: Problemas de mínimos cuadrados generalizados).
• Mínimos cuadrados prácticos para gráficos por computadora. Curso SIGGRAPH 11

• Resolver sistemas lineales subdeterminados de forma iterativa