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
| Identifer | oai:union.ndltd.org:IBICT/oai:repositorio.ufrn.br:123456789/18645 |
| Date | 27 November 2012 |
| Creators | Silva, Catia Regina dos Santos |
| Contributors | CPF:23810270768, http://lattes.cnpq.br/2481613790501364, Nonato, Luis Gustavo, CPF:12918986895, http://lattes.cnpq.br/3794241680729178, Cohen, Nir, CPF:21402190824, http://lattes.cnpq.br/7895700958229353, Medeiros, Walter Eug?nio de, CPF:19980701404, http://lattes.cnpq.br/2170299963939072, Bielschowsky, Roberto Hugo |
| Publisher | Universidade Federal do Rio Grande do Norte, Programa de P?s-Gradua??o em Matem?tica Aplicada e Estat?stica, UFRN, BR, Probabilidade e Estat?stica; Modelagem Matem?tica |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Format | application/pdf |
| Source | reponame:Repositório Institucional da UFRN, instname:Universidade Federal do Rio Grande do Norte, instacron:UFRN |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.006 seconds