Die cvx -Suite für MATLAB kann das (scheinbar harmlose) Optimierungsproblem lösen, ist aber für die großen, vollständigen Matrizen I eher langsam arbeite mit. Ich hoffe, dies liegt daran, dass cvx Overkill ist und dass das Problem tatsächlich eine analytische Lösung hat, oder dass eine geschickte Verwendung einiger integrierter MATLAB-Funktionen die Aufgabe schneller erledigen kann.
Hintergrund: Es ist bekannt, dass sowohl x1=A\b und x2=pinv(A)*b lösen das Problem der kleinsten Quadrate:
mit der Unterscheidung, dass norm(x2)<=norm(x1) . Tatsächlich ist x2 die Mindestnormlösung für das Problem, also norm(x2)<=norm(x) für alle möglichen Lösungen x .
Definition von D=norm(A*x2-b) , (gleichbedeutend D=norm(A*x1-b) ), dann x2 löst das Problem
Problem: Ich würde gerne die Lösung finden für:
%Vor% In Worten, ich brauche norm(A*x-b) nicht so klein wie möglich, nur innerhalb einer bestimmten Toleranz. Ich möchte die Minimum-Norm-Lösung x , die A*x in D+threshold von b bekommt.
Ich war nicht in der Lage, eine analytische Lösung für das Problem (wie die Verwendung der Pseudoinverse im klassischen Kleinste-Quadrate-Problem) im Web oder von Hand zu finden. Ich habe nach Dingen wie "kleinste Quadrate mit nichtlinearer Abhängigkeit" und "kleinste Quadrate mit Schwellenwert" gesucht.
Alle Einsichten würden sehr geschätzt werden, aber ich nehme an, meine wirkliche Frage ist: Was ist der schnellste Weg, dieses "Schwellenwert-Problem" in MATLAB zu lösen?
Interessante Frage. Ich kenne die Antwort auf Ihre genaue Frage nicht, aber eine funktionierende Lösung ist unten dargestellt.
Definieren Sie res(x) := norm(Ax - b) .
Wie Sie sagen, minimiert x2 res(x) . Im überbestimmten Fall (in der Regel hat A mehr Zeilen als Spalten) ist x2 das eindeutige Minimum. Im unbestimmten Fall sind unendlich viele andere verbunden *. Unter all diesen ist x2 jedoch der einzige, der norm(x) minimiert.
Um zusammenzufassen, x2 minimiert (1) res(x) und (2) norm(x) , und zwar in dieser Reihenfolge der Priorität. Tatsächlich charakterisiert (bestimmt) x2 .
Aber eine weitere Charakterisierung von x2 ist
wo
%Vor%wo
%Vor%Es kann gezeigt werden, dass
%Vor% Es sollte beachtet werden, dass diese Charakterisierung von x2 ziemlich magisch ist. Die Grenzen existieren auch wenn (A A')^{-1} nicht existiert. Und das Limit behält Priorität (2) von oben bei.
Natürlich wird für endliche (aber kleine) e , x_e res(x) nicht minimieren (stattdessen minimiert es J(x;e) ). In Ihrer Terminologie ist der Unterschied der Schwellenwert. Ich werde es in
Wenn Sie den Wert von e verringern, wird der Wert von gap garantiert verringert. Das Erreichen eines bestimmten gap -Werts (d. H. Der Schwellenwert) ist daher leicht zu erreichen, indem e eingestellt wird. **
Dieser Modifikationstyp (Hinzufügen von norm(x) zum res(x) -Minimierungsproblem) wird als Regularisierung in der Statistik-Literatur bezeichnet und wird allgemein als eine gute Idee für die Stabilität (numerisch und in Bezug auf Parameterwerte) angesehen.
*: Beachten Sie, dass sich x1 und x2 nur im unterbestimmten Fall unterscheiden
**: Es erfordert nicht einmal schwere Berechnungen, weil die Umkehrung in (eqn a) leicht für jeden (positiven) Wert von e berechnet werden kann, wenn die SVD von A bereits berechnet wurde.
Tags und Links optimization matlab linear-algebra least-squares cvx