Transformação escassa de Walsh-Hadamard

15

A transformada de Walsh-Hadamard (WHT) é uma generalização da transformada de Fourier e é uma transformação ortogonal em um vetor de números reais ou complexos de dimensão . A transformação é popular na computação quântica, mas foi estudada recentemente como uma espécie de pré-condicionador para projeções aleatórias de vetores de alta dimensão para uso na prova do Lema Johnson-Lindenstrauss. Sua principal característica é que, embora seja uma matriz quadrada , ela pode ser aplicada a um vetor no tempo (em vez de ) por um método semelhante à FFT.d=2md×dO(dregistrod)d2

Suponha que o vetor de entrada seja escasso : ele possui apenas algumas entradas diferentes de zero (digamos ). Existe alguma maneira para calcular a WHT em tempo de modo a que e para ?rdf(r,d)f(d,d)=O(dregistrod)f(r,d)=o(dregistrod)r=o(d)

Nota: esses requisitos são apenas uma maneira de formalizar a ideia de que eu gostaria de algo que seja executado mais rapidamente que para pequeno .dregistrodr

Suresh Venkat
fonte
Estou certo de que você está ciente das duas observações fáceis a seguir, mas, de qualquer forma, as anotarei para outros leitores: (1) Uma multiplicação direta fornece tempo O (r). É melhor que O (d log d) somente quando r = o (log d). (2) Mesmo que o vetor de entrada seja esparso, a saída não é esparsa em geral. Isso significa que não podemos esperar que f (r, d) seja o (d) mesmo para r = 1.
Tsuyoshi Ito
4
Você sabe qual é a resposta para a mesma pergunta para a transformação de Fourier?
Robin Kothari
Tsuyoshi: Sim, eu conheço (1) e é isso que é feito para aplicativos que precisam disso. quanto a (2) isso também é verdade. Robin, esse é um bom argumento - não sei nada sobre o FT e, de fato, pode ser um bom lugar para começar a cavar.
Suresh Venkat
Acontece que eu deveria estar procurando na wikipedia. a página da FFT menciona dois artigos que podem estar relacionados ao problema de computação esparsa.
Suresh Venkat

Respostas:

6

0 0x<d(-1 1)x,y

Exemplo:

d = 4.

WHT H é

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

O conjunto arbitrário de colunas é 00 e 10 (mais à esquerda e duas a mais):

++
++
+-
+-

Blocos de linha são

++
++

e

--
--

(uma,b)T(uma+b,0 0)T

++
+-

(uma,b)T(-uma-b,0 0)T

++
+-
Martin Strauss
fonte