Recuperação de sinais esparsos : investigação numérica sobre a quantidade de medidas necessárias para recuperar um sinal esparso /
Resumo: Um dos temas mais populares no tratamento de dados nos últimos dez anos gira em torno da descoberta que a recuperação de sinais esparsos em sistemas lineares, pode ser feita com um número de equações bem menor que o número de variáveis. Em linhas gerais, se A = AmN, queremos resolver Ax = b...
Na minha lista:
| Principais autores: | , , |
|---|---|
| Formato: | Dissertação |
| Publicado em: |
|
| Assuntos: | |
| Endereço do item: | http://repositorio.ufrn.br:8080/jspui/handle/123456789/18645 |
| Tags: |
Adicionar Tag
Sem tags, seja o primeiro a adicionar uma tag!
|
| Resumo: | Resumo: Um dos temas mais populares no tratamento de dados nos últimos dez anos gira em torno da descoberta que a recuperação de sinais esparsos em sistemas lineares, pode ser feita com um número de equações bem menor que o número de variáveis. Em linhas gerais, se A = AmN, queremos resolver Ax = b e procuramos soluções esparsas, ou seja, com apenas s << N entradas n~ao-nulas em algum sistema de coordenadas, isto pode ser feito com um número de equações m << N, minimizando a norma l1 de x, sujeito a restrição Ax = b + r, sob determinadas condições (8). Vale dizer, com muito menos equações que incognitas. Da o nome de Magica l1" para esta possibilidade de recuperar um sinal esparso, resolvendo um problema de otimizacão convexa com relativamente poucas restrições. Para algumas poucas matrizes A, de grande importância em aplicações, ha teorias razoavelmente estabelecidas indicando esta possibilidade, para muitas não. O objetivo desta dissertação e situar e discutir casos nos quais a Magica l1" funciona, com foco nas relações entre a esparsidade s, o número de linhas m e o número de variáveis N, para algumas matrizes importantes e associadas a codificacão de imagens 2D. Em particular, realizamos testes numéricos com três matrizes A, visando encontrar empiricamente relações entre s, m e N para as quais a Magica l1 e bem sucedida. Em duas delas, ha teorias matematicas, ainda em construção, indicando condicões de sucesso, grosso modo, na forma de m=s C log(N=s), sempre com alguma probabilidade de insucesso associada. Listamos inicialmente A = G, formada por entradas aleatorias com distribuic~ao gaussiana i.i.d., de media zero e colunas aproximadamente unitarias. A segunda e a transformada de Fourier, que usaremos numa versão de transformada de cossenos 2D. A denotamos por A = DCT. Para probabilidades esmagadoras" de sucesso na recuperacão de sinais esparsos com G, usando a Magica l1", os resultados teóricos estabelecem regiões menores, vale dizer, valores mais elevados para a constante C. Se relaxamos um pouco esta exigência de sucesso, obtemos regiões mais amplas, conforme teremos oportunidade de discutir na dissertação. m=s C log(N=s) ainda e uma conjectura no caso de Fourier, se queremos probabilidades esmagadoras" de sucesso na recuperação de sinais esparsos pela via da otimização convexa acima prescrita. Os resultados empricos por nos obtidos para iv estas duas matrizes ainda são muito preliminares, mas se ajustam bem , via quadrados mínimos, a m=s C log(s=N), com C 1:6 e 1, correspondendo aos resultados mais otimistas encontrados na literatura para G e DCT, nos quais a eficacia da Magica l1" e assumida num sentido mais fraco, no sentido de permitir alguma taxa de insucesso n~ao totalmente desprezível, porem de forma probabilisticamente controlada. No caso da matriz da transformada de Radon, não ha previsão teorica consolidada para o funcionamento daMagica l1" e sequer encontramos conjecturas sobre o que se pode esperar. Em nossos testes com matrizes de Radon, encontramos uma região para a validade da Magica l1", cujo ajuste de quadrados mínimos a m=s C log(s=N) se deu com 2; 5 e C 0; 29 .#$&Abstract: |
|---|