3.9 关于计算量

最小二乘拟合通常通过矩阵 ${\mathbf{X}}^T\mathbf{X}$ 的 Cholesky 分解或矩阵 $\mathbf{X}$ 的 QR 分解来计算。若样本量为 $N$，输入变量维度为 $p$，Cholesky 分解的计算量为 $p^3+N{p}^2/2$，QR 分解的计算量为 $N{p}^2$。在特定的 $N$ 和 $p$ 组合下，Cholesky 可能会快于 QR；但另一方面，前者可能在数值运算稳定性上不如后者（Lawson and Hansen, 1974）。通过最小角回归算法求解套索回归，与最小二乘拟合的计算量级别相同。