How large a system is it reasonable to attempt to do a linear regression on?
Specifically: I have a system with ~300K sample points and ~1200 linear terms. Is this computationally feasible?
+2
A:
You can express this as a matrix equation:
where the matrix 
is 300K rows and 1200 columns, the coefficient vector 
is 1200x1, and the RHS vector 
is 1200x1.
If you multiply both sides by the transpose of the matrix 
, you have a system of equations for the unknowns that's 1200x1200. You can use LU decomposition or any other algorithm you like to solve for the coefficients. (This is what least squares is doing.)
So the Big-O behavior is something like O(m*m*n), where m = 300K and n = 1200. You'd account for the transpose, the matrix multiplication, the LU decomposition, and the forward-back substitution to get the coefficients.
duffymo
2009-12-23 20:49:16
So, if I'm reading that correctly (and IIRC), generating the A will be O(n*m)~=O(m^2) (in my case `n/m=C`) and the multiplication will be O(n*n*m)~=O(n^3) and the inversion will be O(n^3) Now just to figure out the constant term.
BCS
2009-12-23 21:05:25