Utilize este identificador para referenciar este registo:
http://hdl.handle.net/10773/9787
Título: | Representações esparsas de sinais e algoritmos gananciosos |
Autor: | Costa, Célia Maria Gomes Pereira da |
Orientador: | Kähler, Uwe |
Palavras-chave: | Matemática Aproximações (Matemática) Processamento de sinal |
Data de Defesa: | 2008 |
Editora: | Universidade de Aveiro |
Resumo: | 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. This dissertation presents new results regarding the usage of a greedy algorithm, the so-called Orthogonal Matching Pursuit (OMP), in order to solve sparse approximation problems over redundant dictionaries. We also discuss a modification of this algorithm, due to Donoho, denoted Basis Matching Pursuit (BP). We present a single sufficient condition under which both OMP and BP can recover a sparse signal in an exact way. Moreover, it is shown that both algorithms allow such a recovering for a wide class of dictionaries. Indeed, in this work we give several recent results on BP which can easily be extended to OMP. Furthermore, we also give a sufficient condition under which OMP can retrieve the common atoms from all optimal representations of a non-sparse signal. Thus, OMP can be viewed as an approximation algorithm for the sparse problem over a quasi-incoherent dictionary, that is, for every input signal, OMP can calculate a sparse approximation whose error is only a small factor worse than the optimal error, and this done with same the same number of terms in the approximation. |
Descrição: | Mestrado em Matemática |
URI: | http://hdl.handle.net/10773/9787 |
Aparece nas coleções: | UA - Dissertações de mestrado DMat - Dissertações de mestrado |
Ficheiros deste registo:
Ficheiro | Descrição | Tamanho | Formato | |
---|---|---|---|---|
tese_Celia.pdf | 839.25 kB | Adobe PDF | Ver/Abrir |
Todos os registos no repositório estão protegidos por leis de copyright, com todos os direitos reservados.