python - 解决线性最小二乘法的最快方法

在 https://math.stackexchange.com/a/2233298/340174 中提到，如果通过 LU 分解来求解线性方程“M·x = b”(矩阵 M 是平方)会很慢(但使用 QR 分解会更慢)。现在我注意到 numpy.linalg.solve 实际上是在使用 LU 分解。事实上，我想为最小二乘的非平方 Vandermonde 设计矩阵 V 求解“V·x = b”。我不想正则化。我看到多种方法:

使用 numpy.linalg.lstsq 求解 "V·x = b"，它使用基于 SVD 的 Fortran "xGELSD"。 SVD 应该比 LU 分解还要慢，但我不需要计算“(V^T·V)”。

使用 numpy.linalg.solve 求解 "(V^T·V)·x = (V^T·b)"，使用 LU 分解。

用 numpy.linalg.solve 求解 "A·x = b"，使用 LU 分解，但直接根据 https://math.stackexchange.com/a/3155891/340174 计算 "A=xV^T·V"

或者，我可以使用来自 scipy ( https://docs.scipy.org/doc/scipy-1.2.1/reference/generated/scipy.linalg.solve.html ) 的最新 solve ，它可以使用对称矩阵“A”的对角旋转(我猜这比使用 LU 分解更快)，但我的 scipy 停留在 1.1.0，所以我不不能访问那个。

从 https://stackoverflow.com/a/45535523/4533188 看来 solve 比 lstsq 更快，包括计算“V^T·V”，但是当我尝试它时，lstsq 更快。也许我做错了什么？

解决线性问题的最快方法是什么？

没有真正的选择

statsmodels.regression.linear_model.OLS.fit 使用 Moore-Penrose 伪逆或 QR-factorization + np.linalg.inv + np.linalg.svd + numpy.linalg.solve ，这对我来说似乎不太有效。

sklearn.linear_model.LinearRegression 使用 scipy.linalg.lstsq。

scipy.linalg.lstsq 也使用 xGELSD。

我预计计算“(V^T·V)”的倒数会非常昂贵，所以我放弃了“x = (V^T·V)^-1·(V^T·b)”的直接计算

最佳答案

我将忽略问题的 Vandermonde 部分(bubble 的评论指出它有一个解析逆)，而是回答关于其他矩阵的更一般的问题。

我认为这里可能会混淆一些事情，因此我将区分以下几点:

使用 LU

的 V x = b 精确解

V x = b 使用 QR 的精确解

V x = b 的最小二乘解，使用 QR

V x = b 的最小二乘解，使用 SVD

使用 LU

的 V^T V x = V^T b 精确解

使用 Cholesky

的 V^T V x = V^T b 精确解

您链接到的第一个 maths.stackexchange 答案是关于案例 1 和 2。当它说 LU 很慢时，这意味着相对于特定类型矩阵的方法，例如正定、三角形、带状、...

但我认为你实际上是在问 3-6。最后一个 stackoverflow 链接指出 6 比 4 快。正如你所说，4 应该比 3 慢，但 4 是唯一一个适用于排名不足的 V 。一般来说，6 应该比 5 快。

我们应该确保你做了 6 而不是 5。要使用 6，你需要使用 scipy.linalg.solve 和 assume_a="pos" 。否则，你最终会做 5。

我还没有在 numpy 或 scipy 中找到一个可以执行 3 的函数。 Lapack 例程是 xGELS，它似乎没有在 scipy 中公开。您应该可以使用 scupy.linalg.qr_multiply 后跟 scipy.linalg.solve_triangular 来完成。

关于python - 解决线性最小二乘法的最快方法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/55367024/