Skip to content

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=LL^T$, 则转换为求解 $Lw=\X^T\Y$ and $L^T\beta=w$.

对于 QR 分解,考虑线性方程 $\X\beta = \Y$,若 $\X = QR$,则 $QR\beta = \Y=QQ^T\Y$,所以转换为求解 $Rx=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. 

Comments