Recuperação de sinais esparsos. Investigação numérica sobre a quantidade de medidas necessárias para recuperar um sinal esparso

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior

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 à restrição Ax = b + r, sob determinadas condições (8). Vale dizer, com muito menos equações que incognitas. Dá o nome de Magica l1" para esta possibilidade de recuperar um sinal esparso, resolvendo um problema de otimizaçã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 à codificaçã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~oes 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 distribuição gaussiana i.i.d., de media zero e colunas aproximadamente unitarias. A segunda e a transformada de Fourier, que usaremos numa vers~ao de transformada de cossenos 2D. A denotamos por A = DCT. Para probabilidades esmagadoras" de sucesso na recuperaçã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 empíricos por nos obtidos para iv estas duas matrizes ainda s~ao muito preliminares, mas se ajustam bem , via quadrados míínimos, a m=s C log(s=N), com C em 1:6 e em 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~ao 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~ao 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