線性迴歸的BigO是什麼？

嘗試對其進行線性迴歸有多合理？線性迴歸的BigO是什麼？

具體來說：我有一個具有〜300K採樣點和〜1200線性項的系統。這在計算上是可行的嗎？

來源

2009-12-23 BCS

哪種算法？最小二乘？ – 2009-12-23 20:38:09

是的，最小二乘。我不知道還有其他人。 – BCS 2009-12-23 20:43:56

可以表達這種作爲矩陣方程：

alt text

其中矩陣 alt text 是300K行和列1200，係數向量是1200x1以及RHS矢量是1200x1。

如果你乘以矩陣 alt text 的轉置兩邊，你有一個未知的方程組是1200x1200。您可以使用LU分解或任何其他算法來解決係數問題。（這是最小二乘正在做什麼。）

因此，大O的行爲是類似於O（m m n），其中m = 300K和n = 1200.你會考慮轉置，矩陣乘法，LU分解以及前向替換來獲得係數。

來源

2009-12-23 20:49:16 duffymo

所以，如果我正確讀取（和IIRC），生成A將是O（n * m）〜= O（m^2）（在我的情況下'n/m = C'），並且乘法將會爲O（n * n * m）〜= O（n^3），反演結果爲O（n^3）。現在我們來計算常數項。 – BCS 2009-12-23 21:05:25

線性迴歸計算爲（X'X）^ - 1 X'Y。

如果X是（N×K個）矩陣：

（X」 X）需要O（N * K^2）的時間，併產生（KXK）矩陣
的矩陣求逆的（KXK）矩陣需要O（K^3）時間
（X」 Y）需要O（N * K^2）的時間，併產生（KXK）矩陣
最終矩陣乘法兩個（k x k）矩陣需要O（k^3）時間

所以Big-O運行時間是O（k^2 *（n + k））。

參見：http://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations#Matrix_algebra

如果你看中了它看起來像你可以得到時間降低到O（K^2 *（N + K^0.376））與銅匠，威諾格拉德算法。

來源

2010-12-03 04:17:06 Emiller

Coppersmith-Winograd算法實際上並不實用，因爲係數太大，它需要一個如此之大的矩陣才能看到漸進效率的好處，這是不現實的：https：//en.m.wikipedia.org/wiki/ Coppersmith-Winograd_algorithm – JStrahl 2017-08-02 22:19:55

的閉合形式的模型的線性迴歸計算爲如下：

RSS（W）= -2H^T（Y-HW）

所以，我們解決的衍生物對於

-2H^T（Y-HW）= 0

接着，W值是

W =（H^T 1H）^ - 1 H^2 Y

其中： W¯¯：是預期的權重的矢量 ħ：是特徵矩陣N * d其中，N是觀測值的數量，並且d是特徵 ý數：是實際值

然後，complexit

H ^噸H的Y是N d^2

的轉置的複雜性是d^3

所以，該的

(H^t H)^-1 is n * D^2 + D^3
複雜

來源

2016-03-01 18:53:26

這不就是那個實現的複雜嗎？有沒有證據表明這是最快的實施？ – BCS 2016-03-03 23:42:56

線性迴歸的BigO是什麼？

回答

相關問題