Qu'est-ce que la transformée de Fourier clairsemée?

46

Le MIT a récemment fait du bruit au sujet d'un nouvel algorithme qui est présenté comme une transformation de Fourier plus rapide qui fonctionne sur des types de signaux particuliers, par exemple: " La transformation de Fourier plus rapide est nommée l'une des technologies émergentes les plus importantes au monde ". Le magazine MIT Technology Review déclare :

Avec le nouvel algorithme, appelé Sparse Fourier Transform (SFT), les flux de données peuvent être traités 10 à 100 fois plus rapidement qu'avec la FFT. L'accélération peut se produire car les informations qui nous intéressent ont une structure importante: la musique n'est pas un bruit aléatoire. Ces signaux significatifs n'ont généralement qu'une fraction des valeurs possibles qu'un signal pourrait prendre; le terme technique utilisé est que l'information est "rare". Comme l'algorithme SFT n'est pas conçu pour fonctionner avec tous les flux de données possibles, certains raccourcis peuvent ne pas être disponibles. En théorie, un algorithme ne pouvant traiter que des signaux épars est beaucoup plus limité que la FFT. Mais "la pauvreté est partout", souligne le co-inventeur Katabi, professeur d'électrotechnique et d'informatique. "C'est dans la nature; c'est ' s en signaux vidéo; c'est dans les signaux audio. "

Quelqu'un ici pourrait-il fournir une explication plus technique de ce qu'est réellement l'algorithme et de son applicabilité?

EDIT: Quelques liens:

nibot
la source

Réponses:

40

L'idée de l'algorithme est la suivante: supposons que vous ayez une longueur de signal clairsemée dans le domaine fréquentiel. Cela signifie que si vous deviez calculer sa transformée de Fourier discrète , il y aurait un petit nombre de sorties non nulles; les autres sont négligeables. Une façon d'obtenir les sorties souhaitées consiste à utiliser la FFT sur toute la séquence, puis à sélectionner les valeurs non nulles.NkNNkkk

L'algorithme de transformation de Fourier creuse présenté ici est une technique permettant de calculer les sorties avec une complexité inférieure à celle de la méthode basée sur la FFT. Essentiellement, étant donné que sorties sont nulles, vous pouvez économiser beaucoup d'efforts en prenant des raccourcis à l'intérieur de l'algorithme pour ne même pas générer ces valeurs de résultat. Alors que la FFT a une complexité de , l’algorithme à ressources rares a une complexité potentiellement inférieure à dans le cas du spectre à spectre épars.kNkO(nlogn)O(klogn)

Pour le cas plus général, où le spectre est "un peu maigre" mais où il existe plus de valeurs non nulles (par exemple, pour un certain nombre de sons incorporés dans le bruit), elles présentent une variante de l'algorithme qui estime les plus grands débits, avec une complexité temporelle de , qui pourrait également être moins complexe que la FFT.kkO(klognlognk)

Selon un graphique de leurs résultats (reproduit dans l'image ci-dessous), le point de croisement pour une performance améliorée par rapport à FFTW (une bibliothèque FFT optimisée, créée par d'autres gars du MIT) se situe autour du point où seul -th à -th des coefficients de transformation en sortie ne sont pas nuls. De plus, dans cette présentation, ils indiquent que l’algorithme sparse offre de meilleures performances lorsque .12111210Nk[2000,106]

entrez la description de l'image ici

Ces conditions limitent l'applicabilité de l'algorithme aux cas où vous savez qu'il y aura probablement peu de pics significativement grands dans le spectre d'un signal. Un exemple cité sur leur site Web est le fait qu'en moyenne, les blocs de pixels sur 8 utilisés sur la compression d'images et de vidéos sont rares à 90% dans le domaine fréquentiel et pourraient donc bénéficier d'un algorithme exploitant cette propriété. Ce niveau de parcimonie ne semble pas correspondre à l'espace applicatif de cet algorithme, il peut donc s'agir simplement d'un exemple illustratif.

Je dois lire un peu plus dans la littérature pour mieux comprendre à quel point une telle technique peut être utilisée dans des situations réelles, mais pour certaines classes d'applications, cela pourrait bien convenir.

Jason R
la source
2
C'est donc fondamentalement une FFT avec pertes? Vous aimez un encodeur MP3?
endolith
3
@endolith: Je ne suis pas sûr de pouvoir le dire ainsi. Peut-être plus analogue à un algorithme FFT élagué qui ne calcule qu'un sous-ensemble des sorties. L’affirmation est que si le signal d’entrée est -sparse, les sorties sont calculées exactement. kkk
Jason R
Je me demande comment il va contre l'algorithme de Goertzel (ou une famille d'entre eux). Il semble que la seule différence entre Goertzel et vous savez ce que vous cherchez pour commencer.
Spacey
5
@endolith: la compression MP3 entraîne des pertes car les coefficients sont quantifiés; non pas parce que seuls les k premiers coefficients sont conservés. FFT Clairs = "quelle est la représentation des k-coefficients minimisant la différence avec le signal d'entrée". Codage d'une trame mp3 = "quels sont les coefficients quantifiés et les niveaux de quantification qui minimisent l'erreur (perceptuelle) étant donné un budget de N bits pour stocker les coefficients et les facteurs d'échelle".
Pichenettes
1
Lorsqu'ils sont jetés, il s'agit d'un effet secondaire de la quantification (la valeur est arrondie à 0)
pichenettes
7

Je n'ai pas lu le document sur sFFT, mais mon sentiment est que l'idée d'attacher la FFT derrière exploite le précédent de k-sparsity. Par conséquent, il n'est pas nécessaire de calculer toutes les entrées de coefficients FFT, mais seulement k. C'est pourquoi, pour le signal k-sparse, la complexité est O (klog n) au lieu de O (nlog n) pour la FFT conventionnelle.

Quoi qu’il en soit, en ce qui concerne les commentaires de @rcmpton, en disant: "L’idée de la détection comprimée est qu’il est possible de récupérer des données éparses à partir d’échantillons aléatoires clairsemés tirés d’un domaine différent (p. Ex. Récupérer des images éparses à partir de données aléatoires à fréquence clairsemée (IRM)). . " La question est ce qui est "échantillons aléatoires clairsemés"? Je pense que cela pourrait être des échantillons collectés en projetant au hasard les données rares dans un sous-espace inférieur (de mesure).

Et, si j'ai bien compris, le cadre théorique de la détection en compression comprend principalement 3 problèmes: la parcimonie, la mesure et la récupération. Par rareté, il s'agit de rechercher des représentations éparses pour certaines classes de signaux, ce qui est la tâche de l'apprentissage par dictionnaire. Par mesure, il s’agit de rechercher un moyen efficace (efficacité de calcul et récupérable) de mesurer les données (ou de projeter des données dans un espace de mesure inférieur), tâche qui incombe à la conception d’une matrice de mesure, telle que matrice aléatoire gaussienne, matrice aléatoire structurée,. ... Et par reprise, les problèmes d'inversion linéaire régularisés, l0, l1, l1-l2, lp, groupe-l, blabla ..., sont rares, et les algorithmes obtenus sont variés, Poursuite de correspondance, seuillage progressif, seuillage rigide, poursuite de base, bayésienne, ....

Il est vrai que "cs est la minimisation de la norme L1" et que la norme L1 est un principe de base pour cs, mais que cs n’est pas seulement une minimisation de la norme L1. Outre les 3 parties ci-dessus, il existe également des extensions, telles que la détection compressive structurée (de groupe ou modèle), où la parcimonie structurée est également exploitée et qui améliore largement la capacité de récupération.

En conclusion, cs est une étape importante dans la théorie de l'échantillonnage, offrant un moyen efficace d'échantillonner des signaux, à condition que ces signaux soient suffisamment rares . Donc, cs est une théorie de l'échantillonnage , quiconque l'utilisera comme technique de classification ou de reconnaissance induit le principe en erreur. Et parfois, je trouve un article intitulé "Compression sensible basée sur .....", et je pense que le principe de ce papier exploite la minimisation l1 au lieu de cs et il vaut mieux utiliser "la minimisation l1 ...". ".

Si je me trompe, corrigez-moi s'il vous plaît.

Pierre
la source
Bienvenue sur DSP.SE C’est une contribution formidable.
Phonon
6

J'ai parcouru le journal et je pense avoir une idée générale de la méthode. Le "secret" de la méthode est de savoir comment obtenir une représentation fragmentée du signal d’entrée dans le domaine fréquentiel. Les algorithmes précédents utilisaient une sorte de force brute pour localiser le coefficient rare dominant. Cette méthode utilise à la place une technique appelée "récupération de l'espace" ou "compression comprimée" . Cet article du wiki se trouve ici. La méthode exacte de récupération clairsemée utilisée ici ressemble à la méthode du "seuillage brutal" - l'une des méthodes de récupération dominante dominante.

Technique PS de récupération creuse / détection comprimée et connectée à celle-ci La minimisation L1 a beaucoup utilisé dans le traitement du signal moderne et en particulier dans le cadre de la transformation de Fourier. En fait, il est indispensable de connaître le traitement du signal moderne. Mais auparavant, la transformation de Fourier était utilisée comme l'une des méthodes permettant de résoudre le problème de la récupération clairsemée. Nous voyons ici la récupération inverse de la transformation de Fourier.

Bon site pour une vue d'ensemble de la détection comprimée: nuit-blanche.blogspot.com/

Réponse de PPS à un commentaire précédent - si le signal d'entrée n'est pas parfaitement fragmenté, il y a perte.

N'hésitez pas à me corriger si je me suis trompé de méthode.

miroir2image
la source
Le papier FFT n'est pas une détection comprimée. L'idée sous-jacente à la détection comprimée est que vous pouvez récupérer des données clairsemées d'échantillons aléatoires clairsemés tirés d'un domaine différent (par exemple, récupérer des images clairsemées à partir de données aléatoires à fréquence clairsemée (IRM)). Bien que cela puisse réduire le temps d'acquisition, cela augmente les coûts de calcul. Le document FFT est différent en ce que vous avez toutes vos données dans les deux domaines et l’objectif est d’effectuer rapidement un calcul.
dranxo
Vous avez tort à propos de la détection comprimée.
mirror2image
1
Peux-tu élaborer?
dranxo
Détection comprimé est une vaste zone avec des bords flous, qui comprennent / connectées à non seulement la récupération en soi , mais des domaines similaires régularisation, activités de complexité minimale etc. Initialement ce problème contraint de parcimonie , x dans , R ^ n \ | x \ | _0 <k $, mais plus tard, il devient beaucoup plus brad. Commencez par lire le wiki A x = y R m Y i n , m > > n w i t h c o n s t r a i n tLpAx=yRmyin,m>>nwithconstraint
mirror2image
La détection comprimée signifie que vous résolvez sous . Il existe de nombreuses applications de grande portée, mais si vous n'invoquez pas le théorème de Candes-Romberg-Tao à un moment donné, vous confondez les gens si vous appelez votre travail «détection comprimée». Voici une référence: www-stat.stanford.edu/~candes/papers/spm-robustcs-v05.pdfmin|x|1Ax=y
dranxo