Le domaine fréquentiel est-il un lieu réel ?

• La transformée de Fourier discrète (DFT) est un outil essentiel des télécommunications et du traitement du signal, mais le domaine fréquentiel n’est pas l’unique manière d’interpréter la réalité
• Dans une structure comme la DCT, où l’on calcule des bins de fréquence en multipliant les échantillons d’entrée par les valeurs de fonctions de base, il suffit de changer de base pour créer un domaine fréquentiel régi par d’autres règles
• La matrice de Walsh fournit une base d’ondes carrées n’utilisant que +1 et -1 ; en respectant la sequency et l’orthogonalité, on peut faire des allers-retours entre le domaine temporel et la représentation fréquentielle
• La matrice de Hadamard est une réorganisation de la matrice de Walsh ; on la construit avec un produit de Kronecker ou des opérations sur les bits, puis on réordonne ses lignes selon la sequency pour l’utiliser dans la WHT
• Un même signal d’entrée se répartit en plusieurs composantes harmoniques avec la DCT, mais en composantes d’ondes carrées avec la transformée de Walsh-Hadamard, montrant que la DFT n’a pas le monopole de la « vérité »

---

Revoir le domaine fréquentiel de Fourier

• Le domaine fréquentiel est un espace mathématique qui représente un signal complexe sous forme d’amplitudes et de phases de sinusoïdes
• Grâce à cette représentation, il devient plus facile d’effectuer des tâches de traitement du signal difficiles à traiter directement dans le domaine temporel ou spatial
• La DFT joue un rôle central dans les télécommunications et le traitement du signal, mais savoir si l’interprétation qui transforme une onde carrée en somme d’harmoniques sinusoïdales impaires est l’unique interprétation de la réalité est une autre question
• Les sinusoïdes étant très présentes dans la nature, les outils de la famille de Fourier conviennent bien à de nombreuses tâches, mais il est aussi possible de créer des domaines fréquentiels bien définis qui fonctionnent selon d’autres règles

Comprendre la DCT comme fonctions de base

• La transformée en cosinus discrète (DCT) peut être vue comme une version simplifiée, réelle uniquement, de la DFT
• La DCT-II calcule l’amplitude d’un bin de fréquence donné F_k en multipliant les valeurs d’entrée s_n par les valeurs d’une formule de cosinus donnée, puis en les additionnant
• L’élément clé est la fonction de base qui produit l’onde cosinus de la fréquence correspondant au numéro du bin DCT courant
• En généralisant, B(k, n) renvoie un multiplicateur en fonction de k et n, que l’on multiplie par les échantillons d’entrée avant de sommer
• Du point de vue logiciel, B(k, n) peut être vu comme un tableau de correspondance ; mathématiquement, comme une matrice
• Dans la matrice de base DCT avec N=16, la première ligne k=0 correspond à la composante DC à 0 Hz : c’est un cosinus dont toutes les valeurs valent +1.00
• Les lignes suivantes prennent la forme de cosinus qui varient de plus en plus vite : un demi-cycle, un cycle, un cycle et demi, etc.

Base d’ondes carrées et matrice de Walsh

• Une fonction de base qui découpe le signal non pas en fréquences sinusoïdales, mais en ondes carrées, peut être construite avec une matrice de Walsh
• La matrice de Walsh est composée d’ondes carrées évoluant à des vitesses différentes, et tous ses multiplicateurs valent +1 ou -1
• Le calcul se simplifie alors : il consiste à inverser le signe de certaines parties des données d’entrée, puis à les additionner
• Même une matrice qui paraît simple doit satisfaire deux conditions
  • Chaque ligne doit suivre l’ordre de sequency, avec une transition de signe de plus que la ligne précédente
  • Pour pouvoir passer proprement du domaine temporel à la représentation fréquentielle et inversement, il faut préserver l’orthogonalité
• Pour construire directement une matrice de Walsh, on part d’un tableau N×N, où N doit être une puissance de 2
  • On place +1 dans la première colonne de gauche pour toutes les lignes
  • On crée une nouvelle colonne comme une copie miroir des valeurs existantes, puis on divise la zone nouvellement ajoutée en plusieurs segments horizontaux et on inverse le signe de certains segments
  • À chaque itération, on copie les colonnes, on augmente le nombre de segments de lignes et on inverse les signes en alternance

Construire un tableau de Walsh à partir d’une matrice de Hadamard

• Dans la littérature et le code open source, il est fréquent de dériver le tableau de Walsh à partir d’une matrice de Hadamard plutôt que de le construire directement
• La matrice de Hadamard est une version de la matrice de Walsh dont l’ordre des lignes a été modifié
  • Par exemple, pour N=16, la ligne n° 15 de Walsh devient la n° 1 dans Hadamard, tandis que la ligne n° 1 de Walsh se trouve en n° 8
• Le fait que la construction de Hadamard soit apparue historiquement avant celle de Walsh, qui s’est appuyée dessus, explique en partie cet usage
• En pratique, les méthodes de construction d’une matrice de Hadamard sont mieux documentées, et il existe aussi des méthodes simples et efficaces par manipulation de bits
• La construction classique part d’un tableau 1×1 et copie la matrice précédente H_{n-1} en 4 tuiles
  • En haut à gauche, en haut à droite et en bas à gauche, on la copie telle quelle
  • En bas à droite, on inverse tous les signes
  • Cette extension s’écrit avec le produit de Kronecker ⊗, mais l’opération réelle consiste simplement à copier et inverser des signes
• Après n étapes de construction, la taille de la matrice de Hadamard est toujours 2^n × 2^n
• La valeur de Hadamard d’une cellule donnée peut être calculée en évaluant x & y, puis en regardant si le nombre de bits à 1 dans le résultat est pair ou impair
  • Si le nombre de bits à 1 est impair, la valeur est -1 ; s’il est pair, elle est +1
  • En C, cela s’implémente avec __builtin_popcount(x & y) % 2

Implémenter la transformée de Walsh-Hadamard

• Pour convertir une matrice de Hadamard vers l’ordre Walsh intuitif, il faut trier les lignes selon la sequency
• La méthode la plus simple consiste à compter le nombre de changements de signe sur chaque ligne
• D’autres méthodes de manipulation de bits sont possibles
  • On crée un code Gray en faisant un XOR entre le numéro de ligne Walsh et ce même numéro décalé de 1 bit vers la droite
  • On inverse l’ordre des n derniers bits pour calculer la correspondance vers la ligne Hadamard
• En remplaçant la base de l’implémentation DCT par le tableau de Walsh ainsi obtenu, on peut créer une « discrete square transform » et sa transformée inverse
• Techniquement, cette transformée est la transformée de Walsh–Hadamard (WHT)
• Si l’entrée d’exemple 1 1 1 1 5 5 5 5 est traitée par DCT, les composantes harmoniques se répartissent sur plusieurs bins de fréquence
  • DCT : +24.00 -10.25 -0.00 +3.60 +0.00 -2.41 -0.00 +2.04
• Si la même entrée est traitée avec la transformée en ondes carrées, seules F_0 et F_1 ont des composantes non nulles
  • SQFT : +24.00 -16.00 +0.00 +0.00 +0.00 +0.00 +0.00 +0.00
• La transformée inverse isqft() restaure l’entrée d’origine
  • ISQFT : +1.00 +1.00 +1.00 +1.00 +5.00 +5.00 +5.00 +5.00

Comparaison de spectrogrammes et positionnement pratique

• Un extrait audio de 11 secondes tiré de « DARE » de Gorillaz sert à comparer un spectrogramme DCT et un spectrogramme Walsh-Hadamard
• La transformée de Walsh-Hadamard est efficace à calculer même sur des ordinateurs peu performants et convient bien à certains types de données, ce qui lui vaut quelques usages de niche
• La conclusion n’est pas qu’il faudrait utiliser davantage la WHT, mais que la transformée de Fourier discrète n’a pas le monopole de la vérité
• Les spectrogrammes sont calculés avec DCT et WHT à partir d’un fichier audio mono à 44,1 kHz
  • La fenêtre d’échantillons d’entrée est 512
  • Le pas de transformation est 1
  • La taille du tableau de sortie est d’environ 512 × 485k
  • L’intensité des pixels applique un gamma d’environ 0.4 à la valeur absolue normalisée
  • Les images sont redimensionnées par rééchantillonnage Lanczos et rendues avec une colormap linéaire noir–bleu ciel–blanc
• Un exemple d’expérimentation de Walsh-Hadamard pour la compression d’images est également présenté : http://rotormind.com/blog/2019/hadamard-days-night/

[GN⁺]

Commentaires Hacker News

• Mathématiquement, la transformée de Fourier n’est qu’une façon d’exprimer un signal temporel dans une certaine base de vecteurs orthogonaux.
  Un vecteur de déplacement à la surface de la Terre peut aussi être exprimé dans une base nord/est, ou bien selon la direction d’une route et la direction qui lui est perpendiculaire.
  Les signaux dépendant du temps ou les « jolies » fonctions vivent dans des espaces vectoriels de dimension infinie, ce qui les rend difficiles à imaginer, mais les mathématiques essentielles fonctionnent de manière similaire.
  Dans la transformée de Fourier, les vecteurs de base sont des fonctions harmoniques, et le domaine fréquentiel est une sorte de « carte » qui montre le signal comme une combinaison d’une infinité de fonctions harmoniques.
  Des cartes fondées sur d’autres bases, comme la transformée de Walsh–Hadamard, sont tout aussi réelles, et la représentation dans le domaine temporel n’est elle aussi qu’une carte parmi d’autres, simplement plus familière.

  • C’est la bonne réponse, et j’ajouterais que la transformée de Fourier ne s’applique pas seulement aux signaux temporels, mais aussi aux fonctions continues par morceaux, dérivables et intégrables au sens de Dirichlet.
    Elle a de nombreuses applications : traitement d’images, résolution d’équations différentielles, multiplication rapide, etc.
    Mathématiquement, ces transformées sont sans perte : la fonction transformée contient exactement la même information que la fonction d’origine, et la transformée seule suffit à revenir à l’original.
    En ingénierie, on effectue souvent la transformée pour supprimer des informations indésirables, comme certaines composantes fréquentielles, ce qui brouille souvent ce point.
    Au final, ce n’est qu’un des nombreux points de vue possibles sur une fonction.
  • Avant, je pensais moi aussi en termes d’« autre base », mais aujourd’hui je trouve cette analogie un peu dangereuse, ou du moins incomplète.
    En particulier, dans les espaces multidimensionnels, la transformée de Fourier multidimensionnelle usuelle ne fonctionne correctement que lorsque cet espace possède une métrique plate.
    Quand on pense au fait que l’univers lui-même est courbe, cela ressemble à un signal d’alerte.
    Il y a eu récemment un travail intéressant généralisant les séries de Fourier à certains réseaux hyperboliques, avec pour résultat que l’espace de Fourier peut avoir une dimension plus élevée que l’espace des positions.
    En outre, la dimension de cet « espace de Fourier » dépend de la manière dont on discrétise le réseau : certains réseaux 2D peuvent avoir un domaine analogue aux fréquences en 4D, tandis que d’autres réseaux 2D peuvent avoir un domaine analogue en 8D.
    https://arxiv.org/abs/2108.09314 ou https://www.pnas.org/doi/full/10.1073/pnas.2116869119
  • Les astronomes d’autrefois croyaient à un modèle géocentrique de l’univers auquel ils ajoutaient des épicycles, et lorsqu’il fallait plus de précision, ils ajoutaient encore des épicycles.
    C’était un modèle complètement faux, mais en pratique, ils utilisaient en quelque sorte une série de Fourier comme approximateur de fonctions.
  • Je suis globalement d’accord, mais toutes les bases orthonormées décomposent le spectre de fréquences.
    Même en utilisant une base faite de polynômes, on finit par construire une fonction à partir de composantes fréquentielles.
    La base de Fourier est particulière en ce que chacun de ses éléments correspond à une fréquence donnée.
    Cela dit, chaque base est plutôt conçue pour un objectif précis, et un changement de base peut réorganiser le spectre d’une manière complexe à analyser.
    Dans ce cas, on analyse plutôt d’autres propriétés, comme la régularité.
    La plupart des fonctions qui nous intéressent ont un spectre caractéristique, mais la base de Fourier ne répond pas à toutes les questions.
  • Les vecteurs de base n’ont pas forcément besoin d’être perpendiculaires, si ?
    Comme nord et nord-est : tant qu’il y a une certaine composante orthogonale, on peut aussi exprimer [n, e] dans d’autres coordonnées.
    Les coefficients précis sont peut-être faux à cause des colonnes, mais l’essentiel est que c’est possible.

• Cela me rappelle une discussion devant un tableau blanc, quand j’étais en master, dans un groupe de systèmes dynamiques.
  « De l’énergie est injectée dans le système par la gauche, et elle est dissipée ici, à droite. »
  « Mais le système est invariant par rotation, donc il n’y a pas de gauche ni de droite. »
  « Je parlais dans l’espace des fréquences. »
  « Ah, je pensais que vous parliez de l’espace réel. »
  « Vous êtes idiot ? Qui pense dans l’espace réel ? »

  • Attendez, il y a une gauche et une droite dans l’espace des fréquences ?
    C’est une représentation abstraite, sans rapport direct avec la gauche, la droite, le haut et le bas des dimensions spatiales, non ?
  • Rien qu’avec tout le mépris que j’ai craché toute ma vie envers le monde académique dans sa tour d’ivoire, on pourrait sans doute alimenter un petit État insulaire pendant dix ans.
  • En master, vous vous traitez vraiment d’idiots entre vous, ou c’est largement romancé ?

• La base de Fourier est unique en ce que les fonctions de base exponentielles complexes sont les vecteurs propres des systèmes linéaires invariants dans le temps (LTI).
  Les autres transformées n’ont pas cette propriété.
  Beaucoup de systèmes réels — circuits, canaux de communication, antennes, etc. — sont LTI, et cette propriété fait que les signaux transmis à différentes fréquences n’interfèrent pas entre eux.
  C’est pourquoi la transformée de Fourier est plus largement utilisée que les autres transformées.
  En physique quantique aussi, il existe un lien où l’on utilise des paires de Fourier pour les fonctions d’onde de position et de quantité de mouvement, et les autres transformées n’ont pas cette propriété.

  • Je suis surpris que presque personne n’ait soulevé ce point.
    Avec une formation en génie électrique, on suppose souvent que beaucoup de systèmes sont linéaires, ou seulement très faiblement non linéaires, pour les analyser, et les signaux sont en général périodiques, donc la transformée de Fourier vient naturellement.
    La convolution devient une multiplication, et la dérivée temporelle d’une exponentielle complexe revient à multiplier par j*omega.
    Il vaut bien mieux faire des multiplications que des convolutions et des dérivées temporelles.
    Si l’on accepte l’idée que « l’on utilise la représentation de Fourier parce qu’elle est pratique dans certaines situations courantes », il n’y a rien d’étonnant à utiliser d’autres transformations mathématiques pour d’autres problèmes.
  • Techniquement, n’est-ce pas un cas particulier de la base de Laplace ?
    J’ai toujours trouvé étrange que beaucoup de cours ne traitent pas correctement la transformée de Laplace bilatérale la plus générale, et passent directement de la transformée de Fourier bilatérale à la transformée de Laplace unilatérale.
    https://en.wikipedia.org/wiki/Two-sided_Laplace_transform

• Si l’on me demande si c’est un « lieu réel », cela me rappelle une expérience d’optique d’autrefois
  Si l’on fait passer une image à travers quelques lentilles, on obtient un plan des fréquences, puis l’image est de nouveau projetée sur un écran en repassant par des lentilles
  Si l’on masque une partie de ce plan de fréquences, l’image change
  C’était extrêmement délicat à manipuler, et j’en ai gardé une grande reconnaissance envers le Dr Bruce Sinclair de St Andrew’s
  Le travail en laboratoire de physique permet de voir comment les choses fonctionnent, mais quand on revient à la théorie quelques mois après l’expérience, on se sent vite assez perdu

  • Le plan des fréquences ne se forme-t-il pas toujours ?
    C’est sans doute ainsi que l’ouverture limite la résolution, et que se produisent les aigrettes de diffraction dans les télescopes à réflexion
  • On peut aussi le faire en logiciel : https://imagemagick.org/Usage/fourier/#noise_removal
  • Le fait d’obtenir par l’optique une représentation dans le domaine fréquentiel est assez pratique dans diverses méthodes de microscopie et de spectroscopie fondées sur une source lumineuse
  • C’est de l’optique de Fourier
    La méthode Schlieren fonctionne aussi de cette manière

• Une autre généralisation intéressante de la DFT est la transformée de Lomb-Scargle
  Elle ne nécessite pas d’intervalle de mesure fixe dans le domaine temporel
  Elle est souvent utilisée pour trouver la fréquence de signaux périodiques lorsque les intervalles de mesure ne sont pas réguliers, comme en astrophysique
  https://iopscience.iop.org/article/10.3847/1538-4365/aab766 en donne une introduction générale, et https://docs.astropy.org/en/stable/timeseries/lombscargle.ht... présente bien son utilisation dans la bibliothèque Python astropy

  • Ces derniers temps, je me demande souvent s’il ne serait pas utile de représenter les données Prometheus dans le domaine fréquentiel pour visualiser les schémas d’accès hebdomadaires, quotidiens et annuels dans la planification de capacité
    L’autoscaling peut éviter des dégradations de performance liées à des incidents, mais il ne dit pas quel devrait être le budget annuel ni pourquoi
    Cela dit, les données Prometheus ne correspondent pas vraiment à un véritable intervalle d’échantillonnage
    Même si chaque machine du cluster remonte ses données à intervalles réguliers, elles ne sont pas synchronisées entre elles

• D’un autre point de vue, la cochlée peut être vue comme une implémentation « réelle » de la transformée de Fourier
  https://www.britannica.com/science/sound-physics/The-ear-as-...

  • La cochlée va plutôt dans le sens de l’argument de l’article
    Elle convertit bien vers le domaine fréquentiel, mais elle n’effectue pas, ni même n’approxime, une transformée de Fourier
    La transformation temps → domaine fréquentiel que la cochlée « implémente » ressemble davantage à une transformée en ondelettes
    Interpréter la cochlée comme une transformée de Fourier ressemble à l’erreur consistant à croire que les cônes de l’œil ne réagissent qu’aux lumières rouge, verte et bleue
    En réalité, chaque cellule réagit différemment sur une certaine plage de fréquences
    Les cônes ont un pic dans les domaines de basses, moyennes et hautes fréquences puis décroissent de part et d’autre, tandis que les cellules ciliées de la cochlée ont des courbes de réponse plus proches des ondelettes, avec un pic secondaire sur les harmoniques de la fréquence de pic
    Je ne suis pas spécialiste, seulement un amateur passionné, donc j’espère que quelqu’un de plus compétent me corrigera
  • Il est facile d’oublier à quel point la biologie est solidement enracinée dans la physique
    À l’université, nous avions un problème avec notre lignée de cellules souches qui se différenciaient en os ; il s’est avéré que la rigidité de l’environnement était un signal que les cellules souches pouvaient détecter
    En quelque sorte, la boîte de culture rigide disait aux cellules qu’elles devaient devenir des cellules osseuses

• L’article disait : « je ne connais pas d’algorithme plus élégant que compter les passages par zéro pour ordonner les lignes d’une matrice de Hadamard selon la sequency » ; en regardant la matrice et en devinant le motif, je suis tombé sur une méthode déjà connue
  D’après https://en.wikipedia.org/wiki/Walsh_matrix, l’ordre par sequency de la matrice de Walsh s’obtient en appliquant d’abord une permutation par inversion des bits à la matrice de Hadamard, puis une permutation par code de Gray

• L’article pose une question très générale et philosophique, mais affirme ensuite que, puisqu’on peut trouver d’autres bases et transformations orthogonales, le domaine fréquentiel n’a rien de très spécial
  Je pense pourtant que le domaine fréquentiel et la transformée de Fourier sont plus particuliers que beaucoup d’autres transformations
  Parce qu’on peut les observer directement dans la nature
  Par exemple, une lentille effectue la transformée de Fourier bidimensionnelle d’une image d’entrée transportée par une lumière parallèle, et on peut l’observer sur un écran
  On peut aussi mesurer la longueur d’onde ou la fréquence de la lumière en projetant la sortie d’un réseau ou d’un prisme sur un CCD, ce qui constitue également une mesure directe du domaine fréquentiel
  Des mesures similaires sont possibles avec les ondes RF

• Les sinusoïdes sont particulières en ce qu’elles sont des solutions naturelles de l’équation d’onde de Helmholtz
  Les ondes carrées posent aussi d’autres problèmes, comme une énergie infinie
  Cet article peut avoir du sens pour un mathématicien ou un informaticien, mais il passe à côté de la physique fondamentale du son et des ondes

  • Les sinusoïdes sont aussi particulières parce qu’elles sont des fonctions propres de l’opérateur de dérivation
    Les résultats physiques sont probablement une conséquence de cette propriété
    En fin de compte, l’un des grands enseignements des mathématiques modernes est qu’il est utile de regarder un objet sous plusieurs angles
  • C’est exact
    Un très grand nombre d’objets physiques sont des oscillateurs harmoniques, ce qui repose sur des bases assez fondamentales en physique
    Je peux penser à beaucoup d’autres situations où l’analyse de Fourier est utile, mais les sinusoïdes sont physiquement plus « réelles », et dire qu’on peut les exprimer dans n’importe quelle base relève davantage de la « validité »
    Le mot « réel » semble suggérer qu’il y a un véritable oscillateur derrière le phénomène
    Les ondes carrées sont moins physiques à cause des discontinuités du signal comme de sa dérivée, et la nature n’aime vraiment pas les discontinuités
  • Le domaine fréquentiel simplifie énormément les mathématiques dans les opérations linéaires invariantes dans le temps qui décrivent approximativement de nombreux systèmes présents dans la nature
    Par exemple, le phénomène de Gibbs apparaît naturellement dans la transformée de Fourier inverse d’une réponse fréquentielle qui met à zéro toutes les fréquences au-dessus d’une certaine fréquence de coupure
    Je me demande comment le domaine fréquentiel d’une onde carrée expliquerait le phénomène de Gibbs
    Peut-être que des harmoniques de la fréquence fondamentale de l’onde carrée apparaîtraient, comme si le système était non linéaire

• En étudiant la physique et les mathématiques au premier cycle, j’en suis arrivé à la conclusion que connaître les valeurs d’une fonction f(x) pour une infinité de x, et connaître les composantes fréquentielles de f pour une infinité de fréquences, est équivalent.
  Philosophiquement, les deux représentations sont tout aussi « réelles ».
  Certains problèmes sont simplement plus faciles à résoudre dans une représentation que dans l’autre.

  • Tout à fait d’accord.
    Passer du domaine temporel au domaine fréquentiel, c’est comme changer de système de coordonnées.
    Un signal comportant un seul pic étroit dans le domaine temporel peut être représenté de façon très petite et parcimonieuse par un delta à la position du pic, mais dans le domaine fréquentiel on n’obtient pas une représentation aussi compressée.
    À l’inverse, un signal sinusoïdal dans le domaine temporel n’y est pas compact, mais dans le domaine fréquentiel quelques deltas suffisent.
    Le temps et la fréquence sont deux façons de représenter la même chose ; selon les cas, un domaine est plus simple, et dans d’autres c’est l’inverse.
    On peut démontrer que ce qui est borné dans le domaine temporel devient non borné dans le domaine fréquentiel, et réciproquement.
    Ainsi, ce qui est compact dans un domaine s’étale toujours lorsqu’on passe à l’autre.
    En mécanique quantique, la position et la quantité de mouvement sont des variables conjuguées, comme le temps et la fréquence ci-dessus : si la position est bornée, la quantité de mouvement est non bornée, et réciproquement.
    C’est l’idée centrale du principe d’incertitude de Heisenberg.