线性回归的BigO是什么？

Question

尝试对多大的系统进行线性回归才合理？

具体来说：我有一个具有约 300K 采样点和约 1200 个线性项的系统。这在计算上可行吗？

Answer 1

可以表示这是一个矩阵方程：

其中矩阵是300K行和列1200，系数矢量是1200x1以及RHS矢量是1200x1。

如果你由矩阵的转置相乘两侧，你有方程为一个系统这是为1200x1200未知数。您可以使用LU分解或你想解决的系数任何其他算法。 （这是最小二乘正在做什么。）

因此，大O行为有点像O（米米 n），其中M = 300K和n = 1200。你最好占转置，矩阵乘法时，LU分解和前向回代来获得系数。

Answer 2

线性回归计算为 (X'X)^-1 X'Y。

如果 X 是 (n x k) 矩阵：

1. (X' X) 需要 O(n*k^2) 时间并生成 (k x k) 矩阵

2. (k x k) 矩阵的矩阵求逆需要 O(k^3) 时间

3. (X' Y) 需要 O(n*k^2) 时间并生成 (k x k) 矩阵

4. 两个 (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

如果您感兴趣，看起来可以使用 Coppersmith-Winograd 算法将时间降至 O(k^2*(n+k^0.376))。

Answer 3

的闭合形式的模型的线性回归计算为如下： 的衍生物

  

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是特征的数量 的ý：是实际值

然后，复杂度

  

H ^吨H是N D ^ 2

在转置的复杂性是d ^ 3

因此，该复杂性

  

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