O domínio da frequência é um lugar real?

• A transformada discreta de Fourier (DFT) é uma ferramenta central em comunicações e processamento de sinais, mas o domínio da frequência não é a única forma de interpretar a realidade
• Em estruturas como a DCT, que obtêm bins de frequência multiplicando amostras de entrada pelos valores de uma função de base, é possível criar domínios de frequência com regras diferentes apenas trocando a base
• A matriz de Walsh fornece uma base de ondas quadradas usando apenas +1 e -1; se sequency e ortogonalidade forem ajustadas corretamente, é possível ir e voltar entre o domínio do tempo e a representação em frequência
• A matriz de Hadamard é uma forma reordenada da matriz de Walsh, podendo ser construída com Kronecker product ou operações de bits, e depois ter suas linhas reordenadas pelo critério de sequency para uso na WHT
• A mesma entrada se espalha por vários componentes harmônicos na DCT, mas se divide em componentes de onda quadrada na transformada Walsh-Hadamard, mostrando que a DFT não monopoliza a “verdade”

---

Revisitando o domínio da frequência de Fourier

• O domínio da frequência é um espaço matemático que representa sinais complexos convertendo-os em amplitudes e fases de ondas senoidais
• Essa representação facilita várias tarefas de processamento de sinais que seriam mais difíceis de tratar diretamente no domínio do tempo ou no domínio espacial
• A DFT tem papel central em comunicações e processamento de sinais, mas interpretar uma onda quadrada como soma de harmônicos senoidais ímpares é uma questão separada de considerá-la a única interpretação da realidade
• Ondas senoidais são amplamente encontradas na natureza, então ferramentas da família de Fourier funcionam bem em muitas tarefas, mas também é possível criar domínios de frequência bem definidos que operam com outras regras

Entendendo a DCT como função de base

• A transformada discreta do cosseno (DCT) pode ser vista como uma versão simplificada, apenas com números reais, da DFT
• A DCT-II obtém a magnitude de um bin de frequência específico F_k multiplicando os valores de entrada s_n pelos valores de uma certa fórmula de cosseno e depois somando tudo
• O ponto central é a função de base que gera a onda cosseno da frequência correspondente ao número atual do bin da DCT
• Generalizando, B(k, n) retorna um multiplicador de acordo com k e n, e a estrutura passa a ser a multiplicação disso pelas amostras de entrada, seguida da soma
• Do ponto de vista de software, B(k, n) pode ser vista como um array de consulta; matematicamente, como uma matriz
• Na matriz de base da DCT com N=16, a primeira linha k=0 corresponde ao componente DC de 0Hz e é um cosseno em que todos os valores são +1.00
• As linhas seguintes assumem formas de cosseno que variam cada vez mais rápido, como meio período, um período e um período e meio

Base de ondas quadradas e matriz de Walsh

• É possível criar, com a matriz de Walsh, uma função de base que divide o sinal usando ondas quadradas em vez de frequências senoidais
• A matriz de Walsh é composta por ondas quadradas que mudam em velocidades diferentes, e todos os multiplicadores são +1 ou -1
• O cálculo fica mais simples, resumindo-se a inverter o sinal de parte dos dados de entrada e então somar
• Mesmo parecendo simples, a matriz precisa satisfazer duas condições
  • Cada linha deve seguir a ordem de sequency, com uma troca de sinal a mais que a linha anterior
  • Para ir e voltar suavemente entre os dados no domínio do tempo e a representação em frequência, é preciso manter a ortogonalidade
• Para construir diretamente uma matriz de Walsh, começa-se com um array N×N, e N deve ser uma potência de 2
  • Preenche-se a primeira coluna à esquerda com +1 em todas as linhas
  • Cada nova coluna é feita como uma cópia espelhada dos valores existentes, e a área recém-adicionada é dividida em vários segmentos horizontais, com alguns segmentos tendo o sinal invertido
  • A cada repetição, copia-se a coluna e aumenta-se o número de segmentos de linha, invertendo alternadamente os sinais

Criando um array de Walsh a partir da matriz de Hadamard

• Na literatura e em códigos open source, é comum derivar o array de Walsh de uma matriz de Hadamard em vez de construí-lo diretamente
• A matriz de Hadamard é uma forma com as linhas reordenadas do array de Walsh
  • Por exemplo, em N=16, a linha #15 de Walsh vai para a #1 em Hadamard, e a linha #1 de Walsh fica na #8
• Uma das razões para essa convenção é que a construção de Hadamard surgiu historicamente antes, e Walsh foi desenvolvido sobre essa base
• Na prática, os métodos para construir a matriz de Hadamard são mais bem documentados, e também existem formas simples e eficientes usando manipulação de bits
• A construção clássica começa com um array 1×1 e copia a matriz anterior H_{n-1} em 4 blocos
  • O bloco superior esquerdo, o superior direito e o inferior esquerdo são copiados sem alterações
  • No bloco inferior direito, todos os sinais são invertidos
  • Nessa expansão usa-se a notação de Kronecker product ⊗, mas na prática a operação é copiar e inverter sinais
• Após n etapas de construção, o tamanho da matriz de Hadamard será sempre 2^n × 2^n
• O valor de Hadamard em uma célula específica pode ser obtido calculando x & y e então verificando se o número de bits ligados no resultado é par ou ímpar
  • Se o número de bits ligados for ímpar, o valor é -1; se for par, +1
  • Em código C, isso é implementado com __builtin_popcount(x & y) % 2

Implementando a transformada Walsh-Hadamard

• Para converter a matriz de Hadamard para a ordem intuitiva de Walsh, é preciso ordenar as linhas pelo critério de sequency
• O método mais simples é contar o número de mudanças de sinal em cada linha
• Outras formas com manipulação de bits também são possíveis
  • O número da linha de Walsh pode passar por XOR com ele mesmo deslocado 1 bit à direita para gerar um Gray code
  • Em seguida, inverte-se a ordem dos últimos n bits para calcular o mapeamento das linhas de Hadamard
• Trocando a base da implementação da DCT por esse array de Walsh, é possível criar uma “discrete square transform” e sua transformada inversa
• Tecnicamente, essa transformada é a Walsh–Hadamard transform (WHT)
• Ao processar a entrada de exemplo 1 1 1 1 5 5 5 5 com a DCT, os componentes harmônicos se espalham por vários bins de frequência
  • DCT : +24.00 -10.25 -0.00 +3.60 +0.00 -2.41 -0.00 +2.04
• Ao processar a mesma entrada com a transformada de onda quadrada, componentes não nulos aparecem apenas em F_0 e F_1
  • SQFT : +24.00 -16.00 +0.00 +0.00 +0.00 +0.00 +0.00 +0.00
• A transformada inversa isqft() restaura a entrada original
  • ISQFT : +1.00 +1.00 +1.00 +1.00 +5.00 +5.00 +5.00 +5.00

Comparação de espectrogramas e posição prática

• O texto compara um espectrograma DCT com um espectrograma Walsh-Hadamard usando um clipe de áudio de 11 segundos retirado de “DARE”, do Gorillaz
• A transformada Walsh-Hadamard tem boa eficiência computacional mesmo em computadores de baixo desempenho e se encaixa bem em certos tipos de dados, sendo usada em alguns nichos
• A conclusão não é que a WHT deva ser mais usada, e sim que a transformada discreta de Fourier não monopoliza a verdade
• Os espectrogramas foram calculados com DCT e WHT a partir de um arquivo de áudio mono de 44,1kHz
  • a janela de amostras de entrada é 512
  • o stepover da transformada é 1
  • o tamanho do array de saída é de aproximadamente 512 × 485k
  • a intensidade dos pixels aplica gamma de cerca de 0.4 ao valor absoluto normalizado
  • a imagem é redimensionada com Lanczos resampling e renderizada com um colormap linear de preto–azul-celeste–branco
• Como exemplo de experimento com Walsh-Hadamard em compressão de imagem, o texto também apresenta http://rotormind.com/blog/2019/hadamard-days-night/

[GN⁺]

Opiniões do Hacker News

• Matematicamente, a transformada de Fourier é apenas uma forma de representar um sinal no tempo em uma base específica de vetores ortogonais
  O vetor de deslocamento na superfície da Terra também pode ser representado na base norte/leste, ou na direção de uma estrada qualquer e na direção perpendicular a ela
  Sinais dependentes do tempo ou funções “bonitas” estão em um espaço vetorial de dimensão infinita, o que dificulta a imaginação, mas a matemática central funciona de modo parecido
  Na transformada de Fourier, os vetores de base são funções harmônicas, e o domínio da frequência é um “mapa” que mostra o sinal como uma combinação de infinitas funções harmônicas
  Mapas de outras bases, como a transformada de Walsh–Hadamard, são igualmente reais, e a representação no domínio do tempo também é apenas um entre vários mapas, embora seja a mais familiar para nós

  • É uma resposta correta e, acrescentando a isso, a transformada de Fourier se aplica não só a sinais no tempo, mas também a funções contínuas por partes, diferenciáveis e integráveis no sentido de Dirichlet
    Há muitas aplicações, como processamento de imagens, solução de equações diferenciais e multiplicação rápida
    Matematicamente, essas transformações são sem perdas, de modo que a função transformada contém exatamente as mesmas informações da função original, e só com a transformada é possível voltar ao original
    Na engenharia, muitas vezes se faz a transformação para descartar informações indesejadas, como certos componentes de frequência, e isso costuma deixar esse ponto menos claro
    No fim, é uma das várias perspectivas para olhar uma mesma função
  • Antigamente eu também pensava nisso como “outra base”, mas hoje acho que essa analogia é um pouco perigosa, ou pelo menos não é a história toda
    Especialmente em espaços multidimensionais, a transformada de Fourier multidimensional geral só funciona direito quando esse espaço tem uma métrica plana
    Considerando que o próprio universo é curvo, isso parece um sinal de alerta
    Houve recentemente um estudo interessante que generalizou séries de Fourier para uma rede hiperbólica específica, e o resultado é que o espaço de Fourier pode ter dimensão maior que o espaço de posições
    Além disso, a dimensão desse “espaço de Fourier” varia conforme o modo de discretização da rede, de modo que uma rede 2D pode ter um domínio análogo à frequência de 4 dimensões, enquanto outra rede 2D pode ter um domínio análogo de 8 dimensões
    https://arxiv.org/abs/2108.09314 ou https://www.pnas.org/doi/full/10.1073/pnas.2116869119
  • Astrônomos do passado acreditavam em um modelo geocêntrico do universo com epiciclos anexados, e, se precisavam de mais precisão, adicionavam mais epiciclos
    Era um modelo completamente errado, mas na prática estavam usando séries de Fourier como aproximador de funções
  • Concordo em geral, mas toda base ortonormal divide o espectro de frequências
    Mesmo usando uma base como a de polinômios, no fim você está construindo a função a partir de componentes de frequência
    A base de Fourier é especial porque cada elemento corresponde a uma frequência específica
    Porém, cada base é mais ou menos projetada para um objetivo, e uma mudança de base pode reorganizar o espectro de uma forma complicada de analisar
    Nesse caso, você passa a analisar outras propriedades, como suavidade
    A maioria das funções de interesse tem um espectro característico, mas a base de Fourier não responde a todas as perguntas
  • Os vetores de base não precisam necessariamente ser perpendiculares, precisam?
    Se houver algum componente perpendicular, como norte e nordeste, também dá para representar [n, e] em outras coordenadas
    Os coeficientes específicos podem estar errados por causa das colunas, mas o ponto principal é que é possível

• Isso me lembra uma conversa que tive diante de um quadro branco no grupo de sistemas dinâmicos durante o mestrado
  “A energia é injetada no sistema pela esquerda e se dissipa aqui, à direita”
  “Mas o sistema é invariante por rotação, então não existe esquerda nem direita”
  “Estou falando no espaço de frequências”
  “Ah, achei que você estivesse falando do espaço real”
  “Você é idiota? Quem pensa em espaço real?”

  • Espera, no espaço de frequências também existe esquerda e direita?
    Não é uma representação abstrata, sem relação direta com esquerda, direita, cima e baixo das dimensões espaciais?
  • Só o desprezo que exalei ao longo da vida pela academia da torre de marfim já daria para abastecer uma pequena nação insular por 10 anos
  • No mestrado as pessoas se chamam de idiotas assim, ou isso foi bastante dramatizado?

• A base de Fourier é única no sentido de que as funções de base exponenciais complexas são autovetores de sistemas lineares invariantes no tempo (LTI)
  Outras transformadas não têm essa propriedade
  Muitos sistemas reais, como circuitos, canais de comunicação e antenas, são LTI, e graças a essa propriedade sinais transmitidos em frequências diferentes não interferem entre si
  Por isso a transformada de Fourier é mais usada do que outras transformadas
  Na física quântica também há a conexão em que se usam pares de Fourier para as funções de onda de posição e momento, algo que outras transformadas não têm

  • Fiquei surpreso que quase ninguém mencionou isso
    Com uma formação em engenharia elétrica, para fins de análise assumimos que muitos sistemas são lineares ou têm não linearidades muito fracas, e os sinais também são em geral periódicos, então a transformada de Fourier é natural
    Convolução vira multiplicação, e a derivada temporal de uma exponencial complexa vira multiplicação por j*omega
    É muito melhor fazer multiplicação do que convolução e derivação temporal
    Quando se aceita que “usamos a representação de Fourier porque ela é conveniente em certas situações comuns”, deixa de ser surpreendente usar outras transformações matemáticas para outros problemas
  • Tecnicamente, isso não é um caso especial da base de Laplace?
    Sempre achei estranho que muitos cursos não tratem direito da transformada de Laplace bilateral mais geral e passem direto da transformada de Fourier bilateral para a transformada de Laplace unilateral
    https://en.wikipedia.org/wiki/Two-sided_Laplace_transform

• Se a pergunta é se é um “lugar real”, lembro de um experimento de óptica de antigamente
  Ao passar uma imagem por algumas lentes, surge um plano das frequências, e depois ela passa por outras lentes e é projetada em uma tela
  Se você bloqueia parte desse plano de frequências, a imagem muda
  Era extremamente complicado de manipular, e fiquei muito grato ao Dr. Bruce Sinclair, de St Andrew’s
  Trabalhar em laboratório de física permite ver como as coisas funcionam, mas, alguns meses depois do experimento, ao revisitar a teoria, é fácil ficar bem perdido

  • O plano das frequências não surge sempre?
    Então parece ser por isso que a abertura limita a resolução e que surgem spikes de difração em telescópios refletores, por exemplo
  • Também dá para fazer em software: https://imagemagick.org/Usage/fourier/#noise_removal
  • A propriedade de obter uma representação no domínio da frequência por óptica é bastante conveniente em vários métodos de microscopia e espectroscopia baseados em fontes de luz
  • Isso é óptica de Fourier
    Schlieren também funciona desse jeito

• Outra generalização interessante da DFT é a transformada de Lomb-Scargle
  Ela não exige um intervalo de medição fixo no domínio do tempo
  É muito usada para encontrar a frequência de sinais periódicos quando os intervalos de medição não são uniformes, como em astrofísica
  https://iopscience.iop.org/article/10.3847/1538-4365/aab766 é uma introdução geral, e https://docs.astropy.org/en/stable/timeseries/lombscargle.ht... apresenta bem como usar isso na biblioteca astropy do Python

  • Ultimamente tenho pensado bastante que representar dados do Prometheus no domínio da frequência talvez seja útil para visualizar padrões de acesso semanais, diários e anuais no planejamento de capacidade
    O autoescalonamento pode ajudar a evitar degradações de desempenho com cara de incidente, mas não diz qual deveria ser o orçamento anual nem por quê
    Só que os dados do Prometheus dificilmente podem ser vistos como tendo um intervalo de amostragem de verdade
    Mesmo que cada máquina do cluster reporte em intervalos regulares, elas não estão sincronizadas entre si

• Por outro ângulo, a cóclea pode ser vista como uma implementação “real” da transformada de Fourier
  https://www.britannica.com/science/sound-physics/The-ear-as-...

  • A cóclea, na verdade, reforça o ponto do texto
    Ela transforma para o domínio da frequência, mas não faz nem aproxima uma transformada de Fourier
    A transformação tempo→domínio da frequência que a cóclea “implementa” é mais próxima de uma transformada wavelet
    Interpretar a cóclea como uma transformada de Fourier é parecido com o erro de achar que os cones do olho respondem apenas à luz vermelha, verde e azul
    Na prática, cada célula responde de forma diferente ao longo de uma faixa de frequências
    Os cones têm picos nas regiões de baixa, média e alta frequência e decaem para os dois lados; já as células ciliadas da cóclea têm curvas de resposta mais parecidas com wavelets, com um segundo pico nos harmônicos da frequência de pico
    Não sou especialista, só um amador entusiasmado, então espero que alguém que saiba mais me corrija
  • É fácil esquecer o quanto a biologia está firmemente enraizada na física
    Na faculdade, tivemos um problema em que nossa linhagem de células-tronco estava se diferenciando em osso; descobrimos que a rigidez do ambiente era um sinal que as células-tronco conseguiam perceber
    Era como se a placa de cultura rígida estivesse dizendo às células que elas deveriam virar células ósseas

• O texto dizia que “não conheço um algoritmo elegante para ordenar as linhas de uma matriz de Hadamard por sequency além de contar os cruzamentos por zero”, mas, ao olhar para a matriz e tentar adivinhar o padrão, vi que já era um método conhecido
  Segundo https://en.wikipedia.org/wiki/Walsh_matrix, a ordenação por sequency da matriz de Walsh pode ser obtida aplicando primeiro uma permutação de inversão de bits à matriz de Hadamard e, em seguida, uma permutação por código Gray

• O texto levanta uma pergunta muito geral e filosófica, mas depois diz que, como é possível encontrar outras bases ortogonais e transformadas, o domínio da frequência não é tão especial
  Ainda assim, acho que o domínio da frequência e a transformada de Fourier são mais especiais do que muitas outras transformadas
  Porque podem ser observados diretamente na natureza
  Por exemplo, uma lente realiza a transformada de Fourier bidimensional de uma imagem de entrada carregada por luz paralela, e isso pode ser visto em uma tela
  Também é possível projetar a saída de uma rede de difração ou de um prisma em um CCD e medir o comprimento de onda ou a frequência da luz; isso também é uma medição direta no domínio da frequência
  Medições semelhantes são possíveis com ondas de RF

• Ondas senoidais são especiais por serem soluções naturais da equação de onda de Helmholtz
  Ondas quadradas têm outros problemas, como energia infinita
  Este texto pode fazer sentido para matemáticos ou cientistas da computação, mas deixa passar a física fundamental do som e das ondas

  • Ondas senoidais também são especiais por serem autofunções do operador diferencial
    Os resultados físicos provavelmente são consequência dessa propriedade
    No fim, uma lição central da matemática moderna é que é útil olhar para um objeto por várias perspectivas
  • Concordo
    Um número enorme de objetos físicos são osciladores harmônicos, e isso tem uma base bem fundamental na física
    Consigo pensar em muitos outros lugares em que a análise de Fourier é útil, mas ondas senoidais são fisicamente mais “reais”, enquanto dizer que elas podem ser representadas por qualquer conjunto de bases está mais para “válido”
    A palavra “real” parece sugerir que há um oscilador de verdade por trás do fenômeno
    Ondas quadradas são menos físicas por causa das descontinuidades tanto no sinal quanto em sua derivada, e a natureza realmente não gosta de descontinuidades
  • O domínio da frequência torna a matemática muito fácil em operações lineares invariantes no tempo, que descrevem aproximadamente muitos sistemas existentes na natureza
    Por exemplo, o fenômeno de Gibbs surge naturalmente da transformada inversa de Fourier de uma resposta em frequência que zera todas as frequências acima de uma certa frequência de corte
    Fico curioso sobre como o domínio da frequência de uma onda quadrada explicaria o fenômeno de Gibbs
    Provavelmente apareceriam harmônicos da frequência básica da onda quadrada, como se o sistema fosse não linear

• Ao estudar física e matemática na graduação, cheguei à conclusão de que saber os valores de uma função f(x) para infinitos valores de x e saber os componentes de frequência de f para infinitas frequências são coisas equivalentes
  Filosoficamente, as duas representações são igualmente “reais”
  Alguns problemas simplesmente são resolvidos com mais facilidade em uma representação do que em outra

  • Concordo totalmente
    Mudar do domínio do tempo para o domínio da frequência é como uma mudança de sistema de coordenadas
    Um sinal com um único pico estreito no domínio do tempo pode ser representado de forma muito pequena e esparsa por uma única delta na posição do pico, mas no domínio da frequência essa representação compacta não aparece
    Por outro lado, um sinal senoidal no domínio do tempo não é compacto ali, mas no domínio da frequência bastam algumas deltas
    Tempo e frequência são duas maneiras de representar a mesma coisa e, em alguns casos, um domínio é mais fácil; em outros, é o contrário
    É possível provar que algo limitado no domínio do tempo se torna ilimitado no domínio da frequência, e vice-versa
    Portanto, algo compacto em um domínio sempre se espalha ao passar para o outro
    Na mecânica quântica, posição e momento são variáveis conjugadas, como tempo e frequência acima, de modo que, se a posição é limitada, o momento é ilimitado, e vice-versa
    Essa é a ideia central do princípio da incerteza de Heisenberg