Computational Complexity – Least Square Regression Operation Analysis

algorithmscomputational complexityregression

In a least square regression algorithm, I have to do the following operations to compute regression coefficients:

  • Matrix multiplication, complexity: $O(C^2N)$
  • Matrix inversion, complexity: $O(C^3)$
  • Matrix multiplication, complexity: $O(C^2N)$
  • Matrix multiplication, complexity: $O(CN)$

where, N are the training examples and C is total number of features/variables.

How can I determine the overall computational complexity of this algorithm?

EDIT:
I studied least square regression from the book Introduction to Data Mining by Pang Ning Tan. The explanation about linear least square regression is available in the appendix, where a solution by the use of normal equation is provided (something of the form $a=(X^TX)^{-1}X^Ty)$, which involves 3 matrix multiplications and 1 matrix inversion).

My goal is to determine the overall computational complexity of the algorithm.
Above, I have listed the 4 operations needed to compute the regression coefficients with their own complexity. Based on this information, can we determine the overall complexity of the algorithm?

Thanks!

Best Answer

For a least squares regression with $N$ training examples and $C$ features, it takes:

  • $O(C^2N)$ to multiply $X^T$ by $X$
  • $O(CN)$ to multiply $X^T$ by $Y$
  • $O(C^3)$ to compute the LU (or Cholesky) factorization of $X^TX$ and use that to compute the product $(X^TX)^{-1} (X^TY)$

Asymptotically, $O(C^2N)$ dominates $O(CN)$ so we can forget the $O(CN)$ part.

Since you're using the normal equation I will assume that $N>C$ - otherwise the matrix $X^T X$ would be singular (and hence non-invertible), which means that $O(C^2N)$ asymptotically dominates $O(C^3)$.

Therefore the total time complexity is $O(C^2N)$. You should note that this is only the asymptotic complexity - in particular, for $C$, $N$ smallish you may find that computing the LU or Cholesky decomposition of $X^T X$ takes significantly longer than multiplying $X^T$ by $X$.

Edit: Note that if you have two datasets with the same features, labeled 1 and 2, and you have already computed $X_1^T X_1$, $X_1^TY_1$ and $X_2^TX_2$, $X_2^TY_2$ then training the combined dataset is only $O(C^3)$ since you just add the relevant matrices and vectors, and then solve a $C\times C$ linear system.

In particular this allows you do to very fast bootstrap, jackknife and cross-validation when you are training an OLS regression (or variants like ridge regression, lasso, constrained OLS etc).

Related Question