计算科学 - 更新岭回归的LU分解的聪明方法 - 吾爱随笔录 - 问答

更新岭回归的LU分解的聪明方法

计算科学回归矩阵分解更新

2021-12-10 23:10:51

岭回归可以表示为最小化以下目标函数（超过 $x$ ):

\frac{1}{2} ‖ A x - b ‖_{2}^{2} + \frac{λ}{2} ‖ x ‖_{2}^{2}

$\frac{1}{2} \lVert Ax - b \lVert_2^2 ~+ \frac{\lambda}{2} \lVert x \lVert_2^2$

其中有一个封闭形式的解决方案：

x = (A^{T} A + λ I)^{- 1} A^{T} b

$x = (A^TA + \lambda I)^{-1} A^T b$

假设我们想为的几个不同值解决这个问题。的 LU 分解是一个好主意。在 MATLAB I 中，这转换为： $b$ $A^TA + \lambda I$

[L,U] = factor(A'*A + lambda*I)
x1 = L \ U \ A'*b1
x2 = L \ U \ A'*b2
% etc...

这是我的问题：如果在几次求解后更新，是否有一种简单/有效的更新和的方法？还是我必须完全重做 LU 分解？ $\lambda$ $L$ $U$

1个回答

您的矩阵的大小是多少？是稀疏的吗？是否有其他特殊结构？你想尝试多少值？ $A$ $A$ $A$ $\lambda$

通常，您将使用的 Cholesky 分解而不是 LU 分解，因为是对称且正定的。然而，在全秩对角线更新后更新矩阵的 Cholesky 或 LU 分解在实践中并不容易（低秩更新是另一回事。） $A^{T}A+\lambda I$ $A^{T}A+\lambda I$

一种替代方法是使用的 SVD 计算正则化解。就 SVD 而言，Tikhonov 正则化解有一个简单的公式，因此您只需计算的 SVD一次。这是解决小型问题的合理方法（例如的行/列不超过几千行。）您也可以使用的特征值分解来代替的 SVD 。 $A$ $A$ $A$ $A^{T}A$ $A$

对于大问题，特别是在稀疏的情况下，通常使用迭代方法。您可以通过将显式正则化作为线性最小二乘问题来解决问题（提示：从参数的最大值到最小值工作，并使用先前的解决方案作为每个新值的起点）一种更常见的方法是使用诸如 Landweber 迭代或 CGLS 之类的迭代，当您在完全收敛之前停止迭代时，它将为您提供隐式正则化解决方案。 $A$ $\lambda$ $\lambda$

其它你可能感兴趣的问题

上一篇快速逼近卷积的方法下一篇-ffast-math 有什么作用？