Made available in DSpace on 2015-03-03T15:28:33Z (GMT). No. of bitstreams: 1 CatiaRSS_DISSERT.pdf: 4951076 bytes, checksum: 0231a1261bda878faaaf3e30a97857a0 (MD5) Previous issue date: 2012-11-27 / 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