Spärliche Walsh-Hadamard-Transformation

Die Walsh-Hadamard-Transformation (WHT) ist eine Verallgemeinerung der Fourier-Transformation und eine orthogonale Transformation eines Vektors mit reellen oder komplexen Zahlen der Dimension . Die Transformation ist im Quantencomputer sehr beliebt, wurde aber kürzlich als eine Art Vorkonditionierer für zufällige Projektionen hochdimensionaler Vektoren für den Beweis des Johnson-Lindenstrauss-Lemmas untersucht. Ihr Hauptmerkmal ist , dass , obwohl es ein Quadrat ist Matrix, kann es zu einem Vektor in der Zeit angewendet werden (eher als ) durch eine FFT-ähnliche Verfahren. $d = 2^m$ $d\times d$ $O(d \log d)$ $d^2$

Angenommen, der Eingabevektor ist spärlich : Er enthält nur wenige Einträge ungleich Null (z. B. ). Gibt es eine Möglichkeit, die WHT in der Zeit so zu berechnen dass und für ? $r \ll d$ $f(r,d)$ $f(d,d) = O(d \log d)$ $f(r,d) = o(d \log d)$ $r = o(d)$

Hinweis: Diese Anforderungen sind nur eine Möglichkeit, die Idee zu formalisieren, dass ich etwas möchte, das schneller als für kleine läuft . $d \log d$ $r$

ds.algorithms linear-algebra Suresh Venkat
quelle

Ich bin mir sicher, dass Sie die folgenden zwei einfachen Beobachtungen kennen, aber ich werde sie trotzdem für andere Leser aufschreiben: (1) Eine einfache Multiplikation ergibt O (rd) Zeit. Es ist nur dann besser als O (d log d), wenn r = o (log d) ist. (2) Auch wenn der Eingabevektor dünn ist, ist die Ausgabe im Allgemeinen nicht dünn. Dies bedeutet, dass wir nicht hoffen können, dass f (r, d) auch für r = 1 o (d) ist.

Tsuyoshi Ito

Wissen Sie, wie die Antwort auf dieselbe Frage für die Fourier-Transformation lautet?

Robin Kothari

Tsuyoshi: Ja, mir ist (1) bewusst, und genau das geschieht für Anwendungen, die dies benötigen. wie für (2) ist das auch wahr. Robin, das ist ein guter Punkt - ich weiß über nichts für die FT Bescheid, und in der Tat könnte dies ein guter Ort sein, um mit dem Graben zu beginnen.

Suresh Venkat

Es stellte sich heraus, dass ich auf Wikipedia hätte graben sollen. Auf der FFT-Seite werden zwei Artikel erwähnt, die möglicherweise mit dem Problem der spärlichen Berechnung zusammenhängen.

Suresh Venkat

Spärliche Walsh-Hadamard-Transformation

Antworten: