Ungefähres Spektrum einer großen Matrix

14

Ich möchte das Spektrum ( alle Eigenwerte) einer großen spärlichen Matrix (Hunderttausende von Zeilen) berechnen. Das ist schwer.

Ich bin bereit, mich mit einer Annäherung zufrieden zu geben. Gibt es dazu Näherungsmethoden?

Während ich auf eine allgemeine Antwort auf diese Frage hoffe, würde ich mich auch über eine Antwort im folgenden speziellen Fall freuen. Meine Matrix ist ein normalisierter Laplace-Wert eines großen Graphen. Die Eigenwerte liegen zwischen 0 und 2, wobei sich eine große Anzahl um 1 gruppiert.

MRocklin
quelle
Ist die Matrix dünn oder dicht?
Aron Ahmadia
Die Matrix ist dünn. Ich habe die Frage bearbeitet, um dies widerzuspiegeln.
MRocklin
Warum willst du alle Eigenwerte? Dies ist im Allgemeinen eine schlechte Sache, wenn Sie über eine dünne oder strukturierte Matrix verfügen. Daher ist es wichtig zu wissen, wie Sie sie verwenden möchten.
Jed Brown
Das Spektrum eines Laplace-Diagramms enthält einige wichtige Informationen, die ich untersuchen möchte. Ich brauche sie nicht alle, ich muss nur ungefähr wissen, wo sie sind.
MRocklin

Antworten:

15

Wenn Ihr Graph ungerichtet ist (wie ich vermute), ist die Matrix symmetrisch und Sie können nichts besseres tun als den Lanczsos-Algorithmus (mit selektiver Reorthogonalisierung, falls dies aus Stabilitätsgründen erforderlich ist). Da das gesamte Spektrum aus 100000 Zahlen besteht, interessiert Sie vor allem die spektrale Dichte.

Um eine ungefähre spektrale Dichte zu erhalten, nehmen Sie das Spektrum des führenden Krylov-Unterraums der Dimension 100 oder so und ersetzen Sie dessen diskrete Dichte durch eine geglättete Version.

Das führende Krylov-Spektrum hat nahezu aufgelöste, gut isolierte Eigenwerte (falls vorhanden), nähert sich den Eigenwerten am Ende des nicht isolierten Spektrums an und ist dazwischen etwas zufällig mit einer Verteilung, deren kumulative Verteilungsfunktion der des wahren Spektrums ähnelt . Es würde in exakter Arithmetik dazu konvergieren, wenn die Dimension wächst. (Wenn Ihr Operator unendlich dimensional wäre, wäre dies immer noch der Fall und Sie würden das Integral der wahren spektralen Dichtefunktion für das kontinuierliche Spektrum erhalten.)

Arnold Neumaier
quelle
Ist das Spektrum des führenden Krylov-Subraums nicht einfach die 100 größten Eigenwerte? Mich interessiert auch die Verteilung der moderaten und kleinsten Eigenwerte.
MRocklin
1
@ Mrocklin: Nein. Ich habe meine Antwort erweitert, um mehr Details zu geben.
Arnold Neumaier
4

Wenn es Ihnen recht ist, über Dinge nachzudenken, die keine Eigenwerte, sondern Funktionen sind, die Ihnen in gewisser Weise noch etwas über das Spektrum erzählen, sollten Sie sich einige Arbeiten von Mark Embree von der Rice University ansehen.

Wolfgang Bangerth
quelle
2

Hier ist noch eine andere Möglichkeit, das Spektrum zu charakterisieren.

Avk=λkvkA

S(ω)=kπ1σσ2+(λkω)2=σπTr[σ2+(ωA)2]1
S(ω)=σπzT[σ2+(ωA)2]1z
z+11σω[σ2+(ωA)2]1z can be computed for example with the conjugate gradient method, or sparse LU on [ω+iσA]1[ωiσA]1 to minimize fill-in. This allows estimation of S(ω) also for large matrices. In practice, it seems the CG solution doesn't need to be very accurate, and neither are many vectors necessary in computing the average. This may depend on the problem.

The above appears to weigh parts of the spectrum more evenly than a similarly smeared Krylov spectral density --- try diag(linspace(0, 1, 150000)) --- although maybe there is a way to correct for this?. This is somewhat similar to the pseudospectral approach, but the result indicates the (smeared) number of eigenvalues in the vicinity to point ω, rather than the inverse distance to the nearest eigenvalue.

EDIT: A better performing alternative for computing the above quantity is to compute Chebyshev moments (via similar stochastic evaluation as above) and then reconstruct the spectral density from them. This requires neither matrix inversions nor separate computations for each ω. See http://theorie2.physik.uni-greifswald.de/downloads/publications/LNP_chapter19.pdf and references therein.

pv.
quelle
0

Siehe die Veröffentlichung "On Sampling-based Approximate Spectral Decomposition" von Sanjiv Kumar, Mehryar Mohri und Ameet Talwalkar (ICML 2009.). Es verwendet Stichproben von Spalten Ihrer Matrix.

Da Ihre Matrix symmetrisch ist, sollten Sie Folgendes tun:

Sei A Ihre n * n Matrix. Sie möchten die Berechnung der Eigenwerte einer n * n-Matrix auf die Berechnung der Eigenwerte einer k * k-Matrix reduzieren. Wählen Sie zuerst Ihren Wert von k. Angenommen, Sie wählen k = 500, da Sie die Eigenwerte einer 500 * 500-Matrix leicht berechnen können. Wählen Sie dann zufällig k Spalten der Matrix A aus. Konstruieren Sie die Matrix B, die nur diese Spalten enthält, und die entsprechenden Zeilen.

B = A (x, x) für eine zufällige Menge von k Indizes x

B ist jetzt ak * k Matrix. Berechnen Sie die Eigenwerte von B und multiplizieren Sie sie mit (n / k). Sie haben jetzt k Werte, die ungefähr wie die n Eigenwerte von A verteilt sind. Beachten Sie, dass Sie nur k Werte erhalten, nicht n, aber ihre Verteilung ist korrekt (bis auf die Tatsache, dass es sich um eine Näherung handelt).

Jérôme Kunegis
quelle
-1

Sie können immer die Gershgorin-Kreissatzgrenzen verwenden, um die Eigenwerte anzunähern .

Wenn die nicht diagonalen Terme klein sind, ist die Diagonale selbst eine gute Annäherung an das Spektrum. Andernfalls könnten Sie versuchen, die diagonalen Einträge in diesem System auszudrücken, wenn Sie eine Annäherung des Eigenraums erhalten (mit anderen Methoden). Dies führt zu einer Matrix mit kleineren Gliedern außerhalb der Diagonale, und die neue Diagonale ist eine bessere Annäherung an das Spektrum.

FKaria
quelle
Gerschgoring gibt keine Schätzungen, sondern Fehlergrenzen an, ist also hier irrelevant. Darüber hinaus würde die Verwendung Ihrer Methode auf einer dünnen Matrix eine dichte Eigenvektormatrix erfordern, die für das OPs-Problem nicht gespeichert werden kann.
Arnold Neumaier
Wie ich bereits sagte, ist die Diagonale selbst eine Annäherung des Spektrums an die Fehlergrenzen, die durch den Gershgorin-Kreissatz gegeben sind. Natürlich sind Gershgorin-Fehlergrenzen keine Annäherungen. Die Diagonale ist eine gute Annäherung, wenn die Terme außerhalb der Diagonale klein sind, was meiner Meinung nach der Fall ist, da OP sagte, dass die Matrix dünn ist.
FKaria
5
Die meisten in der Praxis auftretenden spärlichen Matrizen haben einige signifikante nicht diagonale Elemente in jeder Zeile und Spalte, was die Diagonalen zu sehr schlechten Approximationen macht (z. B. ist die Diagonale für einen Laplace eines regulären Graphen konstant), und die Fehlergrenzen sind unbrauchbar.
Arnold Neumaier