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, 19741）．通过 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)$.
-
Lawson, C. and Hansen, R. (1974). Solving Least Squares Problems, Prentice-Hall, Englewood Cliffs, NJ. ↩