big-o - 什么是线性回归的 BigO？

Question

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

具体来说:我有一个包含 ~300K 样本点和 ~1200 个线性项的系统。这在计算上可行吗？

Answer 1

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

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

(X' X) 花费 O(n*k^2) 时间并生成 (k x k) 矩阵

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

(X' Y) 花费 O(n*k^2) 时间并生成 (k x k) 矩阵

两个 (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))。