Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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)$

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!

share|improve this question
    
Could you expand further? You give three different measures of effort for matrix multiplication, and I'm not sure which is right. Also, there are at least three methods I know of for doing linear least squares (and a bit more for nonlinear least squares). What are you trying to do? Where did you get the algorithm you currently have? –  J. M. Nov 22 '11 at 7:46
    
@J.M. I have provided more elaboration in my question. Please let me know if you need more information. –  Andree Nov 22 '11 at 8:21
1  
Okay... forming $\mathbf M=\mathbf X^\top\mathbf X$ is a matrix multiplication. Forming $\mathbf b=\mathbf X^\top \mathbf y$ is a matrix-vector multiplication. But, please, please, please, do not use inversion+multiplication to compute $\mathbf c=\mathbf M^{-1}\mathbf b$! It is better computational practice to form the Cholesky decomposition of $\mathbf M$ and use that in the computation of $\mathbf c$. –  J. M. Nov 22 '11 at 8:28
    
Sure, thanks for the advice! However, I still need to know about how to determine the computational complexity of my current implementation. Can it be inferred from the information I provided above? –  Andree Nov 22 '11 at 8:35
    
Actually, all I want to know is this: From the 4 matrix operations I listed above (with their own complexity), which one has the highest degree of complexity? 3 of them have the same degree of complexity, so I'm not sure which one that I can assign as the algorithm's overall complexity. –  Andree Nov 22 '11 at 8:41
add comment

1 Answer

up vote 13 down vote accepted

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$.

share|improve this answer
1  
Thanks for the answer Chris! I'm really impressed about how you notice that N > C, thus O(C^2N) dominates O(C^3). –  Andree Nov 22 '11 at 8:50
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.