Softwarepaket zur Lösung der linearen Regression der L-Unendlichkeitsnorm

Gibt es ein Softwarepaket zur Lösung der linearen Regression mit dem Ziel, die L-Unendlichkeitsnorm zu minimieren?

Kurze Antwort : Ihr Problem kann als lineares Programm (LP) formuliert werden, sodass Sie Ihren bevorzugten LP-Löser für die Aufgabe auswählen können. Lesen Sie weiter, um zu sehen, wie Sie das Problem als LP schreiben.

Dieses Minimierungsproblem wird oft als Chebyshev-Näherung bezeichnet .

Lassen Sie , mit Zeile bezeichnet mit und . Dann versuchen wir, die Funktion in Bezug auf zu minimieren . Bezeichne den optimalen Wert mit $\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 \} \>.$$

Der Schlüssel zur Neufassung als LP besteht darin, das Problem in epigraphischer Form neu zu schreiben . Es ist nicht schwer, sich davon zu überzeugen, dass tatsächlich

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

Unter Verwendung der Definition der Funktion können wir nun die rechte Seite oben als umschreiben und so sehen wir, dass das Minimieren der Norm in einer Regressionseinstellung dem LP wo die Optimierung durchgeführt wird über und bezeichnet einen Vektor von Einsen der Länge . Ich überlasse es dem Leser als (einfache) Übung, die obige LP in Standardform neu zu fassen.$f$

$$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$ $$\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$

Beziehung zur Version (Total Variation) der linearen Regression$\ell_1$

Es ist interessant festzustellen, dass mit der Norm etwas sehr Ähnliches getan werden kann . Sei . Ähnliche Argumente lassen dann den Schluss zu, dass so dass die entsprechende LP $\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}$$

Beachten Sie hier, dass jetzt ein Vektor der Länge anstelle eines Skalars ist, wie es im Fall Fall war.$\t$$n$$\ell_\infty$

Die Ähnlichkeit dieser beiden Probleme und die Tatsache, dass beide als LPs besetzt werden können, ist natürlich kein Zufall. Die beiden Normen hängen insofern zusammen, als sie die dualen Normen voneinander sind.

Malab kann das mit cvx. um cvx (kostenlos) zu bekommen:

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

In cvx würden Sie es so schreiben:

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

(siehe Beispiel Seite 12 des Handbuchs )

Es gibt eine Python-Implementierung von CVX ( hier ), aber die Befehle unterscheiden sich geringfügig ...

Die Antwort von @ cardinal ist gut formuliert und wurde akzeptiert, aber um diesen Thread vollständig zu schließen, biete ich Folgendes an: Die numerischen IMSL-Bibliotheken enthalten eine Routine zum Durchführen einer Regression der L-Unendlichkeitsnorm. Die Routine ist in Fortran, C, Java, C # und Python verfügbar. Ich habe die C- und Python-Versionen verwendet, für die die Methode lnorm_regression heißt, die auch die allgemeine -norm-Regression unterstützt, .$L_p$$p >= 1$

Beachten Sie, dass dies kommerzielle Bibliotheken sind, die Python-Versionen jedoch (wie in Bier) für den nichtkommerziellen Gebrauch kostenlos sind.