In practice, what's the fastest method to find a least square solution rather than using SVD decompostion?

I'm working on a real-time implementation of Lucas-Kanade for optical flow. However, the SVD decomposition to do achieve the least square method to reduce the error seems to take too much time.

A brief explanation of the algorithm can be accessed here Lucas Kanade algorithm

• One might try using conjugate gradients in the case computing matrix factorizations like the SVD for one's problem is too computationally involving. This being said the computational complexity for each of these methods is in general $O(N^3)$. Oct 29, 2018 at 11:55
• I would recommend to try qr-factorization e.g. by using Gram-Schmidt orthogonalization. Oct 29, 2018 at 21:29
• @user35593 Why GS instead of Householder? Nov 28, 2018 at 23:52

In practice, the fastest direct method is normal equations $$A^TAx=A^Tb$$ + exploiting symmetry to compute $$A^TA$$ + Cholesky to solve the resulting linear system. It scales like $$mn^2 + o(mn^2)$$ for an $$m\times n$$ matrix $$A$$ with $$m\gg n$$, when most other algorithms cost $$2mn^2$$, and it is faster even in the case $$m\approx n$$. However, it may be dramatically unstable, especially if the value of that minimum norm is small.