2
$\begingroup$

I would to find the parameters for $y_i=\beta_0+\beta_1x_{1i}+\beta_2x_{2i}$ using the least squares concept and want to prove that matrix notation is computationally more convenient than my way below :

I want to minimize : $LS(\beta)=\sum(y_i-(\beta_0+\beta_1x_{1i}+\beta_2x_{2i}))^2$

1.derivate $LS(\beta)$ w.r. to $\beta_0$ and set it to $0$

$\beta_0=\bar{y}-\beta_1\bar{x_1}-\beta_2\bar{x_2}$ (use $\beta_0$ for equations below)

2.derivate $LS(\beta)$ w.r. to $\beta_1$ and set it to $0$

$\beta_1=\frac{\sum(y_i-\bar{y_i})(\bar{x_1}-x_{1i})\space+\space\beta_2\sum(\bar{x_2}-x_{2i})(\bar{x_1}-x_{1i})}{\sum(\bar{x_1}-x_{1i})^2}$

3.derivate $LS(\beta)$ w.r. to $\beta_2$ and set it to $0$

$\beta_2=\frac{\sum(y_i-\bar{y_i})(\bar{x_2}-x_{2i})\space+\space\beta_1\sum(\bar{x_1}-x_{1i})(\bar{x_2}-x_{2i})}{\sum(\bar{x_2}-x_{2i})^2}$

I could solve for $\beta_1$ or $\beta_2$ (by plugging in) but I get a very messy expression.

Q) We also know that a matrix solution would be $(X'X)^{-1} X'Y$ which yields $O(n)=O(k^2*(n + k))$ where X = $n$ by $k$ matrix.

Why not solve for all possible $\beta$ in this scalar fashion ? (as I've written above we can solve them independent of each other!). The above complexity would be $O(n)=n^2$ so why would I choose a matrix notation ? or where am I being unreasonable ?

$\endgroup$
  • 4
    $\begingroup$ Because actually we never compute the inverse. Check the threads on Least Squares Regression Step-By-Step Linear Algebra Computation and on Understanding QR Decomposition. $\endgroup$ – usεr11852 Oct 22 '17 at 19:39
  • $\begingroup$ @usεr11852 so I guess the reason why we shouldn't solve all β in a "scalar" fashion is because we don't compute the inverse ? $\endgroup$ – Oleg Oct 22 '17 at 19:56
  • 1
    $\begingroup$ I am not sure why you are distinguishing between "matrix" and "scalar". Matrix "notation" has nothing to do with how algorithms are implemented, it has to do with how we write mathematical expressions in papers etc. and when doing proofs. We will choose the same efficient algorithms for solving mathematical expressions regardless of whether those expressions are written using matrix notation or some other way, because "efficient algorithm" is its own thing, related to computer hardware architecture, not a consequence of mathematical notation. $\endgroup$ – jbowman Oct 22 '17 at 20:03
  • $\begingroup$ @usεr11852 Now that I look it up very quickly, QR decomp. seems to be $O(n^3)$ for square matrix of size $n$, and since computing inverse (and multiplication) is $O(n^{2.37})$ it seems that naive computation of $(X^TX)^{-1}X^TY$ is fast $\endgroup$ – Łukasz Grad Oct 22 '17 at 20:08
  • 1
    $\begingroup$ matrix algebra notation is convenient for textbooks, it is not necessarily efficient for real computations. In particular, linear regression is faster to compute via solving of linear equations system and, in some instances, via sweep operations. $\endgroup$ – ttnphns Oct 22 '17 at 21:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.