Recuperación de soluciones Sparse usando métodos de optimización de puntos interiores

Abstract

RESUMEN: En este trabajo vamos a considerar la recuperación de soluciones sparse para sistemas de ecuaciones lineales indeterminados. Estudiaremos la unicidad de solución del problema. Para su resolución numérica plantearemos varias formulaciones de optimización y analizaremos sus propiedades teóricas. Aquellos problemas que involucren a la norma ǁ.ǁ1 serán resueltos mediante métodos de optimización de puntos interiores. Además presentaremos algunos resultados numéricos obtenidos con dos códigos: linprog (Optimization Toolbox, MATLAB) y l1eq_pd (l1-MAGIC). Se mostrará la influencia del escalamiento y de la aleatoriedad de la muestra en la solución recuperada. Algunos de los experimentos tratarán de la recuperación de una señal sonora.

ABSTRACT: In this work we are going to consider the sparse solution recovery for underdetermined systems of linear equations. We will study the uniqueness of the sparsest solution. For the numerical solution of the problem we will set out several optimization formulations and we will analyze their theoretical properties. Interior point optimization methods are used for solving those problems which involve the ǁ.ǁ1 norm. Moreover we will present some numerical results obtained with two codes: linprog (Optimization Toolbox, MATLAB) and l1eq pd (l1-MAGIC). We will also show the influence of the scaling and the random sampling on the recovered solution. Some of the experiments will be about signal recovery.