Transformada de Fourier dispersa

La transformada de Fourier dispersa ( SFT ) es un tipo de transformada discreta de Fourier (DFT) para el procesamiento de señales de big data . Específicamente, se utiliza en la sincronización GPS , la detección de espectro y los convertidores analógico-digitales .: ^{[ 1 ]}

La transformada rápida de Fourier (FFT) desempeña un papel indispensable en muchos campos científicos, especialmente en el procesamiento de señales. Es uno de los diez algoritmos más importantes del siglo XX. ^{[ 2 ]} Sin embargo, con la llegada de la era del big data, la FFT aún necesita mejoras para ahorrar más potencia de cálculo. Recientemente, la transformada dispersa de Fourier (SFT) ha captado una atención considerable, ya que funciona bien en el análisis de largas secuencias de datos con pocos componentes de señal.

Consideremos una secuencia x _n de números complejos . Mediante series de Fourier , x _n se puede escribir como

${\displaystyle x_{n}=(F^{*}X)_{n}=\sum _{k=0}^{N-1}X_{k}e^{j{\frac {2\pi }{N}}kn}.}$

De manera similar, X _k puede representarse como

${\displaystyle X_{k}={\frac {1}{N}}(Fx)_{k}={\frac {1}{N}}\sum _{n=0}^{N-1}x_{n}e^{-j{\frac {2\pi }{N}}kn}.}$

Por lo tanto, a partir de las ecuaciones anteriores, el mapeo es${\displaystyle F:\mathbb {C} ^{N}\to \mathbb {C} ^{N}}$.

Recuperación de frecuencia única

Supongamos que solo existe una frecuencia en la secuencia. Para recuperar esta frecuencia, es razonable utilizar la relación entre puntos adyacentes de la secuencia.

Codificación de fase

La fase k se puede obtener dividiendo los puntos adyacentes de la secuencia. En otras palabras,

${\displaystyle {\frac {x_{n+1}}{x_{n}}}=e^{j{\frac {2\pi }{N}}k}=\cos \left({\frac {2\pi k}{N}}\right)+j\sin \left({\frac {2\pi k}{N}}\right).}$

Observa que${\displaystyle x_{n}\in \mathbb {C} ^{N}}$.

Una búsqueda basada en alias

La búsqueda de la fase k se puede realizar mediante el teorema chino del resto (CRT). ^{[ 3 ]}

Llevar${\displaystyle k=104{,}134}$Por ejemplo, ahora tenemos tres números enteros primos entre sí: 100, 101 y 103. Por lo tanto, la ecuación se puede describir como:

${\displaystyle k=104{,}134\equiv \left\{{\begin{array}{rl}34&{\bmod {1}}00,\\3&{\bmod {1}}01,\\1&{\bmod {1}}03.\end{array}}\right.}$

Por CRT, tenemos

${\displaystyle k=104{,}134{\bmod {(}}100\cdot 101\cdot 103)=104{,}134{\bmod {1}}{,}040{,}300}$

Agrupación aleatoria de frecuencias

Ahora, deseamos explorar el caso de múltiples frecuencias, en lugar de una sola. Las frecuencias adyacentes se pueden separar mediante las propiedades de escala c y modulación b . Es decir, al elegir aleatoriamente los parámetros c y b , la distribución de todas las frecuencias puede ser casi uniforme. La figura muestra que, al agrupar aleatoriamente las frecuencias, podemos utilizar la recuperación de frecuencia única para buscar los componentes principales.

${\displaystyle x_{n}'=X_{k}e^{j{\frac {2\pi }{N}}(c\cdot k+b)},}$

donde c es la propiedad de escala y b es la propiedad de modulación.

Al elegir aleatoriamente c y b , todo el espectro puede parecer una distribución uniforme . Luego, al tomarlos en bancos de filtros se pueden separar todas las frecuencias, incluidas las gaussianas, ^{[ 4 ]} funciones indicadoras, ^{[ 5 ] [ 6 ]} trenes de picos, ^{[ 7 ] [ 8 ] [ 9 ] [ 10 ]} y filtros de Dolph-Chebyshev. ^{[ 11 ]} Cada banco contiene solo una única frecuencia.

Generalmente, todos los SFT siguen las tres etapas ^{[ 1 ].}

En 2012, Hassanieh, Indyk, Katabi y Price ^{[ 11 ]} propusieron un algoritmo que toma${\displaystyle O(k\log n\log(n/k))}$Muestras y ejecuciones en el mismo tiempo de ejecución.

En 2014, Indyk y Kapralov ^{[ 12 ]} propusieron un algoritmo que toma${\displaystyle 2^{O(d\log d)}k\log n}$muestras y ejecuciones en un tiempo casi lineal en${\displaystyle n}$En 2016, Kapralov ^{[ 13 ]} propuso un algoritmo que utiliza muestras sublineales .${\displaystyle 2^{O(d^{2})}k\log n\log \log n}$y tiempo de decodificación sublineal${\displaystyle k\log ^{O(d)}n}$En 2019, Nakos, Song y Wang ^{[ 14 ]} introdujeron un nuevo algoritmo que utiliza muestras casi óptimas .${\displaystyle O(k\log n\log k)}$^{y requiere un tiempo de decodificación casi lineal. Potts y Volkmer [ 15 ]} propusieron un algoritmo de incremento de dimensión basado en el muestreo a lo largo de retículos de rango 1.

Hay varios trabajos sobre la generalización del entorno discreto al entorno continuo. ^{[ 16 ] [ 17 ]}

Existen varios trabajos basados ​​en el MIT , la MSU , la ETH y la Universidad Tecnológica de Chemnitz (TUC). Además, están disponibles gratuitamente en línea.

• Implementaciones de MSU
• Implementaciones de ETH
• Implementaciones del MIT
• GitHub
• Implementaciones de TUC

• Hassanieh, Haitham (2018). La transformada de Fourier dispersa: teoría y práctica . Association for Computing Machinery y Morgan & Claypool. ISBN 978-1-94748-707-9.