Regression involves many linear algebra tricks. We already discussed the case of influence measure which can be computed most of the time in one pass, even in the case of ML.^{1} Beside model diagnostics, several other algebraic properties are in use when dealing with the normal equations. Recall that parameters of a linear regression model can be found using iterative solution (e.g., gradient descent) or the following algebraic equation: $\hat\theta =(X^TX)^{-1}X^Ty$, where $\theta$ is the parameter of interest (a vector of regression coefficients), $X$ the design matrix and $y$ the response variable. This requires inverting a matrix but there are ways to alleviate its cost as we’ve seen in a previous post on matrix decomposition.
Under the OLS framework, two elimination methods gained popularity long ago. Since we are dealing with a system of linear equations, Doolittle method, which is based on Gaussian elimination, is one option, the other being the Gauss-Jordan (full) elimination. The latter leads to the sweep operator.^{2} Rick Wicklin wrote two nice blog posts on this topic. Basically, the sweep operator allows to “sweep in” or “sweep out” rows of the $X^TX$ matrix, and you can even “sweep in” columns in any order, which amounts to add effects to a model.
The algorithm is discussed in one of Richard B. Darlington’s note. Julia code is available on these blog posts, while R code is provided in The Statistician’s Apprentice: An Introduction to the SWP Operator. Finally, it is worth noting that:^{3}
The SWEEP operator can be programmed to produce generalized inverses and create, as by-products, such items as the Forward Doolittle matrix, the Cholesky decomposition matrix, the Hermite canonical form matrix, the determinant of the original matrix, Type I sums of squares, the error sum of squares, a solution to the normal equations, and the general form of estimable functions.
♪ Poppy • Flux
W.J. Shih and S. Weisberg. Assessing Influence in Multiple Linear Regression With Incomplete Data. Technometrics, 28(3): 231-239, 1986. ↩︎
John F. Monahan. Numerical Methods in Statistics. Cambridge University Press (2011). ↩︎
James H. Goodnight. A Tutorial on the SWEEP Operator. A Tutorial on the SWEEP Operator. The American Statistician, 33(3): 149-158, 1979. ↩︎