Sparse Matrix Implementierung des Kalman Filters?

8

Ich habe einen Kalman-Filter-basierten Modellierungscode, den ich für eine regionale ionosphärische Kartierungsanwendung in Echtzeit entwickelt habe. Der Code assimiliert Daten von verschiedenen Sensoren mithilfe eines Kalman-Filters in eine Karte (beschrieben durch eine Reihe von Basisfunktionen).

Ich versuche, dies auf einen größeren Bereich und mehr Sensoren zu skalieren, aber der Matrixalgebra-Teil des Kalman-Filters wird aufgrund der großen Matrizen (Tausende von Zeilen / Spalten) sehr langsam. Ich vermute, der beste Weg, um das Laufzeitproblem anzugreifen, besteht darin, die Tatsache zu nutzen, dass diese Matrizen mit 80% oder mehr der gesamten Elemente Null normalerweise sehr spärlich sind. Der Grund dafür ist, dass jeder Sensor einen Vorspannungsparameter hat, der gemeinsam mit den Kartenkoeffizienten geschätzt wird. Dies wird in der Spalte für diesen Sensor in der Kalman H-Matrix als 1 angezeigt, in den Spalten für jeden anderen Sensor- und Kartenkoeffizienten als Null. Es gibt Hunderte von Sensoren, die jeweils 8-10 Beobachtungen in jeder Epoche liefern, daher viele Nullen.

Ich könnte versuchen, die Komponenten des Kalman-Filters mit spärlichen Algorithmen zu implementieren, insbesondere mit Multiplikation und Inversion *, aber ich frage mich, ob es einen noch besseren Ansatz gibt, der den Kalman-Filter in eine andere Form umwandelt, die für Fälle mit Matrizen besser geeignet ist spärlich? Ich weiß, dass ich einen Ensemble-Kalman-Filter oder ähnliches verwenden könnte, aber wenn möglich möchte ich die Optimalität des reinen linearen Kalman-Filters beibehalten. Das gesamte Datenvolumen ist nicht unerschwinglich, nur die großen, spärlichen Matrizen, die sich aus dem linearen Modell ergeben.

In Bezug auf die Implementierung erfolgt dies in IDL, die Kernmatrixalgebra erfolgt jedoch über Aufrufe externer optimierter LA-Bibliotheken (insbesondere ATLAS).

* Ich weiß, dass eine optimale Kalman-Filterimplementierung eine Inversion vermeidet und stattdessen eine UD-Zerlegung verwendet. Ich denke darüber nach, so etwas zu implementieren, damit das die Antwort sein kann, aber ich bin gespannt, ob es angesichts der spärlichen Matrizen eine bessere Lösung gibt.

Bogdanovist
quelle
1
Ich denke, diese Frage wäre besser, wenn Sie die Mindestmenge an Mathematik einbeziehen würden, um das Problem zu beschreiben. Viele Menschen hier kennen die lineare Algebra, aber nicht den zugrunde liegenden Kalman-Filterprozess. Die Beschreibung der H-Matrix (was auch immer sie sein mag) und der damit verbundenen Gleichungen, die Sie zu lösen versuchen, sollte zu einer besseren Antwort führen.
Bill Barth
Du hast vielleicht recht. Kalman-Filterschemata sind jedoch ein großes Thema für sich. Es wäre zu viel, jemanden zu fragen, um zu erfahren, wie Kalman-Filter aus meiner Frage funktionieren, und daraus eine Antwort zu finden. Dies wäre eine Arbeit auf Forschungspapierebene (ich nehme das sowieso an). Ich denke, jeder, der in der Lage wäre, die Frage zu beantworten, würde keine zusätzlichen Details benötigen.
Bogdanovist

Antworten:

7

Bei dünn besetzten Matrizen ist es häufig der Fall, dass dicht ist , obwohl eine Matrix dünn ist. In solchen Fällen ist die Cholesky- oder Faktorisierung von eher spärlich (insbesondere wenn die Zeilen / Spalten von neu angeordnet werden, um das Sparsity-Muster zu verbessern). In den meisten Fällen, wenn Sie die Sparsity ausnutzen möchten und nicht daran interessiert sind Wenn Sie einen iterativen Algorithmus zum Lösen von Systemen mit , ist es besser, eine Faktorisierung der Matrix zu verwenden, als explizit zu berechnen . A - 1 L U A A A A - 1AA1LUAAAA1

Insbesondere für die Kalman-Filterung und nicht für die Datenverarbeitung

Sk=(HkPk1,kHkT+Rk)1

Normalerweise ist es besser, mit einer Faktorisierung von . Da symmetrisch ist und positiv definitiv sein sollte, können Sie dazu eine Cholesky-Faktorisierung oder eine -Faktorisierung verwenden. Sie haben uns gesagt, dass Ihre -Matrix dünn ist, aber Sie haben uns nichts darüber gesagt, ob dünn oder anderweitig strukturiert ist, und natürlich könnte ziemlich dicht sein. S k L D L T H k R k P.Sk1SkLDLTHkRkP

Ein Grund dafür, dass der Ensemble Kalman Filter (EnKF) und verschiedene Partikelfiltertechniken so beliebt sind, ist, dass für Systeme mit einem extrem großen Zustandsvektor die herkömmliche Kalman-Filterung sehr schwierig wird. EnKF kann für sehr große Zustandsvektoren effizient implementiert werden, wenn diagonal oder nahezu diagonal ist. Diese Fragen wurden von Personen, die auf dem Gebiet der Datenassimilation tätig sind, eingehend behandelt. Ich empfehle daher, Ihre Recherche damit zu beginnen, zu lesen, wie sie mit diesen Problemen umgegangen sind. Rk

Brian Borchers
quelle
Wenn ich Sie wäre, würde ich EnKF nach diesem Problem durchsuchen.
Brian Borchers
2

Wir haben einen robusten Algorithmus für den Ensemble Kalman-Filter (und den regulären Kalman-Filter). Es eignet sich gut für spärliche Matrizen und parallele Berechnungen, da es auf orthogonalen Matrizen basiert und sich auf die Quadratwurzel- oder UD-Algorithmen bezieht.

Würde gerne das Papier schicken

Thomas, SJ, J. Hacker und J. Anderson, (2009): Eine robuste Formulierung des Ensembles Kalman Filter Quart J. Royal Met. Soc, Band 135, 507-521,

(PDF vom Verlag ist kostenlos .)

Stephen Thomas
quelle
2
Hallo Stephen. Vielen Dank, dass Sie sich scicomp angeschlossen haben. Ich verstehe, dass die Frage ziemlich allgemein war, so dass eine spezifische Antwort unmöglich zu geben ist. Aber auch im Hinblick auf den Nutzen anderer Besucher können Sie möglicherweise mehr Informationen darüber geben, was Ihr Algorithmus tatsächlich tut, und einen stabilen Link bereitstellen, z. über das doi zur referenz.
Jan
Nur das Abstract hier zu veröffentlichen, wäre eine gute Möglichkeit, den Link zu den Stack Exchange-Standards zu "erklären".
dmckee --- Ex-Moderator Kätzchen
Obwohl ich Jan zustimme, lesen EEs, die sich mit KFs befassen (wie ich!), Im Allgemeinen keine meteorologischen Veröffentlichungen. Die Tatsache, dass das Papier als Antwort auf ein notorisch subtiles Problem empfohlen wird, ist für mich Motivation genug, es aufzuspüren.
Damien
Das Ensemble Kalman Filter (EnKF) kann im Kontext der linearen Regressionstheorie interpretiert werden. Die Filtergleichungen entsprechen den Normalgleichungen für eine gewichtete Schätzung der kleinsten Quadrate, die eine quadratische Funktion minimiert. Das Lösen der normalen Gleichungen ist numerisch unzuverlässig und unterliegt großen Fehlern, wenn das Problem schlecht konditioniert ist. Es wird ein numerisch zuverlässiger und effizienter Algorithmus vorgestellt, der auf der Minimierung einer alternativen Funktion basiert. Die Methode basiert auf orthogonalen Rotationen, ist sehr parallel und verwendet keine quadratischen Matrizen, um die Analyse-Aktualisierung zu berechnen.
Stephen Thomas
0

Vor langer Zeit hatte ich die Gelegenheit, an der Reduzierung der Dimensionalität zu arbeiten, die sich mit der Verarbeitung von Daten befasst, die in große Mengen fallen. Die Grundidee dahinter ist, dass die Daten in wenigen Schritten verarbeitet werden, um sie so auszurichten, dass die meisten Informationen daraus berechnet werden können.

Es funktioniert auch ziemlich gut für Matrizen und wird weitgehend verwendet. Das Beste daran ist, dass Sie es nicht einmal programmieren müssen, da bereits Standardbibliotheken dafür verfügbar sind. Wichtige mathematische Tools wie Matlab und Mathematica unterstützen diese Funktionalität ebenfalls unkompliziert.

Es gibt zwei Hauptalgorithmen, die dies erreichen - Hauptkomponentenanalyse und Singularwertzerlegung.

Was diese Algorithmen tatsächlich erreichen, ist das Auffinden der Daten, die Ihren Messwert tatsächlich erheblich beeinflussen. Das Internet ist voll von Informationen zu diesen Algorithmen. Dies zeigt Ihnen, wie Apache es macht.

Rorschach
quelle
-1

Wir entschuldigen uns dafür, dass wir die Diskussion für eine Weile nicht erweitert haben - aber ich würde gerne die Zusammenfassung des Papiers veröffentlichen -, gehen aber auch gerne auf die Gründe ein, warum die Berechnungen anders organisiert sind als die Standard-KF von EnKF-Ansätzen

Stephen Thomas
quelle
Die Zusammenfassung ist:
Stephen Thomas
Meinten Sie, dies sei ein Kommentar oder eine Bearbeitung Ihrer anderen Antwort?
Jed Brown