Complejidad computacional de la operación de regresión por mínimos cuadrados

Question

En un algoritmo de regresión por mínimos cuadrados, tengo que hacer las siguientes operaciones para calcular los coeficientes de regresión:

• Multiplicación de matrices, complejidad: $O(C^2N)$
• Inversión de la matriz, complejidad: $O(C^3)$
• Multiplicación de matrices, complejidad: $O(C^2N)$
• Multiplicación de matrices, complejidad: $O(CN)$

¿Cómo puedo determinar la complejidad computacional global de este algoritmo?

EDITAR: He estudiado la regresión por mínimos cuadrados del libro Introducción a la minería de datos por Pang Ning Tan. La explicación sobre la regresión lineal por mínimos cuadrados está disponible en el apéndice, donde se proporciona una solución mediante el uso de la ecuación normal (algo de la forma $a=(X^TX)^{-1}X^Ty)$ que implica 3 multiplicaciones de matrices y 1 inversión de matrices).

Mi objetivo es determinar la complejidad computacional global del algoritmo. Más arriba, he enumerado las 4 operaciones necesarias para calcular los coeficientes de regresión con su propia complejidad. Basándonos en esta información, ¿podemos determinar la complejidad global del algoritmo?

Gracias.

Answer 1

Para una regresión por mínimos cuadrados con $N$ ejemplos de formación y $C$ características, se necesita:

• $O(C^2N)$ para multiplicar $X^T$ por $X$
• $O(CN)$ para multiplicar $X^T$ por $Y$
• $O(C^3)$ para calcular la factorización LU (o Cholesky) de $X^TX$ y utilizarlo para calcular el producto $(X^TX)^{-1} (X^TY)$

Asintóticamente, $O(C^2N)$ domina $O(CN)$ para que podamos olvidar el $O(CN)$ parte.

Como estás usando la ecuación normal, asumiré que $N>C$ - en caso contrario, la matriz $X^T X$ sería singular (y por tanto no invertible), lo que significa que $O(C^2N)$ domina asintóticamente $O(C^3)$ .

Por lo tanto, la complejidad temporal total es $O(C^2N)$ . Hay que tener en cuenta que esto es sólo la complejidad asintótica - en particular, para $C$ , $N$ pequeño, es posible que el cálculo de la descomposición LU o Cholesky de $X^T X$ tarda bastante más que la multiplicación de $X^T$ por $X$ .

Editar: Tenga en cuenta que si tiene dos conjuntos de datos con las mismas características, etiquetados como 1 y 2, y ya ha calculado $X_1^T X_1$ , $X_1^TY_1$ y $X_2^TX_2$ , $X_2^TY_2$ luego entrenar el combinado El conjunto de datos es sólo $O(C^3)$ ya que sólo hay que sumar las matrices y vectores correspondientes, y luego resolver un $C\times C$ sistema lineal.

En particular, esto le permite hacer un bootstrap muy rápido, jackknife y validación cruzada cuando está entrenando una regresión OLS (o variantes como la regresión ridge, lasso, OLS restringida, etc).

Answer 2

Estaba confundido en cuanto a por qué la multiplicación de la matriz se afirma que es $\mathcal{O}(C^2 N)$ aquí, que es $\mathcal{O}(N^3)$ cuando $N=C$ que es mucho más lento que el de Strassen $\mathcal{O}(N^{2.8})$ y la de Le Gall $\mathcal{O}(N^{2.37})$ .

Resulta que estamos haciendo una multiplicación matricial rectangular donde $N \ggg C$ . Hay muchos más datos que variables.

Hay algoritmos con un escalamiento mucho mejor que el ingenuo $\mathcal{O}(C^2N)$ costo para la parte dominante en la respuesta de Chris Taylor.

Puedes multiplicar $X^TX$ con complejidad $\mathcal{O}(C^{1.8}N)$ si se utiliza la de Strassen $\mathcal{O}(C^{2.8})$ coste de $C \times C$ matrices, y en teoría también se puede hacer con $\mathcal{O}(C^{1.37}N)$ si se utiliza el complejidad más conocida para la multiplicación de $C \times C$ matrices (pero hay que tener en cuenta que a menudo se prefiere el algoritmo de Strassen debido a la gran constante de este último).

Lo he obtenido de la primera ecuación de la página 262 de este documento por medio de la configuración:

• $m=p=C$
• $n=N$
• $N > C$
• $\omega = 2.8$ para Strassen, y $2.37$ para el algoritmo con mejor coste asintótico teórico (pero no práctico).

Answer 3

En este trabajo https://www.research-collection.ethz.ch/bitstream/handle/20.500.11850/153646/eth-6011-01.pdf?sequence=1&isAllowed=y En las páginas 32 y 33 se discuten las dos posibilidades de implementación (la alternativa de eliminación gaussiana frente al uso de la descomposición QR) si está interesado en el coste real en términos de DFLOP.