最小平方法的時間複雜度 (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