1

我有 n 个点 (x0,y0),(x1,y1)...(xn,yn)。n 很小 (10-20)。我想用一个低阶 (3-4) 多项式拟合这些点：P(x)=a0+a1*x+a2*x^2+a3*x^3。

我已经使用最小二乘法作为误差度量来实现这一点，即最小化 f=(p0-y0)^2+(p1-y1)^2+...+(pn-yn)^2。我的解决方案是利用奇异值分解 (SVD)。

现在我想使用 L1 范数（绝对值距离）作为误差度量，即最小化 f=|p0-y0|+|p1-y1|+...+|pn-yn|。

是否有任何库（最好是开源的）可以做到这一点，并且可以从 C++ 调用？是否有任何可用的源代码可以快速修改以满足我的需要？

4

3 回答 3

1

是的，它应该是可行的。将多项式拟合问题表述为多元线性回归的标准方法是定义变量 x1、x2 等，其中 xn 定义为 x.^n（Matlab 表示法中的逐元素取幂）。然后您可以将所有这些向量（包括截距）连接到设计矩阵 X 中：

X = [ 1 x1 x2 x3 ]

那么你的多项式拟合问题是一个回归问题：

argmin_a ( | y - X * a| )

哪里| | notation 是您想要的成本函数（对于您的情况，L1 范数）并且 a 是权重向量（抱歉，据我所知，SO 没有很好的数学标记）。这种回归被称为“稳健回归”，Numerical Recipes 有一个计算它们的例程：http ://www.aip.de/groups/soe/local/numres/bookfpdf/f15-7.pdf

希望这可以帮助！

于 2013-06-12T15:34:31.367 回答
1

L_1 回归实际上很简单地表述为线性程序。你想要

minimize    error
subject to  x_1^4 * a_4 + x_1^3 * a_3 + x_1^2 * a_2 + x_1 * a_1 + a_0 + e_1 >= y_1
            x_1^4 * a_4 + x_1^3 * a_3 + x_1^2 * a_2 + x_1 * a_1 + a_0 - e_1 <= y_1
            .
            .
            .
            x_n^4 * a_4 + x_n^3 * a_3 + x_n^2 * a_2 + x_n * a_1 + a_0 + e_n >= y_n
            x_n^4 * a_4 + x_n^3 * a_3 + x_n^2 * a_2 + x_n * a_1 + a_0 - e_n <= y_n
            error - e_1 - e_2 - ... - e_n = 0.

您的变量是a_0, a_1, a_2, a_3, a_4、error和所有e变量。 x并且y是你的问题的数据，所以x在二、三、四次方看来都不是问题。

您可以使用GLPK (GPL) 或lp_solve (LGPL) 或任意数量的商业软件包解决线性规划问题。我喜欢 GLPK，如果它的许可证没有问题，我建议使用它。

于 2013-06-12T17:08:48.370 回答
0

L1 范数的问题在于它不可微，因此任何依赖导数的最小化器都可能失败。当我尝试使用例如共轭梯度最小化来最小化这些类型的函数时，我发现答案卡在了扭结处，即函数 y=|x| 中的 x=0。

我经常从第一原理解决这些数学计算问题。在这里可能有效的一个想法是，目标函数将在低阶多项式的系数中呈分段线性。因此，可以通过从最小二乘得出的多项式开始解决，然后通过解决一系列线性问题来改进解决方案，但每次只能从您当前的最佳解决方案到最近的扭结点。

于 2013-06-12T14:56:20.160 回答