Qual é a grande regressão linear?

Question

Qual é o tamanho do sistema, é razoável tentar fazer uma regressão linear?

Especificamente: eu tenho um sistema com ~ 300 mil pontos de amostra e ~ 1200 termos lineares. Isso é computacionalmente viável?

Answer 1

Você pode expressar isso como uma equação da matriz:

onde a matriz são 300k linhas e 1200 colunas, o vetor de coeficiente é 1200x1 e o vetor RHS é 1200x1.

Se você multiplicar os dois lados pela transposição da matriz , você tem um sistema de equações para as incógnitas que são 1200x1200. Você pode usar a Decomposição da LU ou qualquer outro algoritmo que deseja resolver para os coeficientes. (É isso que os mínimos quadrados estão fazendo.)

Então, o comportamento Big-O é algo como O (Mmn), onde m = 300k e n = 1200. Você explicaria a transposição, a multiplicação da matriz, a decomposição da LU e a substituição de adiante para obter os coeficientes.

Answer 2

A regressão linear é calculada como (x'x)^-1 x'y.

Se x é uma matriz (nxk):

1. (X 'x) leva o tempo o (n*k^2) e produz uma matriz (kxk)

2. A inversão da matriz de uma matriz (kxk) leva o tempo (k^3)

3. (X 'y) leva o tempo o (n*k^2) e produz uma matriz (kxk)

4. A multiplicação final da matriz de duas matrizes (KXK) leva o tempo (k^3)

Portanto, o tempo de corrida Big-O é O (K^2*(n + k)).

Veja também: http://en.wikipedia.org/wiki/computational_complexity_of_mathematical_operations#matrix_algebra

Se você se sentir sofisticado, parece que você pode ter um tempo para O (k^2*(n+k^0,376)) com o algoritmo Coppersmith -Winograd.

Answer 3

A regressão linear do modelo de forma fechada é calculada da seguinte forma: derivado de

Rss (w) = -2h^t (y -hw)

Então, resolvemos para

-2h^t (y-hw) = 0

Então, o valor W é

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

Onde:C: é o vetor dos pesos esperadosH: é a matriz de recursos n*d onde n é o número de observações e d é o número de recursosy: é o valor real

Então, a complexidade de

H^t h é n d^2

A complexidade da transposição é d^3

Então, a complexidade de

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