c++ - 使用 L1 范数的多项式拟合

Question

我有 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++ 中调用？是否有任何可用的源代码可以快速修改以满足我的需要？

Answer 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，如果它的许可证不是问题，我建议使用它。