Frage:
Wie kann man eine große symmetrische Matrix mit geringer Dichte diagonalisieren, um die Eigenwerte und Eigenvektoren zu erhalten?
Rn2dy
2010-11-28 10:38:03 UTC
view on stackexchange narkive permalink

Die Matrix kann bis zu 2500 $ mal 2500 $ groß sein. Was ist der beste Algorithmus dafür? Gibt es einen Algorithmus, mit dem sich ein Programm leicht schreiben lässt? Gibt es dafür geeignete Pakete?

Vier antworten:
#1
+10
user5012
2011-07-19 17:00:38 UTC
view on stackexchange narkive permalink

In der ersten Tabelle dieses NIPS-Dokuments finden Sie eine Übersicht über Zerlegungsalgorithmen.

Es listet moderne Algorithmen (mit Links zu bekannten Implementierungen) auf, einschließlich der stochastischen Zerlegung von Halko et al., wohl dem Stand der Dinge -art Methode heute.

Sie fragen nach praktischen Programmierpaketen, geben aber nicht die Plattform oder Sprache Ihrer Wahl an. Angenommen, es ist:

  • Python:
    • Verwenden Sie scipy für In-Core-Zerlegungen (Eingabe muss in RAM passen)
    • gensim für spärliche In-Core- und Out-of-Core-Zerlegungen (unterstützt auch inkrementelle Zerlegungsaktualisierungen)
  • Java:
    • Mahout verfügt über mehrere skalierbare Zerlegungsalgen
    • LingPipe (im Kern) unterstützt fehlende Eingabewerte
  • C++
  • redsvd (im Kern) sehr saubere und elegante, effiziente Implementierung
  • MATLAB
    • pca.m von Mark Tygert, einem der Mitautoren der stochastischen Methode.
  • Ihr Problem ist nicht ' Es ist jedoch nicht besonders groß, daher denke ich, dass jedes vorhandene Paket (unter Verwendung des iterativen Lanczos-Algorithmus) gut funktioniert. Eigenzerlegungen gibt es schon seit einiger Zeit.

    Willkommen auf der Seite! Ich bin sicher, dass Sie von dieser Frage genügend Upvotes erhalten, um in Zukunft so viele Links zu veröffentlichen, wie Sie möchten.
    +1 Tolle Antwort: Es bietet viele Lösungen, Links zu allen und einige Ratschläge zu neueren Algorithmen.
    #2
    +6
    NPE
    2010-11-28 18:05:29 UTC
    view on stackexchange narkive permalink

    Sehen Sie sich eine Übersicht über Software für spärliche Eigenwertprobleme von Hernández et al.

    an
    #3
    +5
    Chase
    2010-11-28 11:09:44 UTC
    view on stackexchange narkive permalink

    Ich weiß nicht viel über Eigenwerte oder deren Anwendung, aber R scheint für diesen Zweck eine eingebaute Funktion namens eigen () zu haben. Das Berechnen der Eigenwerte von &-Eigenvektoren für eine 2500 * 2500-Matrix dauerte auf meinem Computer ~ 1 Minute.

      > sampData <-runif (6250000, 0, 2) > x <-Matrix (sampData, ncol = 2500, byrow = TRUE) > system.time (eigen (x)) Benutzersystem abgelaufen 79,74 2,90 65,69  

    Diese Frage wurde auch bei Stapelüberlauf gestellt .

    #4
    +4
    ogrisel
    2010-11-28 22:10:35 UTC
    view on stackexchange narkive permalink

    2500x2500 ist kein so großes Problem. Auch ohne die Sparsamkeit zu nutzen, kann die SVD-Implementierung von scipy.linalg sie in weniger als einer Minute zerlegen. Weitere Informationen finden Sie unter meine Antwort auf verwandte Fragen.

    Bei größeren Problemen müssen Sie die Sparsity explizit verwenden. Das gensim -Projekt hilft Ihnen bei Problemen mittlerer Größe, die auf einen einzelnen Computer passen, aber nicht in den Arbeitsspeicher, und die mahout -Implementierung kann mit spärlichen Matrizen umgehen, die nicht einmal funktionieren auf eine einzelne Festplatte passen.



    Diese Fragen und Antworten wurden automatisch aus der englischen Sprache übersetzt.Der ursprüngliche Inhalt ist auf stackexchange verfügbar. Wir danken ihm für die cc by-sa 2.0-Lizenz, unter der er vertrieben wird.
    Loading...