Optimierung mit orthogonalen Einschränkungen

8

Ich arbeite an Computer Vision und muss eine Zielfunktion optimieren, die Matrix beinhaltet X und Matrix X ist eine orthogonale Matrix.

maximize  f(X)

s.t  XTX=I
Wo Iist die Einheitsmatrix. Ich lese gerade eine Zeitung und sie sprachen über komplizierte Begriffe wie Optimierung über Grassmanian Manfiold, Stiefel Manifold. Grundsätzlich unterscheidet sich der Gradient auf diesen Mannigfaltigkeiten von den regulären Gradienten über euklidischen Räumen.

Können Sie mir ein leicht zu lesendes Papier vorschlagen, damit ich die gradientenbasierte Methode auf diesen Mannigfaltigkeiten implementieren kann? Wenn es einfache Matlab-Beispiele gibt, die die Dokumente veranschaulichen, ist dies hilfreich

Vielen Dank

Lan Trần Thị
quelle
1
Können Sie bitte weitere Informationen zu Ihrem Problem bereitstellen? Derzeit ist die Beantwortung sehr weit gefasst. Zum Beispiel können Sie auch eine zufällige quadratische Matrix erzeugenYHolen Sie sich seine SVD so, dass Y=USVT und verwenden U als Kandidatenlösung für X.
usεr11852
1
Was ist f(.)?
user603
4
Benötigen Sie wirklich die allgemeine Behandlung von Stiefel-Mannigfaltigkeiten oder würde es ausreichen, Informationen über die (viel einfachere) Einschränkung zu haben? XX=I? Im letzteren Fall reduziert sich das Problem auf die Bewegung entlang von Kreisen. Das einfachste Beispiel hierfür sind zwei Dimensionen, in denen die Einschränkung den Einheitskreis definiert: Der Gradient an einem Punkt ist entlang der Tangentenlinie an diesem Punkt gerichtet, aber um dem Gradienten zu folgen, müssen Sie sich entlang des Kreises und nicht entlang der Tangentenlinie bewegen . Diese Idee verallgemeinert. (cc @ usεr11852)
whuber
@whuber: +1 und danke, dass du mich cc :: ing hast. Ich stimme offensichtlich zu. Mit meinem Beispiel wollte ich nur zeigen, dass selbst eine vereinfachte Zufallssuche ausreichen würde, um gültige Kandidatenlösungen zu erhalten.
usεr11852
4
@GeoMatt Dies könnte elementarer sein als Sie denken. Der Unterschied ist folgender: im Flugzeug,f ist eine auf dem Einheitskreis definierte Funktion x2+y2=1. Sie können es optimieren, indem Sie es auf eine Funktion aller erweitern(x,y) in einer Nachbarschaft des Einheitskreises und unter Verwendung von Lagrange-Multiplikatoren, um die Einschränkung durchzusetzen x2+y2=1. Oder Sie können den Einheitskreis als parametrisieren(x,y)=(cos(t),sin(t))und damit machen f eine periodische Funktion der Variablen tund optimieren Sie es ohne Einschränkungen. Genau die gleiche Methode funktioniert mit orthogonalen Matrizen (und Grassmann-Mannigfaltigkeiten).
whuber

Antworten:

7

Ich fand das folgende Papier nützlich:

Edelman, A., Arias, TA & Smith, ST (1998). Die Geometrie von Algorithmen mit Orthogonalitätsbeschränkungen . SIAM Journal on Matrix Analysis and Applications, 20 (2), 303-353.

Dieses Dokument enthält weitaus mehr Informationen als Sie möglicherweise benötigen, was die Differentialgeometrie und Optimierungsmethoden höherer Ordnung betrifft.

Die Informationen zur Beantwortung Ihrer Frage sind jedoch recht einfach und enthalten hauptsächlich die Gleichungen 2.53 und 2.70, die beide die Form haben

f=GXΦ
wo der nominelle Gradient
G=fX
wird auf einen eingeschränkten Gradienten korrigiert f durch Subtrahieren seiner Projektion Φ auf die aktuelle Lösung X. Dies ist die Normale zum Verteiler, ähnlich wie bei einer Kreisbewegung , und stellt sicher, dass der korrigierte Gradient den Verteiler tangiert.

Hinweis: Diese Formeln setzen voraus, dass Sie sich bereits auf dem Verteiler befinden, d. H.XTX=I. In der Praxis müssen Sie also sicherstellen, dass Ihr Ausgangszustand angemessen ist (zX0=Imöglich rechteckig). Möglicherweise müssen Sie auch gelegentlich akkumulierte Rundungs- und / oder Kürzungsfehler korrigieren (z. B. über SVD, siehe Beispiel "ZCA" unten).

Im ungezwungenen Fall Φ=0im eingeschränkten Fall Φ nimmt zwei Formen an:

ΦG=XTGGf=(IXXT)G
das entspricht der "Grassmann-Mannigfaltigkeit". Der Unterschied hier ist dasGist unempfindlich gegen Rotationen , da für eine RotationQTQ=I und X=X0Q, wir haben XXT=X0X0T.

Die zweite Form ist

ΦS=GTXSf=GXGTX
Das entspricht dem "Stiefel-Verteiler" und ist drehempfindlich.

Ein einfaches Beispiel ist die Approximation einer gegebenen Matrix ARn×p mit pn durch eine orthogonale Matrix XMinimieren des Fehlers der kleinsten Quadrate. In diesem Fall haben wir

f[X]=12XAF2=12ij(XijAij)2G=XA
Das ungezwungene Fallf=G hat Lösung X=A, weil es uns nicht darum geht, dies sicherzustellen X ist orthogonal.

Für den Grassmann-Fall haben wir

Gf=(XXTI)A=0
Dies kann nur eine Lösung haben A ist eher quadratisch als "dünn", denn wenn p<n dann Xwird ein Null-Leerzeichen haben .

Für den Stiefel-Fall haben wir

Sf=XATXA=0
was auch dann gelöst werden kann p<n.

Diese beiden Fälle, Grassmann vs. Stiefel, entsprechen im Wesentlichen dem Unterschied zwischen " PCA vs. ZCA Whitening ". In Bezug auf die SVD , wenn die Eingabematrix istA=USVT, dann sind die Lösungen XG=U und XS=UVT. Die PCA-LösungXG gilt nur für eine quadratische Eingabe, dh Amuss die " Kovarianzmatrix " sein. Allerdings die ZCA-LösungXS kann verwendet werden, wenn Aist eine " Datenmatrix ". (Dies ist besser bekannt als das Problem der orthogonalen Krusten .)

GeoMatt22
quelle
2
Ich glaube nicht X0=Iist ein guter Ausgangspunkt, denn dann ist die Ableitung 0.
user103828