使用L1範數的多項式擬合

我有n個點（x0，y0），（x1，y1）...（xn，yn）。 n很小（10-20）。我想用一個低階（3-4）多項式擬合這些點：P（x）= a0 + a1 * x + a2 * x^2 + a3 * x^3。使用L1範數的多項式擬合

我已經完成了這種使用最小平方作爲誤差度量，即最小化f =（p0-y0）^ 2 +（p1-y1）^ 2 + ... +（pn-yn）^ 2。我的解決方案是利用奇異值分解（SVD）。

現在我想用L1範數（絕對值距離）作爲誤差度量，即最小化f = | p0-y0 | + | p1-y1 | + ... + | pn-yn |。

是否有任何庫（最好是開源的）可以做到這一點，並可以從C++調用？有沒有可以快速修改以適應我的需求的源代碼？

來源

2013-06-12 Dženan

你看過http://www.gnu.org/software/gsl嗎？ – 2013-06-12 14:11:41

@anjruu是的，我只做了最小二乘擬合，而不是L1範數擬合。 –

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-12 17:08:48 tmyklebu

我實現了這種方法，但它不起作用。即使我用一個完全位於多項式上的點進行測試，它也會失敗。 –

@Dženan：我也實現了它，它確實有效。 :)你遇到了什麼困難？ – tmyklebu

我用lp_solve來做到這一點，我沒有意識到默認情況下變量是非負的。將a0..a3設置爲無限使其正常工作。非常感謝您的建議。 –

L1範數的問題在於它不可微分，因此任何依賴於微分的最小化都可能失敗。當我嘗試使用例如最小化這些功能時共軛梯度最小化，我發現答案卡在扭結處，即函數y = | x |中的x = 0。

我經常從第一原理解決這些數學計算問題。可能在這裏工作的一個想法是，目標函數將在您的低階多項式的係數中呈分段線性。因此，可以通過從最小二乘出來的多項式開始求解，然後通過求解一系列線性問題來改進求解，但每次只從當前最佳解決方案跳到最接近的扭結。

來源

2013-06-12 14:56:20 Stochastically

我正在尋找一個現有的解決方案，以便不必自己編程。本的和tmyklebu的答案更符合我的想法。但是謝謝你分享想法！ –

是的，它應該是可行的。將多項式擬合問題表示爲多重線性迴歸的一種標準方法是定義變量x1，x2等，其中xn被定義爲x。^ n（在Matlab符號中按元素取冪）。然後，你可以連接所有這些載體，包括一個截距，成設計矩陣X：

X = [1 X1 X2 X3]

然後您的多項式擬合問題是一個迴歸問題：

argmin_a（ | y - X * a |）

其中| |符號是你想要的成本函數（對於你的情況，L1標準）和a是一個權重矢量（抱歉，因爲我沒有看到好的數學標記）。這種迴歸被稱爲「強大的迴歸」，數值食譜有一個例程來計算它們：http://www.aip.de/groups/soe/local/numres/bookfpdf/f15-7.pdf

希望這有助於！

來源

2013-06-12 15:34:31 ben

使用L1範數的多項式擬合

回答

相關問題