Le MIT dévoile une transformation de Fourier très très rapide !

Des chercheurs du MIT ont découvert une méthode pour calculer la transformation de Fourier encore plus rapidement qu’avec la vénérable Transformation de Fourier Rapide (ou « FFT »). Des gains typiques de 10x sont évoqués, avec à la clef des réductions d’autant du temps de calcul ou de l’énergie consommée, ouvrant la voie a un traitement du signal plus fin sur terminaux mobiles.

Aujourd’hui, on va parler mathématiques. Bon, ça, c’est fait : je viens de perdre les trois quarts de mon lectorat potentiel. Ceux qui restent seront ravis d’apprendre qu’on va parler de la transformation de Fourier. Non, M. Fourier ne se transforme pas en Super Sayen, cet honorable mathématicien français a simplement beaucoup travaillé sur la propagation de la chaleur, ce qui amène des équations pas commodes à résoudre. Plutôt que d’essayer de les affronter directement, il invente un moyen de simplifier les choses en les décrivant différemment, en changeant de point de vue en quelque sorte. Ce point de vue nouveau, cette « transformation » va tout bonnement devenir le couteau suisse d’une bonne partie des mathématiques et de l’ingénierie moderne. Alors que des chercheurs du MIT viennent de donner un coup de jeune à cette vénérable transformation, c’est l’occasion d’un petit dossier pour essayer de voir d’un peu plus près (mais pas trop) de quoi il s’agit.

La transformation de Fourier s’applique à des « signaux » périodiques, c’est-à-dire qui se répètent toujours de la même façon à intervalles réguliers. Bon, si votre signal n’est pas périodique, vous n’avez qu’à faire comme si vous le répétiez indéfiniment. Un signal périodique peut être simple, comme celui de la figure 1, ou plus tarabiscoté, comme celui de la figure 2.

Le génie de Fourier, c’est d’avoir remarqué qu’on pouvait décrire ce signal tarabiscoté comme la superposition de plusieurs signaux simples (figure 3). Ces signaux « de base », sont des sinusoïdes (sinus ou cosinus) dont la fréquence est un multiple de celle du signal considéré, qui est dite « fondamentale ». En effet, si vous regardez attentivement la figure 3, vous verrez que le graphique correspondant au second terme de la somme comporte trois fois plus d’oscillations que le premier terme, et que le dernier terme en comporte quatre fois plus.

Savoir quelles sont les fréquences (dites « harmoniques ») qui participent au signal à analyser et dans quelles proportions elles le font, c’est en faire sa transformée de Fourier. Ce changement de point de vue simplifie beaucoup les choses, puisque seuls six nombres (dont trois entiers) sont finalement nécessaires à la description d’un signal, pas forcément très avenant au premier abord.
L’idée est donc la suivante, on prend un signal en entrée et on passe de la description en fonction du temps à la description « en fréquence », ce que l’on appelle le spectre. Vous voyez le spectre d’un signal audio (enfin, une simplification) assez souvent si vous êtes adepte de certaines  visualisations Windows Media Player ou Winamp (oui, il existe toujours…) par exemple. Les applications sont infinies, de la reconnaissance vocale à la compression de données, le MP3 pouvant se résumer à une sorte « d’écrémage » du spectre, on y reviendra.

Mais au fait, c’est compliqué de faire une transformation de Fourier ? En règle générale: oui, plutôt. La technique de base consiste à « confronter » le signal à chaque harmonique potentielle pour en déduire dans quelle proportion elle y contribue. C’est assez long. Supposons que vous ayez un signal de 1024 échantillons. Et bien il vous faudra de l’ordre d’un million d’étapes de calcul pour arriver à vos fins en utilisant la transformée de Fourier discrète. La complexité de l’algorithme est O(n²), c’est-à-dire que si vous avez « n » échantillons vous aurez besoin de l’ordre de n² (n x n) étapes de calculs. Mais n², ça croit très vite, pour une résolution 4 fois plus fine, c’est 16 fois plus de calculs qui seront nécessaires. Du coup, en pratique, ça devient vite ingérable.
Heureusement, pour des raisons de symétries difficiles à expliquer sans formules, il existe une méthode pour calculer la transformée de Fourier beaucoup plus vite, si n est une puissance de 2. C’est ce que l’on appelle la transformée de Fourier rapide ou FFT pour « Fast Fourier Transform ». Mise au point dans les années 60, sa complexité est O(n log (n) ). Or le logarithme est une fonction à croissance très lente, ce qui fait bien nos affaires ! Munissons-nous de nos calculettes (scientifiques) pour comparer le nombre d’étapes de calcul de la méthode de base et de la transformation rapide pour un signal de 4096 échantillons (par exemple). D’un côté, avec mon O( n² ), j’ai 4096² = 16 777 216 étapes. Avec la FFT, j’ai 4096 x log (4096) soit environs 34 097 étapes. Ça change tout ! C’est grâce à cette méthode qu’un traitement fin des signaux peut être fait même sans le secours d’un super-ordinateur !
Car qui dit réduction du temps de calcul, dit aussi réduction de l’énergie consommée, ce qui est crucial pour les appareils mobiles. À tel point, que la recherche en mathématiques sur les meilleures manières de calculer les transformations de Fourier continue. C’est dans ce contexte que le récent travail des mathématiciens du MIT prend toute son importance. On a vue que pour gagner du temps avec la FFT, on était obligé de ne traiter que des signaux d’une longueur égale à une puissance de 2 (8, 16, 32, 64 etc.). En faisant d’autres concessions, est-il possible de gagner davantage de temps ?

C’est ce qu’ont réussi les chercheurs pour les signaux à spectre « creux » (« sparse » en anglais). Schématiquement, on dit qu’un spectre est « creux » s’il ne contient pas beaucoup de fréquences. L’exemple ci-dessus, avec ses trois fréquences (fondamental compris) était bien sûr creux. Et en général ? Revenons un instant sur la compression MP3. Le principe est assez simple, on prend la transformée de Fourier du signal sonore et on élimine du spectre ainsi obtenu les fréquences auxquelles l’oreille humaine est la moins sensible. Vu la différence de taille entre un fichier wav et mp3, vous vous doutez que l’écrémage est assez sévère. Pourtant, à l’écoute, vous n’entendez presque aucune différence. C’est qu’un signal sonore « typique » ne contient finalement que peu de fréquences vraiment utiles. Il existe un signal sonore (idéal) contenant toutes les fréquences possibles, c’est le « bruit blanc ». Vous en entendez une approximation quand votre radio FM ne capte rien ou bien est entre deux stations. C’est un bruit fort peu mélodieux, bien différent du son d’une voix ou d’une musique. Ces derniers signaux sont bien plus structurés, et donc, paradoxalement bien plus simples à décrire. Cette simplicité est reflétée par un spectre assez maigre. Tout ça pour dire que finalement, la plupart des signaux de la vie quotidienne, ont des spectres « creux ». Ainsi, la concession faite pour gagner encore plus de temps n’est pas si méchante.
Pour être un petit peu plus précis, les chercheurs du MIT ont présenté au SODA (Symposium Of Discrete Algorithm) un algorithme permettant de calculer la transformation de Fourier 10 fois plus efficace que la FFT, et peut-être plus encore, selon les signaux.
On dit qu’un signal est « k – creux » si le nombre de fréquences (qui contribuent au signal) est plus petit ou égal à « k ». Notre exemple ci-dessus était donc 3-creux, marrant le vocabulaire des matheux non ? Si on suppose que notre signal comporte « n » échantillons et est « k – creux », avec donc k plus petit que n, alors la complexité de la  nouvelle méthode est O(k log (n) ) ou lieux de O(n log (n) ). La méthode est donc d’autant plus efficace que le spectre est plus creux. La bonne nouvelle, c’est qu’en pratique k croît moins vite que n. Là encore, imaginons le son d’un violon. Au plus le nombre d’échantillons « n » est grand, au plus le son du violon est précis et net, mais c’est toujours un violon avec un spectre de violon ! Donc le nombre de fréquences significatives reste à peu près le même.

La méthode utilisée est originale, puisqu’elle est itérative et utilise des filtres pour trouver les fréquences. Comme on suppose que ces dernières sont peu nombreuses, elles doivent être isolées. On coupe alors le spectre en petits morceaux et on recherche rapidement à l’intérieur de chacun la fréquence la plus grande qu’il contient. Ensuite, on retire les fréquences trouvées du signal d’origine et on réitère le processus pour trouver les suivantes.
Cette méthode ouvre la voie à des analyses de signaux très fines et peu couteuses en temps de calcul. Les applications sont infinies : compression audiovisuelle, analyse de forme, reconnaissance vocale, etc. Le tout à la portée des processeurs et des batteries de tablettes ou de téléphones portables.
En conclusion, le progrès technologique ne se résume pas à l’accroissement du nombre de cœurs ou des gigahertz, les progrès scientifiques en général, et en mathématiques en particulier en sont le premier moteur. Si vous vous demandez encore à quoi peuvent bien servir vos cours de math, pensez-y : sans Fourier, pas de jpeg, pas de mp3, pas de compression vidéo. Bonne chance pour stocker un film en HD sur un Bluray !

Source