Qual é a transformada esparsa de Fourier?

46

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:

nibot
fonte

Respostas:

40

NkNNkkk

kNkO(nlogn)O(klogn)

kkO(klognlognk)

12111210Nk[2000,106]

insira a descrição da imagem aqui

Essas condições limitam a aplicabilidade do algoritmo a casos em que você sabe que é provável que haja poucos picos significativamente grandes no espectro de um sinal. Um exemplo que eles citam em seu site é que, em média, 8 por 8 blocos de pixels freqüentemente usados ​​na compactação de imagens e vídeos são quase 90% escassos no domínio da frequência e, portanto, podem se beneficiar de um algoritmo que explora essa propriedade. Esse nível de escarsidade não parece corresponder ao espaço de aplicação para esse algoritmo específico, portanto pode ser apenas um exemplo ilustrativo.

Preciso ler um pouco mais a literatura para ter uma idéia melhor de como essa técnica é prática para uso em problemas do mundo real, mas, para certas classes de aplicativos, pode ser adequada.

Jason R
fonte
2
Então é basicamente um FFT com perdas? Como um codificador de MP3?
Endolith
3
kk
Eu me pergunto como isso vai contra o algoritmo Goertzel (ou uma família deles). Parece que a única diferença é que, no goertzel, você sabe o que está procurando para começar.
Spacey
5
@ endolith: a compactação do MP3 está com perdas porque os coeficientes são quantizados; não porque apenas os principais coeficientes k sejam mantidos. FFT esparsa = "qual é a representação dos coeficientes k minimizando a diferença com o sinal de entrada". Codificação de um quadro mp3 = "quais são os coeficientes quantificados e os níveis de quantização que minimizam o erro (perceptivo) dado um orçamento de N bits para armazenar os coeficientes e os fatores de escala".
pichenettes
1
Quando eles são deitados fora, isto é um efeito colateral de quantização (o valor é arredondado para 0)
pichenettes
7

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.

Pierre
fonte
Bem-vindo ao DSP.SE Esta é uma grande contribuição.
Phonon 6/03/03
6

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.

mirror2image
fonte
O papel FFT não está com sensor compactado. 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 (por exemplo, ressonância magnética)). Embora isso possa reduzir o tempo de aquisição, aumenta o custo computacional. O documento da FFT é diferente, pois você tem todos os seus dados nos dois domínios e o objetivo é fazer com que a computação aconteça rapidamente.
Dranxo 18/05/12
Você está errado sobre a detecção compactada.
Mirror2image
1
Você pode elaborar?
dranxo
LpAx=yRmyin,m>>nwithconstraint
mirror2image
min|x|1Ax=y