3.9 计算上的考虑¶

最小二乘拟合一般通过对矩阵 \(\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^TX\beta=X^TY\)，若 \(X^TX=LL^T\), 则转换为求解 \(L w=X^TY\) and \(L^T\beta=w\).

对于 QR 分解，考虑线性方程 \(X \beta = Y\)，若 \(X = QR\)，则 \(QR \beta = Y=QQ^TY\)，所以转换为求解 \(R \beta=Q^TY\)。

更多细节详见这里.

note “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.

统计学习精要(中文)

3.9 计算上的考虑

3.9 计算上的考虑¶