Rzadka transformacja Walsha-Hadamarda

Walsh-Hadamard'a transformacji (BLK) jest uogólnieniem transformaty Fouriera i jest prostopadła do przetwarzania na wektorze rzeczywistych lub liczb zespolonych o wymiarze . Transformacja jest popularna w obliczeniach kwantowych, ale ostatnio badano ją jako rodzaj warunku wstępnego losowych rzutów wektorów wielowymiarowych do wykorzystania w dowodzie lematu Johnsona-Lindenstraussa. Jego główną cechą jest to, że mimo iż jest to kwadrat matryca, może być zastosowany do wektora w czasie (a nie ) za pomocą FFT, takich jak metody. $d = 2^m$ $d\times d$ $O(d \log d)$ $d^2$

Załóżmy, że wektor wejściowy jest rzadki : ma tylko kilka niezerowych pozycji (powiedzmy ). Jest jakiś sposób obliczyć WHT w czasie , tak że i dla ? $r \ll d$ $f(r,d)$ $f(d,d) = O(d \log d)$ $f(r,d) = o(d \log d)$ $r = o(d)$

Uwaga: te wymagania są tylko jednym ze sposobów sformalizowania idei, że chciałbym, aby coś działało szybciej niż dla małego . $d \log d$ $r$

ds.algorithms linear-algebra Suresh Venkat
źródło

Jestem pewien, że zdajesz sobie sprawę z następujących dwóch łatwych spostrzeżeń, ale i tak zapiszę je dla innych czytelników: (1) Bezpośrednie pomnożenie daje O (rd) czas. Jest lepszy niż O (d log d) tylko wtedy, gdy r = o (log d). (2) Nawet jeśli wektor wejściowy jest rzadki, wynik ogólnie nie jest rzadki. Oznacza to, że nie możemy mieć nadziei, że f (r, d) będzie o (d) nawet dla r = 1.

Tsuyoshi Ito

Czy wiesz, jaka jest odpowiedź na to samo pytanie dla transformacji Fouriera?

Robin Kothari,

Tsuyoshi: tak, jestem świadomy (1) i tak właśnie się dzieje z aplikacjami, które tego potrzebują. co do (2), to także prawda. Robin, to dobra uwaga - nie wiem nic o FT, a właściwie może to być dobre miejsce do rozpoczęcia kopania.

Suresh Venkat

Okazuje się, że powinienem był kopać na wikipedii. strona FFT wymienia dwa artykuły, które mogą być związane z rzadkim problemem obliczeniowym.

Suresh Venkat,

Odpowiedzi:

Indeksuj wiersze WHT według liczby całkowitej x, dla . Więc x ma log d bitów. Podobnie indeksuj kolumny. (X, Y), sytuacja jest gdzie wykładnik jest kropka produkt log długość d. Załóżmy, że r jest potęgą 2, w razie potrzeby zaokrąglając w górę. Podziel macierz dxr na bloki rxr, pozwalając, aby pierwsze bity logarytmiczne r się zmieniały, i ustalając inne bity log (d / r) na każdy ze sposobów d / r. Ten blok rxr jest mniejszą macierzą WHT o rozmiarze r, z tym wyjątkiem, że niektórych kolumn brakuje, powtarzano lub negowano. W każdym razie należy łatwo wstępnie przetworzyć wektor, a następnie wykonać WHT rxr w czasie r log r, a następnie powtórzyć czasy d / r dla całkowitego czasu d log r. $0 \le x \lt d$ $(-1)^{\langle x,y \rangle}$

Przykład:

d = 4.

WHT H jest

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

Arbitralny zestaw kolumn to 00 i 10 (skrajnie lewy i dwa od tego):

++
++
+-
+-

Bloki wierszy są

++
++

--
--

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

++
+-

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

++
+-

Martin Strauss
źródło