Extraindo a diagonal de uma matriz aproximadamente diagonal quando não sabemos suas entradas

Qual é uma boa maneira de extrair a diagonal de uma matriz simétrica que já é quase diagonal, mas onde você não possui os elementos da matriz (apenas a capacidade de aplicá-la a vetores)?

Outras restrições são: (1) aplicar a matriz n-por-n n-vezes para construir explicitamente a diagonal seria proibitivamente caro e (2) os pequenos elementos da diagonal são importantes além dos grandes.

Aqui está uma imagem de exemplo do tipo de matriz da qual desejo extrair a diagonal (em um caso de teste em pequena escala):

Vou responder minha própria pergunta, pois o método a seguir parece ser muito eficaz. Estou fazendo uma resposta para que as pessoas possam votar de forma positiva ou negativa, independentemente da pergunta, se acham que é bom ou ruim.

Resposta: use a sondagem aleatória da matriz aplicada à diagonal da matriz.

ω 1 , Q 2 , . . , Ω $A$$\omega_1,\omega_2,..,\omega_k$$A$$A \omega_1, A \omega_2, ..., A \omega_k$

$$\min_{\text{diagonal }D} ||D \omega_1-A\omega_1||^2 + ||D \omega_2-A\omega_2||^2 + ... + ||D \omega_k-A\omega_k||^2.$$

O mínimo tem a fórmula exata,

$$d_i=\frac{\omega_1^i A \omega_1^1 + \omega_2^i A \omega_2^i... + \omega_k^i A \omega_k^i}{(\omega_1^i)^2 + (\omega_2^i)^2 + ... + (\omega_k^i)^2}.$$

Código Matlab, por exemplo:

omegas = randn(16,3); 
dprobe=sum(omegas.*(A*omegas),2)./sum(omegas.^2,2);

Na minha matriz de exemplo, com 3 vetores de sondagem, a diagonal exata e a diagonal sondada são comparadas da seguinte forma:

[dprobe, diag(A)]

ans =

1.0e+04 *

2.3297    2.4985
0.4596    0.4921
0.1322    0.0897
0.2838    0.1764
0.0989    0.0999
0.0106    0.0071
0.0068    0.0068
0.0469    0.0571
0.0070    0.0070
0.0355    0.0372
0.0059    0.0060
0.0071    0.0064
0.0067    0.0067
0.0026    0.0021
0.0012    0.0012
0.0015    0.0013

---

Atualização: Eu tenho experimentado aplicar essas idéias a matrizes de bloco simétricas, pois uma matriz com a qual estou trabalhando é quase diagonal de bloco em uma base semelhante a uma wavelet. Parece funcionar muito bem para a construção de pré-condicionadores, desde que a matriz seja "dominante na diagonal do bloco" (a definição é um pouco complicada), e desde que você simetrize os blocos reconstruídos dos mínimos quadrados.

Lembre-se de que uma matriz particionada nos blocos é dominante na diagonal do bloco se $A_{i,j}$

$$||A_{i,i}^{-1}||^{-1} \ge \sum_j ||A_{i,j}||.$$

Dados os aleatórios gaussianos como acima, procuramos encontrar a seguinte reconstrução diagonal do bloco dos mínimos quadrados:$\omega$

$$\min_{\mathrm{block~diagonals~}B} ||B \omega_1-A\omega_1||^2 + ||B \omega_2-A\omega_2||^2 + ... + ||B \omega_k-A\omega_k||^2.$$

Após algumas manipulações de produto tensorial, você pode encontrar a fórmula exata para o 'ésimo bloco , resolvendo os problemas locais:$l$$\tilde{B}^{(l)}$

$$\tilde{B}^{(l)} = [(A\omega_1)^{(l)}\omega_1^{(l)T} + ... + (A\omega_k)^{(l)}\omega_k^{(l)T}][\omega_1^{(l)}\omega_1^{(l)T} + ... + \omega_k^{(l)}\omega_k^{(l)T}]^{-1},$$

onde e são as partes de e correspondentes aos índices do 'ésimo bloco. ω ( l ) i A ω i ω i$(A\omega_i)^{(l)}$$\omega_i^{(l)}$$A\omega_i$$\omega_i$$l$

Se eu apenas usar esses , o pré-condicionamento parecerá muito ruim, mas se eu simetrizar da seguinte maneira,$\tilde{B}$

$$B^{(l)} = (\tilde{B}^{(l)} + \tilde{B}^{(l)T})/2,$$

nas minhas experiências, torna-se quase tão bom quanto se eu tivesse usado os verdadeiros blocos diagonais (geralmente melhores!). Aqui está um exemplo de matriz em imagens,