计算科学 - 使用稀疏矩阵的 L1 最小二乘法 - 吾爱随笔录

计算科学优化稀疏矩阵最小二乘

2021-12-04 17:39:15

我有以下问题：

min_{x \in R^{n}} ‖ A x - b ‖_{1}

$\min_{x\in \mathbb{R}^n}\|Ax-b\|_1$

其中矩阵 $A$ 大而稀疏。我正在寻找可以有效减少这种情况的方法/代码。非常欢迎参考。

2个回答

如果你有一个好的 LP 求解器，那么线性规划方法通常效果很好。不过，您不想为 LP 实现自己的单纯形或内点代码。

由于 Barrodale 和 Roberts，单纯形法的一个特殊变体是解决这个问题的一种流行方法，但它需要一些努力才能有效地实现，并且您最好使用高质量的 LP 求解器，而不是编写自己的 Barrodale 实现和罗伯茨。

还有其他方法

如果您已经拥有诸如 LSQR 之类的最小二乘求解器，则迭代重加权最小二乘法 (IRLS) 特别容易实现。

次梯度下降法也很容易实现。如果您的矩阵的行数远多于列数，则行的随机抽样可以产生一个足够好的近似次梯度。

感谢 Wolfgang Bangerth 指出这可以重写为线性问题。我的重新表述是：

min_{x \in R^{N}} ‖ A x - b ‖_{1} ⟹

$\min_{x\in\mathbb{R}^N}\|Ax-b\|_1 \implies$

min_{(x, y) \in R^{N + M}} \sum_{i = 1}^{N} y_{i},

$\min_{(x,y)\in\mathbb{R}^{N+M}}\sum_{i=1}^N y_i,$

A x - y \leq b

$Ax - y \leq b$

- (A x + y) \leq - b

$-(Ax+y) \leq -b$

y \geq 0

$y\geq0$

其它你可能感兴趣的问题