

3.9 计算上的考虑

原文	The Elements of Statistical Learning
翻译	szcf-weiya
发布	2017-11-15
更新	2019-01-31
状态	Done

最小二乘拟合一般通过对矩阵 $\mathbf X^T\mathbf X$ 进行 Cholesky 分解或者对 $\mathbf X$ 进行 QR 分解实现．在有 $N$ 个观测和 $p$ 个特征时，Cholesky 分解需要 $p^3+Np^2/2$ 次操作，而 QR 分解需要 $Np^2$ 次操作．依赖于 $N$ 和 $p$ 的相对大小，Cholesky 分解有时会更快，但是另一方面，数值不太稳定（Lawson and Hansen, 1974¹）．通过 LAR 算法实现的 lasso 的计算量与最小二乘拟合有相同的阶数．

weiya 注：Cholesky and QR decomposition for Least Squares

对于 Cholesky 分解，考虑线性方程 $\X^T\X\beta=\X^T\Y$，若 $\X^T\X=\L\L^T$, 则转换为求解 $\L w=\X^T\Y$ and $\L^T\beta=w$.

对于 QR 分解，考虑线性方程 $\X\beta = \Y$，若 $\X = \Q\R$，则 $\Q\R\beta = \Y=\Q\Q^T\Y$，所以转换为求解 $\R\beta=\Q^T\Y$．

更多细节详见这里.

weiya 注：Complexity

正如维基中指出的那样，不同计算方法会有不同的复杂度，一般情形下 Cholesky 分解复杂度为 $O(p^3)$，但也存在 $O(p^3/3)$，这里更是指出其复杂度为 $O(Np^2+p^3/3)$. 对于 QR 分解，情况类似，这里 指出其复杂度为 $O(Np^2-2p^3/3)$.

---

1. Lawson, C. and Hansen, R. (1974). Solving Least Squares Problems, Prentice-Hall, Englewood Cliffs, NJ. ↩

💬 讨论区