Transformación escasa de Walsh-Hadamard

La transformación de Walsh-Hadamard (WHT) es una generalización de la transformación de Fourier, y es una transformación ortogonal en un vector de números reales o complejos de dimensión . La transformación es popular en la computación cuántica, pero se ha estudiado recientemente como una especie de preacondicionador para proyecciones aleatorias de vectores de alta dimensión para usar en la prueba del Lema de Johnson-Lindenstrauss. Su característica principal es que, aunque es una matriz cuadrada , se puede aplicar a un vector en el tiempo (en lugar de ) mediante un método similar a FFT. $d = 2^m$ $d\times d$ $O(d \log d)$ $d^2$

Supongamos que el vector de entrada es escaso : solo tiene unas pocas entradas distintas de cero (por ejemplo, ). ¿Hay alguna manera para calcular la WHT en el tiempo tal que y para ? $r \ll d$ $f(r,d)$ $f(d,d) = O(d \log d)$ $f(r,d) = o(d \log d)$ $r = o(d)$

Nota: estos requisitos son simplemente una forma de formalizar la idea de que me gustaría algo que se ejecute más rápido que para pequeño . $d \log d$ $r$

ds.algorithms linear-algebra Suresh Venkat
fuente

Estoy seguro de que conoce las siguientes dos observaciones fáciles, pero de todos modos las escribiré para otros lectores: (1) Una multiplicación directa da tiempo a O (rd). Es mejor que O (d log d) solo cuando r = o (log d). (2) Incluso si el vector de entrada es escaso, la salida no es escasa en general. Esto significa que no podemos esperar que f (r, d) sea o (d) incluso para r = 1.

Tsuyoshi Ito

¿Sabes cuál es la respuesta para la misma pregunta para la transformada de Fourier?

Robin Kothari

Tsuyoshi: sí, soy consciente de (1) y de hecho eso es lo que se hace para las aplicaciones que lo necesitan. en cuanto a (2) eso también es cierto. Robin, ese es un buen punto: no sé nada sobre el FT, y de hecho ese podría ser un buen lugar para comenzar a cavar.

Suresh Venkat

Resulta que debería haber estado cavando en wikipedia. La página FFT menciona dos documentos que podrían estar relacionados con el escaso problema de cálculo.

Suresh Venkat

Respuestas:

Indice las filas WHT por un entero x, para . Entonces x tiene log d bits. Del mismo modo, indexe las columnas. La posición (x, y) es donde el exponente es el producto escalar del registro de longitud d. Suponga que r es una potencia de 2, redondeando si es necesario. Divida la matriz dxr en bloques rxr dejando que varíen los primeros bits log r y arreglando los otros bits log (d / r) en cada una de las formas d / r. Este bloque rxr es una matriz WHT más pequeña de tamaño r, excepto que pueden faltar algunas columnas, repetirse o negarse. En cualquier caso, preprocese el vector fácilmente y luego realice un rxr WHT en el tiempo r log r, luego repita d / r veces para el tiempo total d log r. $0 \le x \lt d$ $(-1)^{\langle x,y \rangle}$

Ejemplo:

d = 4.

WHT H es

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

El conjunto arbitrario de columnas es 00 y 10 (más a la izquierda y dos más de eso):

++
++
+-
+-

Los bloques de fila son

++
++

--
--

En cada bloque, hay columnas repetidas, columnas faltantes y, en el segundo bloque, columnas negadas. Preprocesar un vector en y multiplicar por 2x2 WHT: $(a,b)^T$ $(a+b,0)^T$

++
+-

Luego preprocese en y multiplique por 2x2 WHT: $(a,b)^T$ $(-a-b,0)^T$

++
+-

Martin Strauss
fuente