algorithm - 线性回归 - 使用什么算法来解决最小二乘法 - 逆或 LU 或......？

Question

我正在研究对一个或多个自变量执行线性回归的算法。

即:(如果我有 m 个真实世界值，并且在两个自变量 a 和 b 的情况下)

C + D*a1 + E* b1 = y1

C + D*a2 + E* b2 = y2

...

C + D*am + E* bm = ym

我想使用最小二乘法找到最佳拟合直线。

我将使用矩阵符号所以

其中 Beta 是向量 [C, D, E]，其中这些值将是最佳拟合线。

问题解决这个公式的最佳方法是什么？我应该计算 的倒数吗？

或者我应该使用矩阵的 LU 因式分解/分解。每个在大量数据上的性能如何(即 m 的大值，可能是 10^8 ...)

编辑

如果答案是使用 Cholesky 分解或 QR 分解，是否有任何实现提示/简单的库可供使用。我正在使用 C/C++ 进行编码。

Answer 1

解决稠密超定系统 Ax=b 的两种直接方法浮现在脑海中:

1. 形成 A^T A x = A b，然后 Cholesky 分解 A^T A = L L^T，然后进行两次反向求解。这通常会让您得到一个精确到 sqrt(机器 epsilon)的答案。

2. 使用 Householder 消元之类的方法计算 QR 因式分解 A = Q*R，其中 Q 的列是正交的，R 是正方形和上三角形。然后通过回代求解 x 的 Rx = Q^T b。这通常会让您得到关于机器 epsilon 的精确答案 --- 精度是 Cholesky 方法的两倍，但它花费的时间大约是其两倍。

对于稀疏系统，我通常更喜欢 Cholesky 方法，因为它可以更好地利用稀疏性。