什么是线性回归的BigO？

Question

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

具体来说:我有一个约300K采样点和~1200个线性项的系统.这在计算上是否可行？

Answer 1

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

如果X是(nxk)矩阵:

1. (X'X)取O(n*k ^ 2)时间并产生(k×k)矩阵

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

3. (X'Y)取O(n*k ^ 2)时间并产生(kxk)矩阵

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

您可以将其表示为矩阵方程:

矩阵在哪里 是300K行和1200列,系数向量 是1200x1,和RHS矢量 是1200x1.

如果将两边乘以矩阵的转置 ,你有一个1200x1200未知数的方程组.您可以使用LU分解或您想要为系数求解的任何其他算法.(这是最小二乘法正在做的事情.)

因此,Big-O行为类似于O(m m n),其中m = 300K且n = 1200.您将考虑转置,矩阵乘法,LU分解和前后替换以获得系数.