最小平方法的時間複雜度 (Computational Complexity of Least Square Regression)

假設我們目前有 $n$ 個 training samples，而我們會使用這些 samples 中的 $p$ 個 features 來進行 OLS (Ordinary Least Squares)。則：

• 計算 $X^T$ 乘以 $X$ 的時間複雜度為 $O(p^2 n)$
• 計算 $X^T$ 乘以 $Y$ 的時間複雜度為 $O(p n)$
• 計算 $X^TX$ 的 LU factorization 並使用其結果來計算 $(X^TX)^{-1}(X^TY)$ 的時間複雜度為 $O(p^3)$ 

我們現在可以來分析整體計算流程的時間複雜度了。$O(p^2 n)$ 與 $O(p n)$ 相較，由於$O(p^2 n)$ dominates $O(p n)$，所以可不理會 $O(p n)$。

再者，這邊討論的是 normal equation，我們因此可以假設 $n>p$ (否則 $X^T X$ 會是 singular 的，並因此不可逆，找不到 $(X^TX)^{-1}$)，這也代表 $O(p^2 n)$ dominates $O(p^3)$。

因此，整個運算過程的時間複雜度為 $O(p^2 n)$。

相較於使用 normal equation 來計算 OLS，我們也可以使用梯度下降法，由於梯度下降法僅會進行固定個迭代的矩陣相乘運算，其複雜度僅有 $O(p n)$，這也因此成為一般 samples 數量很多時所會採用的解法。

Reference:
http://math.stackexchange.com/questions/84495/computational-complexity-of-least-square-regression-operation