I am reading Elements of Statistical Learning and read the following claim from the text (page 93, Chapter 3.7):

Least squares fitting is usually done via the Cholesky decomposition of the matrix $\mathbf{X}^T\mathbf{X}$ or a QR Decomposition of $\mathbf{X}$. With $N$ obserations and $p$ features, the Cholesky decomposition requires $p^3 + Np^2/2$ operations, while the QR decomposition requires $Np^2$ operations.

I understand Cholesky and QR decompositions individually, but I do not understand where this claim came from. Please help.

  • 1
    $\begingroup$ It just states the running time (or rather its order of magnitude) of the common algorithms for computing these decompositions. In fact, using fast matrix multiplication you can do better – theoretically. These algorithms are hardly used in practice. $\endgroup$ – Yuval Filmus May 17 '15 at 20:32

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.