Qual è il Bigo di regressione lineare?

Question

Quali sono le dimensioni di un sistema è ragionevole tentare di fare una regressione lineare sui?

In particolare: Ho un sistema di pozzetti ~ 300K e ~ 1.200 termini lineari. E 'questo computazionalmente fattibile?

Answer 1

È possibile esprimere questa come un'equazione matriciale:

dove la matrice è 300K righe e 1200 colonne, il vettore dei coefficienti è 1200x1, e il vettore RHS è 1200x1.

Se si moltiplica entrambi i lati per la trasposta della matrice , si dispone di un sistema di equazioni per le incognite che è in 1200x1200. È possibile utilizzare decomposizione LU o qualsiasi altro algoritmo che ti piace di risolvere per i coefficienti. (Questo è ciò che i minimi quadrati sta facendo.)

Quindi, il comportamento Big-O è qualcosa di simile a O (m m n), dove m = 300K e n = 1200. Si potrebbe considerazione per la trasposizione, la moltiplicazione di matrici, la decomposizione LU , e la sostituzione in avanti-indietro per ottenere i coefficienti.

Answer 2

La regressione lineare viene calcolato come (X'X) ^ -. 1 x'y

Se X è una matrice (n x k):

1. (X' X) richiederà O (n * k ^ 2) tempo e produce un (k x k) Matrice

2. L'inversione di matrice a (k x k) matrice richiede O (k ^ 3) Tempo

3. (X' Y) richiederà O (n * k ^ 2) tempo e produce un (k x k) Matrice

4. La moltiplicazione matrice finale di due (k x k) matrici richiederà O (k ^ 3) Tempo

Così il Big-O tempo di esecuzione è O (k ^ 2 * (n + k)).

Si veda anche: http://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations#Matrix_algebra

Se si ottiene fantasia sembra che è possibile ottenere il tempo fino a O (k ^ 2 * (n + k ^ 0,376)) con l'algoritmo Coppersmith-Winograd.

Answer 3

La regressione lineare del modello forma chiusa viene calcolata come segue: derivato di

  

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

Quindi, risolviamo per

  

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

Quindi, il valore W è

  

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

dove: W : è il vettore dei pesi attesi H : è la matrice caratteristiche N * D dove N è il numero di osservazioni, e D è il numero di funzioni y : è il valore effettivo

Quindi, la complessità della

  

H ^ t H è n D ^ 2

La complessità della trasposizione è D ^ 3

Quindi, la complessità della

  

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