Ultimamente, o MIT está fazendo um pouco de barulho sobre um novo algoritmo que é apresentado como uma transformada de Fourier mais rápida que funciona em tipos específicos de sinais, por exemplo: " Transformada de Fourier mais rápida chamada uma das tecnologias emergentes mais importantes do mundo ". A revista MIT Technology Review diz :
Com o novo algoritmo, chamado de transformada esparsa de Fourier (SFT), os fluxos de dados podem ser processados 10 a 100 vezes mais rápido do que era possível com a FFT. A aceleração pode ocorrer porque as informações que mais nos interessam têm uma grande estrutura: a música não é um ruído aleatório. Esses sinais significativos geralmente têm apenas uma fração dos valores possíveis que um sinal pode receber; o termo técnico para isso é que as informações são "esparsas". Como o algoritmo SFT não se destina a funcionar com todos os fluxos de dados possíveis, ele pode usar certos atalhos que não estavam disponíveis. Em teoria, um algoritmo que pode lidar apenas com sinais esparsos é muito mais limitado que o FFT. Mas "a escarsidade está em toda parte", aponta Katabi, professor de engenharia elétrica e ciência da computação. "Está na natureza; é ' s em sinais de vídeo; está em sinais de áudio ".
Alguém aqui poderia fornecer uma explicação mais técnica sobre o que realmente é o algoritmo e onde ele pode ser aplicável?
EDIT: Alguns links:
- O artigo: " Transformada de Fourier esparsa quase ideal " (arXiv) de Haitham Hassanieh, Piotr Indyk, Dina Katabi, Eric Price.
- Site do projeto - inclui implementação de amostra.
fonte
Eu não li o artigo sobre o sFFT, mas meu sentimento é que a ideia de prender a FFT por trás está explorando o prior da k-sparsity. Portanto, não é necessário calcular todas as entradas dos coeficientes da FFT, apenas computar k deles. É por isso que, para o sinal k-sparse, a complexidade é O (klog n) em vez de O (nlog n) para FFT convencional.
De qualquer forma, com relação aos comentários do @rcmpton, dizendo "A idéia por trás do sensor compactado é que você pode recuperar dados esparsos de amostras aleatórias esparsas extraídas de um domínio diferente (por exemplo, recuperar imagens esparsas de dados aleatórios de frequência esparsa (ou seja, MRI)) . " A questão é o que são "amostras aleatórias esparsas"? Eu acho que podem ser amostras coletadas projetando aleatoriamente os dados esparsos para algum subespaço inferior (de medição).
E, como eu entendi, o arcabouço teórico do sensor de compressão é composto principalmente por três questões: escassez, medição e recuperação. Por esparsidade, refere-se à busca de representações esparsas para determinada classe de sinais, que é a tarefa do aprendizado de dicionário. Por medição, refere-se a buscar uma maneira eficiente (eficiência computacional e recuperável) de medir os dados (ou projetar dados para diminuir o espaço de medição), que é a tarefa do design da matriz de medição, como matriz gaussiana aleatória, matriz aleatória estruturada. ... E por recuperação, são os problemas de inversão linear regularizada esparsa, l0, l1, l1-l2, lp, l-group, blabla ..., e os algoritmos resultantes são vários: busca de correspondência, limiar suave, limiar rígido, busca de base, bayesiana, ....
É verdade que "cs é minimização da norma L1", e a norma L1 é um princípio básico para cs, mas cs não é apenas minimização da norma L1. Além das três partes acima, também existem algumas extensões, como detecção compressiva estruturada (grupo ou modelo), em que a esparsidade estruturada também é explorada e comprovadamente melhora bastante a capacidade de recuperação.
Como conclusão, cs é um grande passo na teoria da amostragem, fornecendo uma maneira eficiente de amostrar sinais, desde que esses sinais sejam escassos o suficiente . Portanto, cs é uma teoria de amostragem , qualquer pessoa que a utilize como alguma técnica de classificação ou reconhecimento está enganando o princípio. E, ocasionalmente, encontro algum artigo intitulado "compressão baseada em sensoriamento .....", e acho que o princípio desse artigo é explorar a minimização de l1 em vez de cs e é melhor usar "a minimização de l1 ... "
Se eu estiver errado, me corrija, por favor.
fonte
Examinei o artigo e acho que entendi a idéia geral do método. O "segredo secreto" do método é como obter uma representação esparsa do sinal de entrada no domínio da frequência. Os algoritmos anteriores usaram o tipo de força bruta para a localização do coeficiente esparso dominante. Em vez disso, esse método usa a técnica que chamou de artigo da wiki "recuperação de espaço" ou "detecção compactada". O método exato de recuperação esparsa usado aqui é semelhante ao 'hard thresholding "- um dos métodos dominantes de recuperação esparsa.
A técnica PS de recuperação esparsa / detecção compactada e conectada a ela, a minimização de L1, utilizou muito no processamento moderno de sinais e principalmente em conexão com a transformada de Fourier. De fato, é necessário conhecer o processamento moderno de sinais. Porém, antes da transformação de Fourier ser usada como um dos métodos para solução do problema de recuperação esparsa. Aqui vemos oposto - recuperação escassa para transformada de Fourier.
Bom site para visão geral do sensor compactado: nuit-blanche.blogspot.com/
O PPS responde ao comentário anterior - se o sinal de entrada não for exatamente esparso, será perdido.
Fique à vontade para me corrigir se eu entendi errado o método.
fonte