Orientadores: Daniela Renata Cantane, Aurelio Ribeiro Leite de Oliveira

Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matemática Estatística e Computação Científica

Resumo: Vários são os métodos propostos para reconstrução de sinal. Nosso enfoque é o método Basis Pursuit. Trabalhando com dicionários overcomplete, são inúmeras as combinações possíveis para a representação do sinal. Basis Pursuit encontra a mais esparsa, porque minimiza a soma dos módulos dos...

Resumo: Vários são os métodos propostos para reconstrução de sinal. Nosso enfoque é o método Basis Pursuit. Trabalhando com dicionários overcomplete, são inúmeras as combinações possíveis para a representação do sinal. Basis Pursuit encontra a mais esparsa, porque minimiza a soma dos módulos dos coeficientes da combinação, ou seja, minimiza os coeficientes na norma 1. Veremos que podemos reescrever o problema em questão como um problema de programação linear. Apresentaremos um método já existente para a resolução deste problema, o Método Primal-Dual Barreira Logarítmica. Em um primeiro momento, vamos aplicar o Método Barreira Logarítmica, e buscando maior eficiência, iremos incluir a direção afim-escala, a direção de centragem e a direção de correção no mesmo método, obtendo o Método Primal-Dual Barreira Logarítmica Preditor- Corretor, além de implementar uma variação deste. Resultados computacionais com problemas reais comprovam a eficiência do método proposto

Abstract: There are many proposed methods for signal reconstruction. However, our focus is on the Basis Pursuit method. When working with overcomplete dictionaries, there exist countless possible combinations to represent the signal. Basis Pursuit finds the sparsest, because it minimizes the sum of...

Abstract: There are many proposed methods for signal reconstruction. However, our focus is on the Basis Pursuit method. When working with overcomplete dictionaries, there exist countless possible combinations to represent the signal. Basis Pursuit finds the sparsest, because it minimizes the sum of the combination coefficients absolute values, i.e., it minimizes the coefficients on norm 1. We will see that the problem in question can be rewritten as a linear programming problem. An existing method is shown for the solution of this problem, the Primal-Dual Logarithmic Barrier Method. Initially, we will apply the Logarithmic Barrier Method, and seeking higher efficiency, we will include the affine scaling direction, the centering direction and the nonlinear correction direction in the same method, obtaining the Predictor-Corrector Primal-Dual Logarithmic Barrier Method, of which a variation is also implemented. Computational results with real life problems show the efficiency of the proposed method