ein wenig matrixalgebra..

[FORYOUITERRA]

jungs, ich steh gerade bisschen auf der leitung.

gilt auch für eine eine _beliebige nxm_ matrix X (n größer gleich m) mit X'X= I (=>X besteht aus orthonormalen spalten vektoren). y ist nx1, b ist mx1.

(Xb-y)'(Xb-y) = (b-X'y)'(b-X'y)?

es gilt ja:

(Xb-y)'(Xb-y) = b'X'Xb - b'X'y - y'Xb + y'y = b'b - b'X'y - y'Xb + y'y

(b-X'y)'(b-X'y) = b'b -b'X'y-y'Xb + y'XX'y

die beiden zeilen wären nur dann identisch, wenn y'XX'y = y'y gelten würde.
gilt dies nur, falls X eine orthogonale Matrix ist (das heißt X ist implizit nxn)?

dann gilt ja X'X=XX' = I und die obige Gleichung folgt unmittelbar.

merci beaucoup.

edit: nach gegenbeispielsimulation gilt es auf keinen fall allgemein im m>n setting. schade eigentlich.

 

[Aquarius]

Was meinst du mit I? Die Einheitsmatrix? Und ' is des Matrizenprodukt? Des ganze Zeug mit orthogonal ect is nur für quadratische Matrizen definiert. Maximal gibtz zu mxn-Matrizen rechts- oder linksinverse. (aber keine echte Inverse).

Und ne Matrix kann keine Orthonormalbasis des R^n als Spaltenvektoren haben, wenn se net quadratisch ist. Entweder sinds zuwenig Vektoren, oder zuviele, d.h. du kannst entweder keine Basis bilden oder die Vektoren wären linear abhängig (Vektorenzahl > n), womit es auch keine Basis mehr wär. Orthonormale Vektoren, die n R^n aufspannen, sind immer linear unabhängig.

Was du mit den Gleichungen meinst, ka ehrlichgesagt, is mir zu anstrengend jetz noch

guck ich mir demnächst mal an. Ich glaub aber, ne orthonormale Matrix is immer orthogonal.

Googel mal n bissle nach linearer Algebra, lies mal in Büchern rum und nimm Wikipedia als Hilfe, die is öfters nt schlecht, v.a. wenn der Rest versagt. (Ohne die würd ich heute noch über Jacobi-Matrizen darben)

 

[crazyBlTCH]

was genau ist deine frage? ob y'XX'y = y'y nur genau dann gilt, wenn X orthogonal? so ist orthogonal ja gerade definiert: http://de.wikipedia.org/wiki/Orthogonale_Matrix
oder war die frage ob die gleichungen und umformungen richtig sind?

 

[FORYOUITERRA]

Meine Frage war, ob es eine NICHT quadratische Matrix X gibt mit der Eigenschaft
X'X= I (kein problem, gilt für alle X, die aus orthornomalen Spaltenvektoren bestehen)
und XX'=I (gilt hingegen nicht mehr bei obiger Konstruktion von X)

' ist die Transponierte und I natürlich die Einheitsmatrix.
Orthonormale Matrizen gibt es übrigens nicht.

 

[Amad3us]

Ich würde Nein sagen, denn:

Angenommen es gebe eine nxk-Matrix (o.B.d.A n>k) mit der Eigenschaft, dann wäre:

1) XX'=I(nxn) und 2) X'X=I(kxk)

Nun gilt aber stets für jede Matrix A: Rang(A)=Rang(A'A)=Rang(AA')

Angewandt auf die obigen Gleichungen folgt somit aus 1) :

Rang(X)=n;

Aus 2) folgt:

Rang(X)=k

Nun hast du folgenden Widerspruch: n=k .

 

[FORYOUITERRA]

danke dir

 

[FORYOUITERRA]

Jungs, nochmal meinen eigenen Thread hijacken, diesesmal keine Matrixalgebra:

z.Z.: es sei t>=0, die Menge M={x: x\in R^n, |x_1|+...+|x_n|<=t} ist kompakt
wobei <= : kleiner gleich bedeutet und |x| den betrag von x kennzeichnet.

 

[MesH]

Najo, du bist über R^n, also zeigst du beschränkt & abgeschlossen. Beschränktheit ist mehr oder weniger klar (da da quasi ||x||_1 <= t als Bedingung steht), falls ihr Äquivalenz von Normen über R^n kennt (wenn nicht, das zeigen ). Abgeschlossenheit könnte man mit Stetigkeit der Funktion x auf |x_1| + |x_2| + ... + |x_n| argumentieren zB..

 

[Dr. Picasso]

zeige: jede konvergente folge in M hat ihren grenzwert in M

 

[FORYOUITERRA]

vielen dank an euch, vor allem meshs idee mit der äquivalenz der normen war gut
nun noch eine kleine frage:

ich hab ein minimierungsproblem einer konvexen funktion f(x) mit x \in R^n unter der bedingung, daß x größer gleich 0 ist. (f: R^n -> R)
ich weiß zusätzlich, daß wenn x gegen unendlich, dann f(x) gegen unendlich. (1)
zu zeigen ist die existenz eines extremwertes.

den extremwertsatz von weierstrass kann ich ja nicht direkt anwenden, da die zulässige menge nicht kompakt ist.
ist hier das argument dennoch gültig, daß ich den satz von weierstrass dennoch anwenden kann, weil die lösung sich aufgrund von (1) auf einer hinreichend großen kompakten menge abspielen muß?
oder gibts gar noch einen besseren satz für meinen spezialfall?
danke schonmal.

 

[MesH]

Deine Idee ist okay, sofern du noch argumentierst, warum eine auf R^n konvexe Funktion auch stetig ist, würde ich sagen. Wenn ich mich recht entsinne, ist der Beweis aber gar nicht so leicht. Alternativ könntest du die Konvexität auch direkt benutzen. Vielleicht kommst du da drauf, wenn ich dir sage, dass du die Notwendigkeit von f(x) -> \infty für ||x|| -> \infty tatsächlich brauchst, damit ein Extremwert existiert (sonst mal f(x) = e^x anschauen). Also das auch wirklich ausnutzen.

 

[FORYOUITERRA]

habs mal bisschen mathematischer formuliert nun, kann ich das so machen?
Es galt: f war konvex (da reelwertig auch stetig), mit f(x) -> \infty, wenn ||x||_1 ->\infty. zu zeigen, die funktion nimmt mindestens ein minimum an.

beweis:
betrachte S={x \in R^n : f(x)<= f(0)}. (anmerkung: <= wieder "kleiner gleich").
Zeigen S ist kompakt und wenden dann Weierstrass'schen Hauptsatz an.

a) S ist abgeschlossen, da f stetig.
b) außerdem ist S beschränkt, denn: angenommen S wäre nicht beschränkt, dann existiert eine folge {x^k} \subset S derart, daß ||x^k||_1 -> \infty. Da aber f(x) -> \infty, falls ||x||_1 -> \infty widerspricht dies der Forderung, daß f(x^k)<= f(0).

Somit ist S kompakt und Satz von Weierstrass sagt, daß es mindestens ein Minimum auf S gibt.
ist das so korrekt? kann ich S so wählen?

desweiteren hab ich noch ein problem:
ich hab eine zielfunktion der form f(x) = g(x) + a*h(x). (x \in R^n) die es zu minimieren gilt.
g(x), h(x) sind dabei stetig, konvex (h jedoch nicht überall diffbar).
a>=0.
das Minimum existiert (muß nicht eindeutig sein) und die lösung x*, hängt natürlich von a ab, d.h. x*=x*(a). hier steht nun irgendwas davon, daß standard resultate zeigen würden, daß x*(a) eine stetig funktion wäre. warum ist das so?

 

[MesH]

Sieht für mich okay aus. Stetigkeit von konvexem f auf ganz R bzw. R^n habt ihr zur Verfügung? Sonst würd ich da nachhaken

Und zu deiner zweiten Frage: Anschaulich ist das doch recht deutlich, oder? Das Minimum wird nicht plötzlich wild durch die Gegend springen, wenn du a nur wenig änderst, da g und h ja selbst beide stetig sind. Lass dir am besten mal n paar Funktionenfamilien mit passendem g,h in Abhängigkeit von a plotten oder schau dir sowas an: http://www.wolframalpha.com/input/?i=plot+f%28x%29+%3D+x^2+%2B+a*e^x um das einzusehen (alternativ und eigentlich besser für deinen Fall, aber da spackt wolfram irgendwie rum: f(x) = x^2 + a*|x|) Ansonsten kann man das bestimmt auch beweisen, wird aber sicherlich nicht allzu schick.

 

[FORYOUITERRA]

merci fürs feedback. die wolframseite ist ja mal sehr geil.
stetigkeit und konvexität geht bei mir hand in hand, da die menge der zulässigen punkte, x\in R^n, natürlich offen ist:

http://de.wikipedia.org/wiki/Konvexe_und_konkave_Funktionen#Konvexit.C3.A4t_und_Stetigkeit

 

[MesH]

Mehr wollte ich nicht hören

 

[FORYOUITERRA]

blobb, hat einer auch noch zufällig eine ahnung womit und wie man gute 3d plots erstellen kann? geht um obige funktion aus dem anfangspost in R^3, f:R^3->R,

f(b)= b'b - b'X'y - y'Xb + KONSTANTE = ||Y-Xb||^2

wobei ||.|| die euklidische norm ist.
ich will dabei nur die kombinationen (b1,b2,b3) darstellen, die zu einem vorgegebenen funktionswert führen (also sowas wie konturlinien im R^2, eben nur dreidimensional: das sind dann ellipsen/bälle im dreidimensionalen raum.
womit bekomm ich das am leichtesten hin?
da X aus einer multivariaten normalverteilung gezogen wird sollte das programm einen random sampler für selbige am besten eingebaut haben oder die option daten extern einzulesen haben. R scheint mir für die zwecke ziemlich ungeeignet zu sein.

edit: falls es irgendwie hilft
die funktion ist bis auf die konstante durch f(b)= (b-c)'X'X(b-c) beschrieben (ist ellipsenschreibweise?), wobei c der minimierer der funktion ist (kq-schätzer)

edit2: r ist ungeeignet. gibt zwar contour3d zum plotten impliziter funktionen, aber relativ langsam und hässlich wie sau.

 

[FORYOUITERRA]

jungs, ich hab nochmal nen problem mit einem beweis.
Es sei X eine symmetrische R^(nxn) matrix mit
a'Xa >= M>0 für alle a aus R^n mit a'a = 1
(>= wieder größer gleich, ' : transponierte)
die bedingung ist hinreichend dafür, daß X invertierbar ist.

nun steht hier in einem beweis irgendwo die zeile

|X^{-1} d| <= 1/M ||d||_2

wobei ||.||_2 die euklidische norm ist und d ein vektor R^n mit einträgen, die entweder 1 oder -1 sind sowie X^{-1} die inverse von X.
aus dem zusammehang nehme ich an, daß |X^{-1}d| das maximum der zeilen von |X^{-1}d| sein soll -
kann aber ebensogut auch sein, daß die ungleichung zeileweise verstanden werden soll.
falls es irgendwie hilfreich ist: X:=A'A

wie kommt die abschätzung zustande?

 

[MesH]

Ich würde eher vermuten, dass |X^{-1} d| auch die ||.||_2-Norm sein soll. Deine Bedingung an die Matrix bedeutet insbesondere, dass der kleinste Eigenwert von X >= M ist (Einheitsvektoren für a betrachten), also der größte Eigenwert von X^{-1} <= 1/M.

||X^{-1} d||_2 <= ||X^{-1}||_2 *||d||_2 <= 1/M ||d||_2, weil die ||.||_2 Norm von ner Matrix genau den betragsmässig größten Eigenwert darstellt. Klar soweit? ;P

Kuhle Arbeitszeiten btw

 

[FORYOUITERRA]

die abschätzung ist teil einer anderen abschätzung in welcher die zeilen des betrages X^{-1}d vorkommen. wäre natürlich hervorragend, wenn ich die spektralnorm benutzen könnte.

 

[MesH]

Also kA, ich kenn deine Aufzeichnungen da nun nicht. Aber mir würde alles andere sehr unwahrscheinlich vorkommen. Wenn das im Kontext von irgendwelchen Zeilen-Abschätzungen ist, kommt wohl sonst nur die oo-Norm in Betracht. Aber mit der wirst du die 1/M nicht ins Spiel bringen können (die 2-Norm von d könnte man reinbringen, da ||d||_oo = 1 <= ||d||_2 für deine gegebenen d). Aber Betrag von nem Vektor ist meines Erachtens nur ne (faule) andere Schreibweise für die 2-Norm des Vektors.

 

[FORYOUITERRA]

hab dir mal nen link zu dem paper geschickt.

 

[FORYOUITERRA]

nochmals mein topic hijacken:

wie kommt man auf die ungleichung (bla)?

definition der l1-norm:
||x||_1: = \sum_{i=1}^n |x_i|

 

[FORYOUITERRA]

ich glaube die ungleichung ist falsch. ich komme auf eine abschätzung mit dem faktor 4 statt 2.

 

[MesH]

Mir kam da auch schon was komisch vor. Für nen Beweis könnte man noch sowas wie ||\hat{x}|| >= ||x|| gebrauchen. Konnte mir aber auch kein Gegenbeispiel überlegen und hab dann beschlossen, dass ich was übersehe

 

[DJT]

Hm, irgendwas fehlt da oder irgendeine Ungleichung ist falsch herum. Als Gegenbeispiel muss man ja einfach nur A gleich der leeren Menge setzen und schon steht da, dass die Norm der Differenz beider Vektoren kleiner gleich also gleich Null ist. Was ja nun allgemein nicht stimmen kann ^^