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:
- Le document: " Transformation de Fourier clairsemée presque optimale " (arXiv) par Haitham Hassanieh, Piotr Indyk, Dina Katabi et Eric Price.
- Site Web du projet - comprend un exemple de mise en œuvre.
la source
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.
la source
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.
la source