¿El dominio de la frecuencia es un lugar real?

• La transformada discreta de Fourier (DFT) es una herramienta clave en comunicaciones y procesamiento de señales, pero el dominio de la frecuencia no es la única forma de interpretar la realidad
• En estructuras como la DCT, donde se obtienen bins de frecuencia multiplicando las muestras de entrada por valores de una función base, basta con cambiar la base para crear un dominio de frecuencia con reglas distintas
• La matriz de Walsh ofrece una base de ondas cuadradas que usa solo +1 y -1, y si se ajustan la sequency y la ortogonalidad, es posible ir y venir entre el dominio del tiempo y su representación en frecuencia
• La matriz de Hadamard es una forma reordenada de la matriz de Walsh, y se construye con el producto de Kronecker o mediante operaciones de bits; luego se reordenan las filas según la sequency para usarla en la WHT
• La misma entrada se distribuye en varios componentes armónicos en la DCT, mientras que en la transformada Walsh-Hadamard se divide en componentes de onda cuadrada, lo que muestra que la DFT no monopoliza la “verdad”

---

Volver a mirar el dominio de frecuencia de Fourier

• El dominio de la frecuencia es un espacio matemático que representa señales complejas transformándolas en amplitud y fase de ondas sinusoidales
• Gracias a esta representación, muchas tareas de procesamiento de señales que son difíciles de manejar directamente en el dominio del tiempo o del espacio se vuelven más sencillas
• La DFT cumple un papel central en comunicaciones y procesamiento de señales, pero interpretar una onda cuadrada como la suma de armónicos sinusoidales impares es una cuestión distinta a decir que esa sea la única interpretación posible de la realidad
• Las ondas sinusoidales abundan en la naturaleza, por eso las herramientas de la familia Fourier encajan bien en muchas tareas, pero también es posible construir dominios de frecuencia bien definidos que funcionen con otras reglas

Entender la DCT como una función base

• La transformada discreta del coseno (DCT) puede verse como una versión simplificada y solo real de la DFT
• La DCT-II calcula la magnitud de un bin de frecuencia específico F_k multiplicando cada valor de entrada s_n por el valor de una expresión cosenoidal determinada y luego sumando el resultado
• La clave es la función base que genera una onda cosenoidal con la frecuencia correspondiente al número de bin actual de la DCT
• En forma general, B(k, n) devuelve un multiplicador según k y n, y la estructura consiste en multiplicarlo por las muestras de entrada y acumular la suma
• Desde la perspectiva del software, B(k, n) puede verse como un arreglo de consulta; matemáticamente, como una matriz
• En una matriz base DCT con N=16, la primera fila k=0 corresponde al componente DC de 0Hz, y es un coseno cuyos valores son todos +1.00
• Las filas siguientes toman la forma de cosenos que cambian cada vez más rápido: medio período, un período, período y medio, etc.

Base de ondas cuadradas y matriz de Walsh

• Una función base que divide una señal no con frecuencias sinusoidales sino con ondas cuadradas puede construirse con la matriz de Walsh
• La matriz de Walsh está formada por ondas cuadradas que avanzan a distintas velocidades, y todos sus multiplicadores son +1 o -1
• El cálculo se simplifica a cambiar el signo de parte de los datos de entrada y luego sumarlos
• Incluso una matriz que parece simple debe cumplir dos condiciones
  • Cada fila debe seguir un orden de sequency con una transición de signo más que la fila anterior
  • Para poder ir y volver sin problemas entre los datos en el dominio del tiempo y su representación en frecuencia, debe mantenerse la ortogonalidad
• Para construir directamente una matriz de Walsh, se parte de un arreglo N×N, donde N debe ser una potencia de 2
  • Se coloca +1 en la primera columna de todas las filas
  • Se crea una nueva columna como copia en espejo de los valores existentes, y el área recién añadida se divide en varios tramos horizontales para invertir el signo en algunos de ellos
  • En cada repetición se copia una columna y se incrementa el número de tramos de fila, invirtiendo signos de forma alternada

Crear un arreglo de Walsh a partir de una matriz de Hadamard

• En la literatura y en el código open source, muchas veces no se construye el arreglo de Walsh de forma directa, sino que se deriva de la matriz de Hadamard
• La matriz de Hadamard es una versión con las filas reordenadas del arreglo de Walsh
  • Por ejemplo, con N=16, la fila #15 de Walsh pasa a la #1 en Hadamard, y la fila #1 de Walsh queda en la #8
• Una razón de esta convención es que la construcción de Hadamard apareció antes históricamente y Walsh se desarrolló sobre esa base
• En la práctica, los métodos para construir una matriz de Hadamard están mejor documentados, y también existen enfoques simples y eficientes con manipulación de bits
• La construcción clásica de manual empieza con un arreglo 1×1 y copia la matriz previa H_{n-1} en 4 bloques
  • La parte superior izquierda, superior derecha e inferior izquierda se copian sin cambios
  • En la parte inferior derecha se invierten todos los signos
  • En esta expansión se usa la notación de producto de Kronecker ⊗, aunque en la práctica lo que ocurre es copiar e invertir signos
• Después de aplicar este proceso n veces, el tamaño de la matriz de Hadamard siempre es 2^n × 2^n
• El valor de Hadamard en una celda específica puede obtenerse calculando x & y y luego determinando si la cantidad de bits encendidos en el resultado es par o impar
  • Si la cantidad de bits encendidos es impar, el valor es -1; si es par, +1
  • En código C, esto se implementa con __builtin_popcount(x & y) % 2

Implementación de la transformada Walsh-Hadamard

• Para convertir la matriz de Hadamard al orden intuitivo de Walsh, hay que ordenar las filas según la sequency
• La forma más simple es contar cuántos cambios de signo hay en cada fila
• También son posibles otros métodos basados en operaciones de bits
  • Se aplica XOR entre el número de fila de Walsh y ese mismo número desplazado 1 bit a la derecha para generar un código Gray
  • Luego se invierte el orden de los últimos n bits para calcular el mapeo de filas de Hadamard
• Si se reemplaza la base de una implementación DCT por este arreglo de Walsh, se puede crear una “discrete square transform” junto con su transformada inversa
• Técnicamente, esta transformación es la transformada Walsh–Hadamard (WHT)
• Si la entrada de ejemplo 1 1 1 1 5 5 5 5 se procesa con DCT, los componentes armónicos se reparten en varios bins de frecuencia
  • DCT : +24.00 -10.25 -0.00 +3.60 +0.00 -2.41 -0.00 +2.04
• Si la misma entrada se procesa con una transformada de ondas cuadradas, solo aparecen componentes no nulos en F_0 y F_1
  • SQFT : +24.00 -16.00 +0.00 +0.00 +0.00 +0.00 +0.00 +0.00
• La transformada inversa isqft() recupera la entrada original
  • ISQFT : +1.00 +1.00 +1.00 +1.00 +5.00 +5.00 +5.00 +5.00

Comparación de espectrogramas y lugar práctico

• Se comparan un espectrograma DCT y un espectrograma Walsh-Hadamard usando un clip de audio de 11 segundos tomado de “DARE” de Gorillaz
• La transformada Walsh-Hadamard tiene buena eficiencia computacional incluso en computadoras de bajo rendimiento y se usa en algunos nichos para ciertos tipos de datos
• La conclusión no es que haya que usar más la WHT, sino que la transformada discreta de Fourier no monopoliza la verdad
• Los espectrogramas se calcularon con DCT y WHT a partir de un archivo de audio mono de 44.1kHz
  • La ventana de muestras de entrada es 512
  • El stepover de la transformada es 1
  • El tamaño del arreglo de salida es aproximadamente 512 × 485k
  • La intensidad de los píxeles aplica una gamma de aproximadamente 0.4 sobre el valor absoluto normalizado
  • La imagen se redimensiona con remuestreo Lanczos y se renderiza con un colormap lineal negro–celeste–blanco
• Como ejemplo de experimentos con Walsh-Hadamard en compresión de imágenes, también se presenta http://rotormind.com/blog/2019/hadamard-days-night/

[GN⁺]

Opiniones de Hacker News

• Matemáticamente, la transformada de Fourier no es más que una forma de expresar una señal temporal en una base de vectores ortogonales específica.
  El vector de desplazamiento sobre la superficie de la Tierra también puede expresarse en una base norte/este, o en la dirección de alguna carretera y la dirección perpendicular a ella.
  Las señales dependientes del tiempo o las funciones “bonitas” están en un espacio vectorial de dimensión infinita, así que son difíciles de imaginar, pero la matemática central funciona de forma parecida.
  En la transformada de Fourier, los vectores base son funciones armónicas, y el dominio de la frecuencia es un “mapa” que muestra la señal como una combinación de infinitas funciones armónicas.
  Los mapas con otras bases, como la transformada de Walsh–Hadamard, son igual de reales, y la representación en el dominio del tiempo también es solo uno de muchos mapas, aunque sea el que nos resulta familiar.

  • Es una respuesta correcta, y agregaría que la transformada de Fourier se aplica no solo a señales temporales, sino también a funciones continuas por tramos, diferenciables e integrables en el sentido de Dirichlet.
    Tiene muchas aplicaciones, como procesamiento de imágenes, resolución de ecuaciones diferenciales y multiplicación rápida.
    Matemáticamente, estas transformaciones son sin pérdida, de modo que la función transformada contiene exactamente la misma información que la función original, y con solo la transformada se puede volver al original.
    En ingeniería, a menudo se transforma para descartar información no deseada, como ciertos componentes de frecuencia, y por eso este punto suele quedar difuso.
    En última instancia, es una de varias perspectivas para mirar una misma función.
  • Antes yo también pensaba en esto como “otra base”, pero hoy creo que esa analogía es un poco peligrosa, o al menos no lo explica todo.
    En particular, en espacios multidimensionales, la transformada de Fourier multidimensional general solo funciona bien cuando ese espacio tiene una métrica plana.
    Si pensamos que el universo mismo es curvo, eso parece una señal de advertencia.
    Hace poco hubo una investigación interesante que generalizó las series de Fourier a ciertas redes hiperbólicas, y el resultado es que el espacio de Fourier puede terminar teniendo más dimensiones que el espacio de posiciones.
    Además, la dimensión de este “espacio de Fourier” cambia según la forma de discretizar la red: una red bidimensional puede tener un dominio análogo de frecuencias de 4 dimensiones, mientras que otra red bidimensional puede tener uno de 8 dimensiones.
    https://arxiv.org/abs/2108.09314 o https://www.pnas.org/doi/full/10.1073/pnas.2116869119
  • Los astrónomos de antes creían en un modelo geocéntrico del universo al que le agregaban epiciclos, y si necesitaban más precisión, añadían más epiciclos.
    Era un modelo completamente equivocado, pero en la práctica estaban usando una serie de Fourier como aproximador de funciones.
  • En general estoy de acuerdo, pero toda base ortonormal divide el espectro de frecuencias.
    Incluso si usas una base como la de polinomios, al final estás construyendo una función a partir de componentes de frecuencia.
    La base de Fourier es especial en que cada elemento corresponde a una frecuencia específica.
    Dicho eso, cada base está más bien diseñada para un propósito, y un cambio de base puede reordenar el espectro de formas complejas de analizar.
    En ese caso, uno termina analizando otras propiedades, como la suavidad.
    La mayoría de las funciones que nos interesan tienen un espectro característico, pero la base de Fourier no responde todas las preguntas.
  • ¿Los vectores base no necesariamente tienen que ser perpendiculares, no?
    Si tienen cierta componente perpendicular, como norte y noreste, también se puede expresar [n, e] en otras coordenadas.
    Puede que los coeficientes concretos estén mal por culpa del calor, pero lo importante es que se puede.

• Me acordé de una conversación frente al pizarrón en el grupo de sistemas dinámicos durante mi maestría.
  “La energía se inyecta en el sistema por la izquierda y se disipa aquí, a la derecha”.
  “Pero el sistema es invariante ante rotaciones, así que no hay izquierda ni derecha”.
  “Estoy hablando en el espacio de frecuencias”.
  “Ah, pensé que hablaba del espacio real”.
  “¿Es usted tonto? ¿Quién piensa en el espacio real?”

  • Espera, ¿en el espacio de frecuencias también hay izquierda y derecha?
    ¿No es una representación abstracta sin relación directa con izquierda, derecha, arriba o abajo en las dimensiones espaciales?
  • Con todo el desprecio que he acumulado hacia la academia de torre de marfil durante toda mi vida, probablemente se podría alimentar a un pequeño país insular durante 10 años.
  • ¿En la maestría se llaman tontos entre ustedes, o está muy dramatizado?

• La base de Fourier es única en el sentido de que las funciones base exponenciales complejas son autovectores de los sistemas lineales invariantes en el tiempo (LTI).
  Otras transformadas no tienen esta propiedad.
  Muchos sistemas reales, como circuitos, canales de comunicación y antenas, son LTI, y gracias a esta propiedad las señales transmitidas en distintas frecuencias no interfieren entre sí.
  Por eso la transformada de Fourier se usa más que otras transformadas.
  En física cuántica también existe la conexión de usar pares de Fourier para las funciones de onda de posición y momento, y otras transformadas no tienen esa propiedad.

  • Me sorprende que casi nadie haya mencionado esto.
    Desde una formación en ingeniería eléctrica, para el análisis se asume que muchos sistemas son lineales o solo muy débilmente no lineales, y las señales suelen ser mayormente periódicas, así que la transformada de Fourier resulta natural.
    La convolución se convierte en multiplicación, y la derivada temporal de una exponencial compleja pasa a ser multiplicar por j*omega.
    Es mucho mejor hacer multiplicaciones que convoluciones y derivadas temporales.
    Si uno acepta que “se usa la representación de Fourier porque es conveniente en ciertas situaciones comunes”, no sorprende que se usen otras transformaciones matemáticas para otros problemas.
  • Técnicamente, ¿no es un caso especial de la base de Laplace?
    Siempre me pareció raro que muchos cursos no traten bien la transformada bilateral de Laplace más general, y salten directamente de la transformada bilateral de Fourier a la transformada unilateral de Laplace.
    https://en.wikipedia.org/wiki/Two-sided_Laplace_transform

• Si preguntas si es un “lugar real”, me viene a la mente un experimento óptico de hace tiempo
  Si haces pasar una imagen por unas cuantas lentes, aparece un plano de frecuencias, y luego se proyecta en una pantalla tras pasar de nuevo por lentes
  Si bloqueas parte de ese plano de frecuencias, la imagen cambia
  Era increíblemente difícil de manipular, y le quedé muy agradecido al Dr Bruce Sinclair, de St Andrew’s
  Trabajar en un laboratorio de física te permite ver cómo funcionan las cosas, pero si vuelves a la teoría unos meses después del experimento, es bastante fácil perderte

  • ¿No se forma siempre el plano de frecuencias?
    Por eso parece que la apertura limita la resolución, y de ahí se derivan cosas como los picos de difracción en los telescopios reflectores
  • También se puede hacer con software: https://imagemagick.org/Usage/fourier/#noise_removal
  • La propiedad de obtener una representación en el dominio de la frecuencia mediante óptica es bastante práctica en varias técnicas de microscopía y espectroscopía basadas en fuentes de luz
  • Es óptica de Fourier
    Schlieren también funciona de esta manera

• Otra generalización interesante de la DFT es la transformada de Lomb-Scargle
  No requiere intervalos de medición fijos en el dominio del tiempo
  Se usa mucho para encontrar la frecuencia de señales periódicas cuando los intervalos de medición no son uniformes, como en astrofísica
  https://iopscience.iop.org/article/10.3847/1538-4365/aab766 es una introducción general, y https://docs.astropy.org/en/stable/timeseries/lombscargle.ht... explica bien cómo usarla en la biblioteca astropy de Python

  • Últimamente he pensado mucho que representar los datos de Prometheus en el dominio de la frecuencia podría ser útil para visualizar patrones de acceso semanales, diarios y anuales en la planificación de capacidad
    El escalado automático puede ayudar a evitar degradaciones de rendimiento que causen fallas, pero no te dice cuál debería ser el presupuesto anual ni por qué
    Eso sí, los datos de Prometheus difícilmente pueden considerarse un intervalo de muestreo real
    Aunque cada máquina del clúster reporte a intervalos regulares, no están sincronizadas entre sí

• Desde otra perspectiva, la cóclea puede verse como una implementación “real” de la transformada de Fourier
  https://www.britannica.com/science/sound-physics/The-ear-as-...

  • La cóclea, más bien, respalda el punto central del artículo
    Sí transforma al dominio de la frecuencia, pero no hace una transformada de Fourier ni la aproxima
    La transformación tiempo→dominio de la frecuencia que “implementa” la cóclea se parece más a una transformada wavelet
    Interpretar la cóclea como una transformada de Fourier es parecido al error de pensar que los conos del ojo solo responden a luz roja, verde y azul
    En realidad, cada célula responde de manera distinta a un rango de frecuencias
    Los conos alcanzan su pico en las zonas de baja, media y alta frecuencia y disminuyen hacia ambos lados, mientras que las células ciliadas de la cóclea tienen una curva de respuesta más parecida a una wavelet, con picos secundarios en los armónicos de la frecuencia pico
    No soy experto, solo un aficionado entusiasta, así que espero que alguien que sepa más me corrija
  • Es fácil olvidar lo firmemente arraigada que está la biología en la física
    En la universidad tuvimos un problema con nuestra línea de células madre, que se diferenciaba en hueso, y resultó que la rigidez del entorno era una señal que las células madre podían percibir
    Era como si la placa de cultivo rígida les estuviera diciendo a las células que debían convertirse en osteocitos

• El artículo decía que “no conozco un algoritmo más elegante para ordenar las filas de una matriz de Hadamard según la sequency que contar los cruces por cero”, pero al mirar la matriz y adivinar el patrón resultó que ya era un método conocido
  Según https://en.wikipedia.org/wiki/Walsh_matrix, el ordenamiento por sequency de una matriz de Walsh puede obtenerse aplicando primero a la matriz de Hadamard una permutación de inversión de bits y luego una permutación de código Gray

• El artículo plantea una pregunta muy general y filosófica, pero después dice que, como se pueden encontrar otras bases ortogonales y transformadas, el dominio de la frecuencia no es tan especial
  Aun así, creo que el dominio de la frecuencia y la transformada de Fourier son más especiales que muchas otras transformadas
  Porque pueden observarse directamente en la naturaleza
  Por ejemplo, una lente realiza la transformada de Fourier bidimensional de una imagen de entrada transportada por luz paralela, y eso puede verse en una pantalla
  También se puede medir la longitud de onda o la frecuencia de la luz proyectando la salida de una rejilla o un prisma sobre un CCD, y eso también es una medición directa en el dominio de la frecuencia
  Con ondas RF se pueden hacer mediciones parecidas

• Las ondas sinusoidales son especiales en tanto son soluciones naturales de la ecuación de onda de Helmholtz
  Las ondas cuadradas también tienen otros problemas, como energía infinita
  Este artículo puede tener sentido para matemáticos o científicos de la computación, pero pasa por alto la física fundamental del sonido y las ondas

  • Las ondas sinusoidales también son especiales porque son funciones propias del operador diferencial
    Los resultados físicos probablemente sean consecuencia de esa propiedad
    Al final, una lección central de la matemática moderna es que es útil mirar los objetos desde varios puntos de vista
  • Exacto
    Una cantidad enorme de objetos físicos son osciladores armónicos, y eso tiene una base bastante fundamental en la física
    Se me ocurren muchos otros lugares donde el análisis de Fourier resulta útil, pero las ondas sinusoidales son más “reales” físicamente, y decir que se pueden expresar con cualquier conjunto de bases se acerca más a algo “válido”
    La palabra “real” parece dar la sensación de que hay un oscilador real detrás del fenómeno
    Una onda cuadrada es menos física por las discontinuidades tanto de la señal como de su derivada, y a la naturaleza realmente no le gustan las discontinuidades
  • El dominio de la frecuencia hace que la matemática sea mucho más sencilla en operaciones lineales invariantes en el tiempo que describen de forma aproximada muchos sistemas presentes en la naturaleza
    Por ejemplo, el fenómeno de Gibbs surge de manera natural de la transformada inversa de Fourier de una respuesta en frecuencia que pone en cero todas las frecuencias por encima de cierta frecuencia de corte
    Me pregunto cómo explicaría el dominio de la frecuencia de una onda cuadrada el fenómeno de Gibbs
    Supongo que aparecerían armónicos de la frecuencia de la onda cuadrada fundamental, como si el sistema fuera no lineal

• Al estudiar física y matemáticas en la licenciatura, llegué a la conclusión de que conocer los valores de una función f(x) para infinitos x, y conocer los componentes de frecuencia de f para infinitas frecuencias, son cosas equivalentes
  Filosóficamente, ambas representaciones son igual de “reales”
  Algunos problemas simplemente se resuelven más fácilmente en una representación que en la otra

  • Estoy totalmente de acuerdo
    Cambiar del dominio del tiempo al dominio de la frecuencia es como un cambio de sistema de coordenadas
    Una señal con un solo pico estrecho en el dominio del tiempo puede representarse de forma muy pequeña y dispersa con una sola delta en la posición del pico, pero en el dominio de la frecuencia no se obtiene una representación tan comprimida
    A la inversa, una señal sinusoidal en el dominio del tiempo no es compacta allí, pero en el dominio de la frecuencia basta con unas pocas deltas
    El tiempo y la frecuencia son dos formas de representar lo mismo; en algunos casos un dominio es más fácil, y en otros ocurre lo contrario
    Se puede demostrar que lo que está acotado en el dominio del tiempo queda no acotado en el dominio de la frecuencia, y viceversa
    Por eso, lo que es compacto en un dominio siempre se dispersa al pasar al otro
    En mecánica cuántica, la posición y el momento son variables conjugadas, como el tiempo y la frecuencia de arriba, de modo que si la posición está acotada, el momento queda no acotado, y viceversa
    Esa es la idea central del principio de incertidumbre de Heisenberg