Transformation clairsemée de Walsh-Hadamard

La transformée de Walsh-Hadamard (WHT) est une généralisation de la transformée de Fourier, et est une transformation orthogonale sur un vecteur de nombres réels ou complexes de dimension . La transformation est populaire en informatique quantique, mais elle a été étudiée récemment comme une sorte de préconditionneur pour les projections aléatoires de vecteurs de grande dimension à utiliser dans la preuve du lemme de Johnson-Lindenstrauss. Sa principale caractéristique est que bien qu'il s'agisse d'une matrice carrée , elle peut être appliquée à un vecteur dans le temps (plutôt que ) par une méthode de type FFT. $d = 2^m$ $d\times d$ $O(d \log d)$ $d^2$

Supposons que le vecteur d'entrée soit clairsemé : il n'a que quelques entrées non nulles (disons ). Existe-t-il un moyen de calculer le WHT dans le temps tel que et pour ? $r \ll d$ $f(r,d)$ $f(d,d) = O(d \log d)$ $f(r,d) = o(d \log d)$ $r = o(d)$

Remarque: ces exigences ne sont qu'un moyen de formaliser l'idée que j'aimerais quelque chose qui tourne plus vite que pour petit . $d \log d$ $r$

ds.algorithms linear-algebra Suresh Venkat
la source

Je suis sûr que vous êtes au courant des deux observations faciles suivantes, mais de toute façon je les noterai pour d'autres lecteurs: (1) Une multiplication simple donne du temps à O (rd). Il vaut mieux que O (d log d) que lorsque r = o (log d). (2) Même si le vecteur d'entrée est clairsemé, la sortie n'est pas clairsemée en général. Cela signifie que nous ne pouvons pas espérer que f (r, d) soit o (d) même pour r = 1.

Tsuyoshi Ito

Savez-vous quelle est la réponse à la même question pour la transformée de Fourier?

Robin Kothari

Tsuyoshi: oui, je connais (1) et c'est en fait ce qui est fait pour les applications qui en ont besoin. quant à (2) c'est vrai aussi. Robin, c'est un bon point - je ne sais rien pour le FT, et en fait ce pourrait être un bon endroit pour commencer à creuser.

Suresh Venkat

Il s'avère que j'aurais dû creuser sur wikipedia. la page FFT mentionne deux articles qui pourraient être liés au problème de calcul clairsemé.

Suresh Venkat

Réponses:

Indexez les lignes WHT par un entier x, pour . Donc x a des bits de log d. De même, indexez les colonnes. (X, y) est la position où l'exposant est le produit scalaire de journal de longueur d. Supposons que r est une puissance de 2, arrondissant si nécessaire. Divisez la matrice dxr en blocs rxr en laissant varier les premiers bits de log r et en fixant les autres bits de log (d / r) de chacune des manières d / r. Ce bloc rxr est une matrice WHT plus petite de taille r, sauf qu'il peut y avoir des colonnes manquantes, répétées ou annulées. Dans tous les cas, prétraitez facilement le vecteur, puis effectuez un rxr WHT dans le temps r log r, puis répétez d / r fois pour le temps total d log r. $0 \le x \lt d$ $(-1)^{\langle x,y \rangle}$

Exemple:

d = 4.

WHT H est

++++
+-+-
++--
+--+

Un ensemble arbitraire de colonnes est 00 et 10 (le plus à gauche et deux de plus):

++
++
+-
+-

Les blocs de lignes sont

++
++

--
--

$(a,b)^T$ $(a+b,0)^T$

++
+-

$(a,b)^T$ $(-a-b,0)^T$

++
+-

Martin Strauss
la source