Positive Definitheit des Polynomkerns

11.01.2008, 20:14	Mazze	Auf diesen Beitrag antworten »
Positive Definitheit des Polynomkerns Hallo, ich melde mich auch mal wieder mit einer Frage. Sei im folgenden $\begin{eqnarray} X \subseteq \mathbb{R}^n \end{eqnarray}$ und definiere $\begin{eqnarray} K(x,y) = (1 + x^Ty)^d \\| d \geq 0 \end{eqnarray}$ Weiterhin haben wir die Auswahl von Vektoren $\begin{eqnarray} \{v_1,v_2,...,v_r\} \subset \mathbb{R}^n \end{eqnarray}$ und von Zahlen $\begin{eqnarray} \{c_1,...,c_r\} \subset \mathbb{R} \end{eqnarray}$ Ich möchte nun zeigen das $\begin{eqnarray} \sum_{i=1}^{r}\sum_{j=1}^{r}K(v_i,v_j)c_ic_j \geq 0 \end{eqnarray}$ oder in anderen worten das K ein positiv semidefiniter Kern ist. Ich habe bisher 3 Ansätze verfolgt, vollständige Induktion das Trennen in quadratische Terme (bezüglich i,j , also Terme i = j) und die "gemischten" Terme und einen Weg über Binomialkoeffizient und Multinomialkoeffizient. Aber irgendwie komme ich nicht voran. Eventuel bin ich einfach nur blind oder ist die Aufgabe schwerer als ich dachte? viele Grüße Mazze
11.01.2008, 23:34	Tomtomtomtom	Auf diesen Beitrag antworten »
Ist d aus IR oder aus IN vorausgesetzt?
11.01.2008, 23:41	Mazze	Auf diesen Beitrag antworten »
d ist eine natürliche Zahl, hät ich noch dazu sagen müssen!
11.01.2008, 23:56	Tomtomtomtom	Auf diesen Beitrag antworten »
Dann hab ich mir umsonst den Kopf zerbrochen, gut daß ich nochmal gefragt habe ^^ Eigentlich brauchst du nur zu wissen, daß * die konstante Funktion K(x,y)=c ein positiv semidefiniter Kern ist * die durch ein beliebiges (Semi)Skalarprodukt gegebene Funktionen K(x,y)=<x,y> ein positiv semidefiniter Kern ist (hier halt das gewöhnliche Euklidische Skalarprodukt im IR^n) * positive Linearkombinationen positiv semidefiniter Kerne wieder positiv semidefinite Kerne sind * Produkte positiv semidefiniter Kerne wieder positiv semidefinite Kerne sind ...und das wars auch schon. Ich bin mir grad nciht sicher, eventuell geht das alles sogar noch mit d aus IR. Dann müßte man noch zeigen, daß * (1+<x,y>) unbeschränkt teilbar ist, d.h. für jedes n aus IN existiert ein positiv semidefiniter Kern K mit K^n=(1+<x,y>) (das ist der Punkt wo ich mir unsicher bin) * dadurch gilt das ganze für alle rationalen d * und da der punktweise Limes einer Folge positiv semidefiniter Kerne auch wieder ein positiv semidefiniter Kern ist, auch für alle reellen d. Aber wie gesagt, ohne Gewähr.
12.01.2008, 00:09	Mazze	Auf diesen Beitrag antworten »
Hehe, diese Idee ist mir vor knapp 20 min. auch gekommen, nur muss ich jetzt zeigen das linearkombinationen von positiv definiten Kernen positiv definit (semidefinit sind). Das ganze findet im Rahmen von machine Intelligence statt, und naja, der Prof. ist wohl eher jemand den man in die Ingenieurssparte steckt. Nur ist der Übungsleiter anderer ansicht, ergo wissen wir nichts über Kerne bis auf die Definition der pos. Definitheit Prinzipiell würde es reichen wenn man weiß das das Produkt von 2 pos. semidefiniten Kernen, pos. semidefinit ist, also das $\begin{eqnarray} \sum_{i=1}^{r}\sum_{j=1}^{r}K_1(v_i,v_j)K_2(v_i,v_j)c_ic_j \geq 0 \end{eqnarray}$ Der Beweis davon ist nichtmal schwierig, man kann ja zu jedem reellen c 2 zahlen g h(g) finden so das $\begin{eqnarray} c = gh(g) \end{eqnarray}$ und kann damit bel. die Koeffizienten neu bilden und umsortieren und erhällt $\begin{eqnarray} \sum_{i=1}^{r}\sum_{j=1}^{r}K_1(v_i,v_j)g_ih(g)_1jK_2(v_i,v_j)o_ip(o)_j \end{eqnarray}$ im Falle i = j wäre dann auch $\begin{eqnarray} c_i = g_i = h(g)_i = o_i = p(o)_i \end{eqnarray*}$ Das Problem ist in der Summe steht noch das Produkt, meine Idee war hier das ganze in 2 große Summanden aufzuteilen so das man jeweils die pos. definitheit der einzelnen Kerne ausnutzen kann, daher auch die Zerlegung der c's.
12.01.2008, 00:12	Tomtomtomtom	Auf diesen Beitrag antworten »
Also d aus Q funktioniert nicht mehr, Beispielsweise erhältst du für d=1/3, v_1=2, v_2=-2 eine Matrix mit komplexen Eigenwerten. Das hier: ftp://hacktor.fs.uni-bayreuth.de/pub/skr...ellesLernen.pdf scheint in die Richtung zu gehen und mathematisch einigermaßen sauber zu sein.
Anzeige

12.01.2008, 00:40	Mazze	Auf diesen Beitrag antworten »
Hm ich hab heut ewig rumgesucht, aber Deine Quelle ist im Verhältnis zu dem was Wir haben ein sehr gut. Danke schonmal, ich kümmer mich aber erst morgen drum. gute Nacht
12.01.2008, 11:26	Tomtomtomtom	Auf diesen Beitrag antworten »
Das Skript ist nen Zufallstreffer, mit deinem Them kenne ich mich nicht aus. Ich wollte nur versuchen, dir einen Link zu liefern, in dem der Beweis dafür steht, daß das elementweise Produkt (auch oft als Schurprodukt bezeichnet) nichtnegativ definiter Matrizen wieder nichtnegativ definit ist, ohne selber die ganzen Matrizen texen zu müssen. Und die Google-Suche nach "Schurprodukt definit" liefert genau das verlinkte Skript. Ich komme eigentlich aus einer völlig anderen Richtung auf dieses Thema, nämlich aus der Stochastik. Dort treten solche Kerne bei der Harmonischen Analyse auf R / Fouriertransformation von Maßen auf.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »