Extrahieren der Diagonale einer ungefähr diagonalen Matrix, wenn wir ihre Einträge nicht kennen

8

Was ist ein guter Weg, um die Diagonale aus einer symmetrischen Matrix zu extrahieren, die bereits fast diagonal ist, bei der Sie jedoch keine Matrixelemente haben (nur die Möglichkeit, sie auf Vektoren anzuwenden)?

Weitere Einschränkungen sind: (1) das n-fache Anwenden der n-mal-n-Matrix zum expliziten Konstruieren der Diagonale wäre unerschwinglich kostspielig, und (2) die kleinen Elemente der Diagonale sind zusätzlich zu den großen Elementen wichtig.

Hier ist ein Beispielbild des Matrixtyps, aus dem ich die Diagonale extrahieren möchte (in einem kleinen Testfall):

Geben Sie hier die Bildbeschreibung ein

Nick Alger
quelle

Antworten:

9

Ich werde meine eigene Frage beantworten, da die folgende Methode sehr effektiv zu sein scheint. Ich mache es zu einer Antwort, damit die Leute es unabhängig von der Frage positiv oder negativ bewerten können, wenn sie denken, dass es gut oder schlecht ist.

Antwort: Verwenden Sie eine randomisierte Matrixprüfung, die auf die Diagonale der Matrix angewendet wird.

Sei der Operator, dessen Diagonale wir finden möchten, und sei eine kleine Anzahl von Gaußschen Zufallsvektoren. dann auf die Zufallsvektoren an, um und das folgende Minimierungsproblem der kleinsten Quadrate zu lösen: Aω1,ω2,..,ωkAAω1,Aω2,...,Aωk

mindiagonal D||Dω1Aω1||2+||Dω2Aω2||2+...+||DωkAωk||2.

Das Minimum hat die genaue Formel,

di=ω1iAω11+ω2iAω2i...+ωkiAωki(ω1i)2+(ω2i)2+...+(ωki)2.

Matlab-Code zum Beispiel:

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

In meiner Beispielmatrix mit 3 Abtastvektoren vergleichen sich die exakte Diagonale und die untersuchte Diagonale wie folgt:

[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

Update: Ich habe experimentiert, diese Ideen auf symmetrische Blockmatrizen anzuwenden, da eine Matrix, mit der ich arbeite, fast blockdiagonal in einer Wavelet-ähnlichen Basis ist. Es scheint ziemlich gut für das Erstellen von Vorkonditionierern zu funktionieren, solange die Matrix "blockdiagonal dominant" ist (Definition ist etwas schwierig) und solange Sie die rekonstruierten Blöcke der kleinsten Quadrate symmetrisieren.

Recall , dass eine Matrix in Blöcke partitioniert ist block-diagonal-dominant , wenn Ai,j

||Ai,i1||1j||Ai,j||.

Gegeben Gaußsche Zufall ‚s wie oben, versuchen wir , die folgende Least-Squares - Block diagonal Rekonstruktion zu finden:ω

minblock diagonals B||Bω1Aω1||2+||Bω2Aω2||2+...+||BωkAωk||2.

Nach einigen Tensorproduktmanipulationen können Sie die genaue Formel für den -ten Block indem Sie die lokalen Probleme lösen:lB~(l)

B~(l)=[(Aω1)(l)ω1(l)T+...+(Aωk)(l)ωk(l)T][ω1(l)ω1(l)T+...+ωk(l)ωk(l)T]1,

wobei und die Teile von und , die den Indizes des -ten Blocks entsprechen. ω ( l ) i A ω i ω i l(Aωi)(l)ωi(l)Aωiωil

Wenn ich nur diese , scheint die Vorkonditionierung ziemlich schlecht zu sein, aber wenn ich wie folgt symmetriere,B~

B(l)=(B~(l)+B~(l)T)/2,

In meinen Experimenten wird es fast so gut, als hätte ich die wahren Diagonalblöcke verwendet (oft besser!). Hier ist eine Beispielmatrix in Bildern, Geben Sie hier die Bildbeschreibung ein

Nick Alger
quelle
3
Zögern Sie nicht, Ihre eigene Frage zu beantworten. Dies ist genau das, was wir auf SciComp wollen (ich habe es getan). Möglicherweise möchten Sie warten, bis Sie Ihre eigene Antwort akzeptiert haben, falls eine bessere Antwort angezeigt wird. Es ist viel besser, Ihre eigene Frage zu beantworten (wenn Sie eine Antwort haben), als sie unbeantwortet zu lassen. Wir empfehlen allen Benutzern, wenn möglich Ihrem Beispiel zu folgen.
Geoff Oxberry
Ok, ich bin froh das zu hören! Ich werde ein paar Tage auf die Annahme warten, falls jemand eine bessere Antwort hat.
Nick Alger