Quelle est la Bigo de régression linéaire?

Question

Quelle un système est-il raisonnable d'essayer de faire une régression linéaire sur?

Plus précisément: J'ai un système avec des points d'échantillonnage ~ 300K et ~ 1200 termes linéaires. Est-ce possible informatiquement?

Answer 1

Vous pouvez exprimer cela comme une équation matricielle:

où la matrice est 300K lignes et 1200 colonnes, le vecteur de coefficient est 1200x1, et le second membre est 1200x1.

Si vous multipliez les deux côtés par la transposée de la matrice , vous avez un système d'équations pour les inconnues qui est 1200x1200. Vous pouvez utiliser la décomposition LU ou tout autre algorithme vous voulez résoudre pour les coefficients. (C'est ce que les moindres carrés est en train de faire.)

Ainsi, le comportement Big-O est quelque chose comme O (m m n), où m = 300K et n = 1200. Vous souhaitez compte pour la transposition, la multiplication de la matrice, la décomposition LU et le remplacement de l'avant-retour pour obtenir les coefficients.

Answer 2

La régression linéaire est calculée comme (X'X) ^ -. 1 X'Y

Si X est une matrice (n x k):

1. (X » X) tire O (n * k ^ 2) le temps et produit une matrice (k x k)

2. La matrice prend O (k ^ 3) l'inversion de la matrice d'un (k x k) Temps

3. (X » Y) a O (n * k ^ 2) le temps et produit une (k x k) matrice

4. La multiplication de la matrice finale de deux matrices (k x k) prend O (k ^ 3) Temps

Alors le temps d'exécution Big-O est O (k ^ 2 * (n + k)).

Voir aussi: http://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations#Matrix_algebra

Si vous avez envie, il semble que vous pouvez obtenir le temps d'arrêt à O (k ^ 2 * (n + k ^ 0,376)) avec l'algorithme Chaudronnier-Winograd.

Answer 3

La régression linéaire du modèle de forme fermée est calculée comme suit: Dérivé de

  

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

Alors, nous résolvons pour

  

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

Ensuite, la valeur de W est

  

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

où: W : est le vecteur des poids attendus H : est la matrice des fonctionnalités N * D où N est le nombre d'observations, et D représente le nombre de fonctionnalités y : est la valeur réelle

Ensuite, la complexité

  

H ^ t H est n D ^ 2

La complexité de la transposition est D ^ 3

Ainsi, la complexité

  

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