| Summary: | Nesta dissertação apresentaremos novos resultados ligados ao uso de um algoritmo ganancioso, o dito Orthogonal Matching Pursuit (OMP), por forma a resolvermos problemas de aproximação esparsa em dicionários redundantes. Discutiremos, igualmente, uma modificação deste algoritmo, devida a Donoho, chamada Basis Matching Pursuit (BP). Apresentaremos uma condição (única) que assegura que ambos, OMP e BP, permitem recuperar sinais esparsos de forma exacta. Mais, mostraremos que ambos os algoritmos permitem efectuar a recuperação do sinal para uma vasta classe de dicionários. Com efeito, neste trabalho faremos um resumo de vários resultados recentes em BP, facilmente extensíveis ao caso de OMP. Adicionalmente, daremos também uma condição suficiente de garantia de que OMP pode recuperar átomos comuns a partir de todas as representações óptimas de um sinal não-esparso. Assim, OMP pode ser visto como um algoritmo de aproximação para o problema esparso num dicionário quasi-incoerente , isto é, para qualquer sinal dado, OMP permite calcular uma aproximação esparsa cujo erro não é muito pior do que o erro óptimo, e isto para o mesmo número de termos na aproximação.
|
|---|