¿Cuál es el BigO de regresión lineal?

Question

Cómo es de grande un sistema es razonable tratar de hacer una regresión lineal en?

Específicamente:Tengo un sistema con ~300K de puntos de muestra y ~1200 términos lineales.Es este computacionalmente factible?

Answer 1

Se puede expresar esto como una ecuación de matriz:

donde la matriz es de 300K filas y 1200 columnas, el coeficiente de vector es 1200x1, y el vector HR es 1200x1.

Si se multiplican ambos lados por la transpuesta de la matriz , tiene un sistema de ecuaciones para las incógnitas que de 1200 x 1200.Puede utilizar la descomposición LU o cualquier otro algoritmo que les gusta resolver para los coeficientes.(Esto es lo que menos plazas que está haciendo.)

Así que el Big-O comportamiento es algo así como O(mmn), donde m = 300 K y n = 1200.Usted tendría en cuenta para la transposición, la multiplicación de la matriz, de la descomposición LU, y la sustitución hacia atrás para obtener los coeficientes.

Answer 2

La regresión lineal se calcula como (X'X) ^ -. 1 X'Y

Si X es una matriz (n x k):

1. (X X') realiza (* 2 n k ^) Tiempo de O y produce un (k x k) matriz

2. La inversión de la matriz de un (k x k) matriz toma O (k ^ 3) tiempo

3. (X' Y) toma (* 2 n k ^) Tiempo de O y produce un (k x k) matriz

4. La multiplicación matriz final de dos matrices (k x k) toma O (k ^ 3) tiempo

Así que el Big-O tiempo de ejecución es O (k ^ 2 * (n + k)).

Vea también: http://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations#Matrix_algebra

Si conseguir la suposición parece que se puede obtener el tiempo de inactividad a O (k ^ 2 * (n + k ^ 0.376)) con el algoritmo Calderero-Winograd.

Answer 3

La regresión lineal de forma cerrada modelo se calcula como sigue: derivado de

  

RSS (W) = -2H ^ t (y-HW)

Por lo tanto, se resuelve para

  

-2H ^ t (y-HW) = 0

A continuación, el valor W es

  

W = (H ^ t H) ^ - 1 H ^ 2 y

donde: W : es el vector de pesos esperados H : es la características matriz de N * D donde N es el número de observaciones, y D es el número de características y : es el valor real

A continuación, la complejidad de

  

H ^ t H es n D ^ 2

La complejidad de la transpuesta es D ^ 3

Por lo tanto, la complejidad de

  

(H^t H)^-1 is n * D^2 + D^3