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 [x^{T} A x]

$\operatorname{tr}(\mathbf{A}) = {E[\mathbf{x}^T \mathbf{A} \mathbf{x}]}$

gdzie . $\mathbf{x} \sim N(\mathbf{0},\mathbf{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? $\mathbf{x}^T \mathbf{A} \mathbf{x}$

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.

normal-distribution matlab

— petrichor
źródło

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 jest pozytywny. Rzeczywiście, załóżmy tylko, że współrzędne mają zerową średnią, wariancję jednego i są nieskorelowane (ale niekoniecznie niezależne); to znaczy, , , i dla wszystkich . $\newcommand{\x}{\mathbf{x}}\newcommand{\e}{\mathbb{E}}\newcommand{\tr}{\mathbf{tr}}\newcommand{\A}{\mathbf{A}}\x$ $\A$ $\x$ $\e \x_i = 0$ $\e \x_i^2 = 1$ $\e \x_i \x_j = 0$ $i \neq j$

Podejście gołymi rękami

Niech będzie dowolną macierzą . Z definicji . Następnie $\A = (a_{ij})$ $n \times n$ $\tr(\A) = \sum_{i=1}^n a_{ii}$ i tak skończyliśmy.

t r (A) = \sum_{i = 1}^{n} a_{i i} = \sum_{i = 1}^{n} a_{i i} E x_{i}^{2} = \sum_{i = 1}^{n} a_{i i} E x_{i}^{2} + \sum_{i \neq j} a_{i j} E x_{i} x_{j},

$\tr(\A) = \sum_{i=1}^n a_{ii} = \sum_{i=1}^n a_{ii} \e \x_i^2 = \sum_{i=1}^n a_{ii} \e \x_i^2 + \sum_{i\neq j} a_{ij} \e \x_i \x_j ,$

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

\sum_{i = 1}^{n} a_{i i} E x_{i}^{2} + \sum_{i \neq j} a_{i j} E x_{i} x_{j} = E (\sum_{i = 1}^{n} \sum_{j = 1}^{n} a_{i j} x_{i} x_{j}) = E (x^{T} A x)

$\sum_{i=1}^n a_{ii} \e \x_i^2 + \sum_{i\neq j} a_{ij} \e \x_i \x_j = \e\Big(\sum_{i=1}^n \sum_{j=1}^n a_{ij} \x_i \x_j \Big) = \e(\x^T \A \x)$

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 o odpowiednich wymiarach . Następnie, ponieważ , mamy $\A$ $\newcommand{\B}{\mathbf{B}}\B$ $\tr(\A\B) = \tr(\B\A)$ $\x^T \A \x = \tr(\x^T \A \x)$ a więc

E (x^{T} A x) = E (t r (x^{T} A x)) = E (t r (A x x^{T})) = t r (E (A x x^{T})) = t r (A E x x^{T}),

$\e(\x^T \A \x) = \e( \tr(\x^T \A \x) ) = \e( \tr(\A \x \x^T) ) = \tr( \e( \A \x \x^T ) ) = \tr( \A \e \x \x^T ),$

E (x^{T} A x) = t r (A I) = t r (A) .

$\e(\x^T \A \x) = \tr(\A \mathbf{I}) = \tr(\A) .$

Kwadratowe formy, produkty wewnętrzne i elipsoidy

Jeśli dodatni określona, wówczas wewnętrzna Produkt może być określona poprzez i określa elipsoidalny wyśrodkowany pochodzenie. $\A$ $\mathbf{R}^n$ $\langle \x, \mathbf{y} \rangle_{\A} = \x^T \A \mathbf{y}$ $\mathcal{E}_{\A} = \{\x: \x^T \A \x = 1\}$ $\mathbf{R}^n$

— kardynał
źródło

x_{i}

$\mathbf{x}_i$

x_{i}

$x_i$

E [(x^{T} A x)] = E [(\sum_{i = 1}^{n} \sum_{j = 1}^{n} a_{i j} x_{i} x_{j})] = \sum_{i = 1}^{n} a_{i i} E [x_{i}^{2}] + \sum_{i \neq j} a_{i j} E [x_{i} x_{j}]

$\newcommand{\x}{\mathbf{x}}\newcommand{\tr}{\operatorname{tr}} {E[(\x^T \mathbf{A} \x)]} = {E[\Big(\sum_{i=1}^n \sum_{j=1}^n a_{ij} x_i x_j \Big)]} = \sum_{i=1}^n a_{ii} {E[x_i^2]} + \sum_{i\neq j} a_{ij} {E[x_i x_j]}$

x_{i}

$\mathbf{x}_i$

i

$i$

x

$\mathbf{x}$

X = (X_{i})

$\mathbf{X} = (X_i)$

X_{i}

$X_i$

X

$\mathbf{X}$

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

$A$ $A = U^tDU$ $U$ $D$ $x$ $U$ $Ux$ $y = Ux$ $E[x^TAx] = E[y^tDy]$ $\sum_{i=0}^n \lambda_i E[y_i^2]$ $y_i$

$A$ $x^TAx = 1$ $1/\sqrt\lambda_i$ $\lambda_i$

$A = C^{-1}$ $C$

— aprokopiw
źródło

1

$Ax$ $A$ $A$ $A$

$A$ $A$

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