计算的考虑

1 Cholesky 分解

• Cholesky 分解是把一个对称正定的矩阵表示成一个下三角矩阵L和其转置的乘积的分解 $$Z = LL^T=R^TR$$

• 流程：

• 考虑最小二乘的导数为0的方程： $$X^TX\beta = X^T y\\ \Leftrightarrow LL^T\beta = X^T y \\ \Leftrightarrow L^T\beta = L^{-1}$$

• 流程：

• 计算出$X^TX$和$X^Ty​$

• 进行分解 $$X^TX = R^TR$$

• 计算下三角问题 $$X^TX\beta = X^T y\\ \leftrightarrow R^TR\beta = X^Ty\\ \leftrightarrow R^Tw =X^T y$$

• 或者计算上三角问题 $$X^TX\beta = X^T y\\ R\beta = R^{-1} X^Ty\\ $$

• 复杂度：为$p^3 + Np^2$

2 QR 分解

• 算法流程

• 计算出$X^TX$和$X^Ty$

• 进行QR分解 $$X=QR$$

• 计算出$Q^T y$

• 解决上三角问题 $$X^TX\beta = X^Ty\\ \leftrightarrow R^T R\beta = R^TQ^Ty\\ \leftrightarrow R\beta = Q^Ty$$

• 复杂度$O(Np^2)​$

3 lasso

• 通过 LAR 算法实现的 lasso 的计算量与最小二乘拟合有相同的阶数