Projizieren von hochdimensionalen Ellipsoiden

krümelkacker

Ich würde gerne etwas berechnen, weiß aber gerade nicht, wie ich dort hinkomme. Vielleicht habt ihr ja eine Idee:

Gegeben:
- eine NxN symmetrisch positiv (semi-)definite Matrix H
- eine positive reelle Zahl M
- eine Indexmenge I, Teilmenge aus {1,2,...,N}

Über eine solche Matrix H mit einem Wert M kann ich mir die Menge S definieren:
S := {x | x^T H x <= M} (hochdimensionales Ellipsoid)

Gesucht:
- eine Matrix H', die nur h_i,j mit i,j aus I nicht verschwindende Elemente besitzt. Die restlichen Elemente sind also alle 0.
- wobei die dazugehörige Menge S' so "klein" wie möglich ist, dabei aber noch S komplett enthält

Räumlich kann man sich das so vorstellen: Das Ellipsoid S wird orthogonal auf eine Hyperebene projiziert und mich interessiert die resultierende Ellipse in der Hyperebene. Das ist übrigens nicht der Schnitt der Ebene mit der Ellipse.

Irgendwer 'ne Idee?

Mein Gefühl sagt mir, dass man dazu ein Gleichungssystem a la H*A = B aufstellen und für A lösen muss.

CStoll

Irgendwie habe ich jetzt gerade keine Ahnung, was du damit erreichen willst. Wie definierst du "klein" in diesem Zusammenhang?

Um das mal etwas anschaulicher zu machen: Wie würde denn die "Projektion" einer Kugel in eine zweidimensionale (Hyper)ebene aussehen?

Bashar

CStoll schrieb:

Um das mal etwas anschaulicher zu machen: Wie würde denn die "Projektion" einer Kugel in eine zweidimensionale (Hyper)ebene aussehen?

Das wäre der kleinste Zylinder, der senkrecht auf der Ebene steht und die Kugel enthält. Würde ich nicht wirklich Projektion nennen, aber so hat er's beschrieben.

Edit: Kann man das nicht erreichen, indem man einfach die Zeilen und Spalten, dieh nicht in I sind, auf 0 setzt? Du willst nur auf die Koordinatenhyperebenen projizieren, richtig?

bmario

Das was du suchst ist eine Hauptachsentransformation. Soweit ich mich erinnere geht man dazu über die EW von H und sucht dann eine Matrix, so dass sich H schreiben lässt als $H=S^TAS$ , wobei A eine Matrix mit Spalten aus Eigenvektoren ist. Oder so ähnlich ging das

krümelkacker

CStoll schrieb:

Irgendwie habe ich jetzt gerade keine Ahnung, was du damit erreichen willst. Wie definierst du "klein" in diesem Zusammenhang?

Die Menge, die am wenigsten Punkte enthält. Es gibt eine Punktemenge, die eine Teilmenge von allen Punktemengen ist, die die anderen Bedingungen erfüllen. Die dazugehörige Matrix H' suche ich.

CStoll schrieb:

Um das mal etwas anschaulicher zu machen: Wie würde denn die "Projektion" einer Kugel in eine zweidimensionale (Hyper)ebene aussehen?

Eine Kugel ist ein uninteressanter Spezialfall, da in diesem Fall der Schnitt zwischen Kugel und Ebene gleich der Projektion aller Kugelpunkte auf die Ebene ist.

Bashar schrieb:

Das wäre der kleinste Zylinder, der senkrecht auf der Ebene steht und die Kugel enthält. Würde ich nicht wirklich Projektion nennen, aber so hat er's beschrieben.

Genau. Naja, der Schnitt dieses Zylinders ist die Projektion aller Punkte im Ellipsoiden auf die Hyperebene. Ich glaube, Du hast verstanden, was ich wollte.

Bashar schrieb:

Edit: Kann man das nicht erreichen, indem man einfach die Zeilen und Spalten, dieh nicht in I sind, auf 0 setzt?

Nein, das ist nicht dasselbe.

Bashar schrieb:

Du willst nur auf die Koordinatenhyperebenen projizieren, richtig?

Ja, aber im Fall von Ellipsoiden ist das nicht äquivalent zur Schnittmenge zwischen Ellipsoid und Hyperebene.

bmario schrieb:

Das was du suchst ist eine Hauptachsentransformation.

Nicht wirklich. Ich würde liebend gern drum herum kommen, von H die Eigenwertzerlegung zu berechnen, da die Matrix riesengroß ist und die Indexmenge I typischerweise sehr klein ist, 3.

Bashar

krümelkacker schrieb:

Bashar schrieb:

Edit: Kann man das nicht erreichen, indem man einfach die Zeilen und Spalten, dieh nicht in I sind, auf 0 setzt?

Nein, das ist nicht dasselbe.

Hm, ich seh meinen Fehler. Dann muss ich nochmal etwas drüber nachdenken.

Bashar schrieb:

Du willst nur auf die Koordinatenhyperebenen projizieren, richtig?

Ja, aber im Fall von Ellipsoiden ist das nicht äquivalent zur Schnittmenge zwischen Ellipsoid und Hyperebene.

Das ist klar. Man denke einfach an eine langgestreckte Ellipse, wie eine Zigarre, die in einem schiefen Winkel zu der Ebene liegt.

- vektor x in orthogonale (x_o) und parallele (x_p) komponente zerlegen
- x^THx über x_o mit konstantem x_p minimieren (-> Lagrange!)
- Ursprungsgleichung auf die Form x^TH'x bringen. Gefühlt sollte die Einschränkung von H' auf den Unterraum automatisch folgen.

Das Gerechne bleibt dem geneigten Leser überlassen

krümelkacker

gagamel, das kann ich leider nicht nachvollziehen, wie du das gemeint hast.

krümelkacker schrieb:

Ich würde gerne etwas berechnen, weiß aber gerade nicht, wie ich dort hinkomme. Vielleicht habt ihr ja eine Idee:

Gegeben:
- eine NxN symmetrisch positiv (semi-)definite Matrix H
- eine positive reelle Zahl M
- eine Indexmenge I, Teilmenge aus {1,2,...,N}

Über eine solche Matrix H mit einem Wert M kann ich mir die Menge S definieren:
S := {x | x^T H x <= M} (hochdimensionales Ellipsoid)

Gesucht:
- eine Matrix H', die nur h_i,j mit i,j aus I nicht verschwindende Elemente besitzt. Die restlichen Elemente sind also alle 0.
- wobei die dazugehörige Menge S' so "klein" wie möglich ist, dabei aber noch S komplett enthält

Räumlich kann man sich das so vorstellen: Das Ellipsoid S wird orthogonal auf eine Hyperebene projiziert und mich interessiert die resultierende Ellipse in der Hyperebene. Das ist übrigens nicht der Schnitt der Ebene mit der Ellipse.

Irgendwer 'ne Idee?

Mein Gefühl sagt mir, dass man dazu ein Gleichungssystem a la H*A = B aufstellen und für A lösen muss.

wenn ich dich richtig verstanden habe, suchst du

S' := {x | min_{x_o}{{(x_o + x_p)^T H (x_o + x_p)} <= M}

mit:
x_o orthogonal zur hyperebene und x = x_o + x_p

d.h. ein punkt ist in S' wenn die projektion irgendeines punktes aus R^N in S ist.

das minimierungsproblem kannst du explizit lösen, da es ein einfaches quadratisches problem ist. damit hast du eine explizite darstellung von S', und der Schnitt von S' mit der Hyperebene ist deine gesuchte Menge.