Pakiet oprogramowania do rozwiązania regresji liniowej normy L-infinity

Czy istnieje jakiś pakiet oprogramowania do rozwiązania regresji liniowej w celu zminimalizowania normy L-nieskończoności.

Krótka odpowiedź : Twój problem można sformułować jako program liniowy (LP), dzięki czemu możesz wybrać swój ulubiony solver LP do zadania. Aby zobaczyć, jak napisać problem jako LP, czytaj dalej.

Ten problem minimalizacji jest często określany jako przybliżenie Czebyszewa .

$\newcommand{\y}{\mathbf{y}}\newcommand{\X}{\mathbf{X}}\newcommand{\x}{\mathbf{x}}\newcommand{\b}{\mathbf{\beta}}\newcommand{\reals}{\mathbb{R}}\newcommand{\ones}{\mathbf{1}_n} \y = (y_i) \in \reals^n$$\X \in \reals^{n \times p}$$i$$\x_i$$\b \in \reals^p$$f(\b) = \|\y - \X \b\|_\infty$$\b$

$$f^\star = f(\b^\star) = \inf \{f(\b): \b \in \reals^p \} \>.$$

Kluczem do przekształcenia tego jako LP jest przepisanie problemu w formie epigraficznej . Nie jest trudno przekonać się, że w rzeczywistości

$$f^\star = \inf\{t: f(\b) \leq t, \;t \in \reals, \;\b \in \reals^p \} \> .$$

Teraz, korzystając z definicji funkcji , możemy przepisać prawą stronę powyżej jako a więc widzimy, że minimalizowanie normy w ustawieniu regresji jest równoważne LP gdzie przeprowadzana jest optymalizacja over , a oznacza wektor jedności o długości . Pozostawiam to (łatwe) ćwiczenie dla czytelnika, aby przekształcić powyższy LP w standardowej formie.f ⋆ = inf { t : - t ≤ y i - x i β ≤ t $f$ℓ ∞ minimalizuj t z zastrzeżeniem y - X β ≤ t 1

$$f^\star = \inf\{t: -t \leq y_i - \x_i \b \leq t, \;t \in \reals, \;\b \in \reals^p,\; 1 \leq i \leq n \} \>,$$ $\ell_\infty$ (β,t)1n $$\begin{array}{ll} \text{minimize} & t \\ \text{subject to} & \y-\X \b \leq t\ones \\ & \y - \X \b \geq - t \ones \>, \\ \end{array}$$ $(\b, t)$$\ones$$n$

Związek z wersją regresji liniowej (całkowita zmienność)$\ell_1$

Warto zauważyć, że coś bardzo podobnego można zrobić za pomocą normy . Niech . Następnie podobne argumenty prowadzą do wniosku, że więc odpowiedni LP to $\ell_1$$g(\b) = \|\y - \X \b \|_1$

$$\newcommand{\t}{\mathbf{t}} g^\star = \inf\{\t^T \ones : -t_i \leq y_i - \x_i \b \leq t_i, \;\t = (t_i) \in \reals^n, \;\b \in \reals^p,\; 1 \leq i \leq n \} \>,$$ $$\begin{array}{ll} \text{minimize} & \t^T \ones \\ \text{subject to} & \y-\X \b \leq \t \\ & \y - \X \b \geq - \t \>. \\ \end{array}$$

Zauważ, że jest teraz wektorem długości zamiast skalara, tak jak to było w przypadku .$\t$$n$$\ell_\infty$

Podobieństwo tych dwóch problemów i fakt, że można je obsadzić jako płyty LP, oczywiście nie jest przypadkiem. Dwie normy są ze sobą powiązane, ponieważ są one podwójnymi normami .

Malab może to zrobić za pomocą CVX. aby uzyskać cvx (bezpłatny):

http://cvxr.com/cvx/download/

W cvx napisałbyś to w ten sposób:

cvx_begin
   variable x(n);
   minimize( norm(A*x-b,Inf) );
cvx_end

(patrz przykładowa strona 12 instrukcji )

Istnieje implementacja CVX w Pythonie ( tutaj ), ale polecenia są nieco inne ...

$L_p$$p >= 1$

Zauważ, że są to biblioteki komercyjne, ale wersje Pythona są bezpłatne (jak w piwie) do użytku niekomercyjnego.