Technika śledzenia losowego

10

W M. Seeger poznałem następującą losową technikę śledzenia: „Niski poziom aktualizacji rozkładu Choleskiego”, University of California w Berkeley, Tech. Rep, 2007.

tr(A)=E[xTAx]

gdzie .xN(0,I)

Jako osoba bez głębokiego doświadczenia matematycznego zastanawiam się, w jaki sposób można osiągnąć tę równość. Co więcej, jak możemy interpretować , na przykład geometrycznie? Gdzie powinienem szukać, aby zrozumieć znaczenie wzięcia iloczynu wewnętrznego wektora i jego wartości zakresu? Dlaczego średnia jest równa sumie wartości własnych? Jakie są praktyczne znaczenie, oprócz własności teoretycznej?xTAx

Napisałem fragment kodu MATLAB, aby zobaczyć, czy to działa

#% tr(A) == E[x'Ax], x ~ N(0,I)

N = 100000;
n = 3;
x = randn([n N]); % samples
A = magic(n); % any n by n matrix A

y = zeros(1, N);
for i = 1:N
    y(i) = x(:,i)' * A * x(:,i);
end
mean(y)
trace(A)

Ślad wynosi 15, a przybliżenie wynosi 14,9696.

petrichor
źródło

Odpowiedzi:

12

Uwaga: Podany wynik nie zależy od jakiegokolwiek założenia normalności, a nawet niezależności współrzędnych . Nie zależy to również od tego, czy A jest pozytywny. Rzeczywiście, załóżmy tylko, że współrzędne x mają zerową średnią, wariancję jednego i są nieskorelowane (ale niekoniecznie niezależne); to znaczy, E x i = 0 , E x 2 i = 1 , i E x i x j = 0 dla wszystkich i j .xAxExi=0Exi2=1Exixj=0ij

Podejście gołymi rękami

Niech będzie dowolną macierzą n × n . Z definicji t r ( A ) = n i = 1 a i i . Następnie t r ( A ) = n i = 1 a i i = n i = 1 a i i E x 2 i = n A=(aij)n×ntr(A)=i=1naii i tak skończyliśmy.

tr(A)=i=1naii=i=1naiiExi2=i=1naiiExi2+ijaijExixj,

W przypadku, gdy nie jest to całkiem oczywiste, należy zauważyć, że po prawej stronie, według liniowości oczekiwań, jest

i=1naiiExi2+ijaijExixj=E(i=1nj=1naijxixj)=E(xTAx)

Dowód za pomocą właściwości śledzenia

Jest inny sposób na napisanie tego, co jest sugestywne, ale opiera się koncepcyjnie na nieco bardziej zaawansowanych narzędziach. Potrzebujemy, aby zarówno oczekiwanie, jak i operator śledzenia były liniowe oraz, że dla dowolnych dwóch macierzy i B o odpowiednich wymiarach t r ( A B ) = t r ( B A ) . Następnie, ponieważ x T A x = t r ( x T A x ) , mamy E ( x T A x ) = EABtr(AB)=tr(BA)xTAx=tr(xTAx) a więc E ( x T A x ) = t r ( A I )

E(xTAx)=E(tr(xTAx))=E(tr(AxxT))=tr(E(AxxT))=tr(AExxT),
E(xTAx)=tr(AI)=tr(A).

Kwadratowe formy, produkty wewnętrzne i elipsoidy

Jeśli dodatni określona, wówczas wewnętrzna Produkt R n może być określona poprzez x , y = x T r i e = { x : x T x = 1 } określa elipsoidalny R n wyśrodkowany pochodzenie.ARnx,yA=xTAyEA={x:xTAx=1}Rn

kardynał
źródło
xixi
E[(xTAx)]=E[(i=1nj=1naijxixj)]=i=1naiiE[xi2]+ijaijE[xixj]
xiixX=(Xi)XiX
Właściwie jest to zgodne z odpowiedzią. Chciałem tylko upewnić się, że zmienne w indeksie są elementami wektora. Teraz to jasne.
petrichor
Cóż, jest spójny (teraz), ponieważ go edytowałem! :) Dzięki za wskazanie literówek. W ciągu kilku dni postaram się dodać trochę więcej o geometrii.
kardynał
3

AA=UtDUUDxUUxy=UxE[xTAx]=E[ytDy]i=0nλiE[yi2]yi

AxTAx=11/λiλi

A=C1C

aprokopiw
źródło
1

AxAAA

AA

Niektóre zastosowania tej techniki do problemów inwersji geofizycznej na dużą skalę omówiono w

JK MacCarthy, B. Borchers i RC Aster. Skuteczne oszacowanie stochastyczne diagonalnej matrycy rozdzielczości modelu i uogólniona walidacja krzyżowa dla dużych problemów odwrotnych geofizycznych. Journal of Geophysical Research, 116, B10304, 2011. Link do artykułu

Brian Borchers
źródło
+1 W tym semestrze spotkałem się z losowymi algorytmami i fascynowałem się nimi. Pozwól mi dodać kolejny fajny artykuł. Nathan Halko, Per-Gunnar Martinsson, Joel A. Tropp "Znalezienie struktura z przypadkowości: probabilistyczne algorytmy dla konstruowania przybliżone rozkład macierzy", 2010, arxiv.org/abs/0909.4061
Petrichor