Técnica de rastreamento aleatório

10

Eu conheci a seguinte técnica de rastreamento aleatório em M. Seeger, "Atualizações de baixa classificação para a decomposição de Cholesky", Universidade da Califórnia em Berkeley, Tech. Rep. 2007.

tr(A)=E[xTAx]

onde .xN(0,I)

Como uma pessoa sem profundos conhecimentos de matemática, me pergunto como essa igualdade pode ser alcançada. Além disso, como podemos interpretar , por exemplo, geometricamente? Onde devo procurar para entender o significado de obter o produto interno de um vetor e seu valor de intervalo? Por que a média é igual à soma dos valores próprios? Além da propriedade teórica, qual é a sua importância prática?xTAx

Eu escrevi um trecho de código MATLAB para ver se funciona

#% 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)

O traço é 15, onde a aproximação é 14,9696.

petrichor
fonte

Respostas:

12

NB O resultado declarado não depende de nenhuma suposição de normalidade ou mesmo independência das coordenadas do . Também não depende de ser positivo definido. De fato, suponha apenas que as coordenadas de tenham média zero, variação de uma e não sejam correlacionadas (mas não necessariamente independentes); isto é, , e para todos os .xAxExi=0Exi2=1Exixj=0ij

Abordagem de mãos nuas

Seja uma matriz arbitrária . Por definição . Então, e assim terminamos.A=(aij)n×ntr(A)=i=1naii

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

Caso isso não seja óbvio, observe que o lado direito, por linearidade da expectativa, é

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

Prova através de propriedades de rastreio

Há outra maneira de escrever isso que é sugestivo, mas se baseia conceitualmente em ferramentas um pouco mais avançadas. Precisamos que a expectativa e o operador de rastreamento sejam lineares e que, para quaisquer duas matrizes e de dimensões apropriadas, . Então, como , temos e portanto, ABtr(AB)=tr(BA)xTAx=tr(xTAx)

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

Formas quadráticas, produtos internos e elipsóides

Se for positivo definido, então um produto interno em poderá ser definido por e define um elipsóide em centralizado na origem.ARnx,yA=xTAyEA={x:xTAx=1}Rn

cardeal
fonte
É bastante confuso seguir as variáveis bold e mormalcase . Eu acho que eles são valores escalares. Entendo mais claramente quando começo da forma de expectativa, como você fez na última parte. Então está muito claro para mim agora. xixi
E[(xTAx)]=E[(i=1nj=1naijxixj)]=i=1naiiE[xi2]+ijaijE[xixj]
Petrichor
xi é a ésima coordenada do vetor . Os outros são simplesmente erros de digitação. Me desculpe por isso. Eu estava tentando seguir sua anotação o mais próximo possível. Normalmente, eu usaria com como coordenadas da variável aleatória . Mas eu não queria (potencialmente) confundir. ixX=(Xi)XiX
cardeal
Na verdade, é consistente com a resposta. Eu só queria ter certeza de que as variáveis ​​subscritas são os elementos do vetor. Agora é claro.
Petrichor
Bem, é consistente (agora) porque eu editei! :) Obrigado por apontar os erros de digitação. Vou tentar adicionar um pouco mais sobre a geometria em algum momento nos próximos dias.
cardeal
3

Se é simétrico positivo definido, então com ortonormal e diagonal com autovalores na diagonal. Como possui matriz de covariância de identidade e é ortonormal, também possui matriz de covariância de identidade. Portanto, escrevendo , temos . Como o operador de expectativa é linear, isso é apenas . Cada é qui-quadrado com 1 grau de liberdade, portanto, possui o valor esperado 1. Portanto, a expectativa é a soma dos valores próprios.AA=UtDUUDxUUxy=UxE[xTAx]=E[ytDy]i=0nλiE[yi2]yi

Geometricamente, matrizes definidas positivas simétricas estão em 1-1 correspondência com elipsóides - dada pela equação . Os comprimentos dos eixos do elipsóide são dados por onde são os autovalores.AxTAx=11/λiλi

Quando onde é a matriz de covariância, este é o quadrado da distância de Mahalanobis .A=C1C

aprokopiw
fonte
1

Deixe-me abordar a parte "qual é a sua importância prática" da questão. Há muitas situações em que temos a capacidade de produtos vetor matriz de computação de forma eficiente, mesmo se não temos uma cópia armazenada da matriz ou não tem armazenamento suficiente para guardar uma cópia de . Por exemplo, pode ser do tamanho 100.000 por 100.000 e totalmente denso - seria necessário 80 gigabytes de RAM para armazenar essa matriz no formato de ponto flutuante de dupla precisão. AxAAA

Algoritmos aleatórios como este pode ser utilizado para estimar o rastreio de ou (usando um algoritmo relacionada) diagonais individuais de . AA

Algumas aplicações desta técnica para problemas de inversão geofísica em larga escala são discutidas em

JK MacCarthy, B. Borchers e RC Aster. Estimativa estocástica eficiente da matriz de resolução do modelo na diagonal e validação cruzada generalizada para grandes problemas inversos geofísicos. Journal of Geophysical Research, 116, B10304, 2011. Link para o artigo

Brian Borchers
fonte
+1: Encontrei algoritmos aleatórios neste semestre e fiquei fascinada com eles. Deixe-me adicionar outro bom artigo. Nathan Halko, Per-Gunnar Martinsson, Joel A. Tropp, "Encontrar estrutura com aleatoriedade: algoritmos probabilísticos para a construção de decomposições matriciais aproximados", de 2010, arxiv.org/abs/0909.4061
Petrichor