Home          
 
Short Presentations Accepted
 
 
     A Path Following for Solving l_1-underdetermined Problems and its Applications in Signal Processing
     Presenter: Miguel Argaez
     Co-Authors: Reinaldo Sanchez & Carlos Ramirez
Abstract

In this work, we consider a homotopic principle for solving large-scale and dense l_1 underdetermined problems. The idea consists of obtaining the solution of the problem by solving a sequence of linear equality constrained multiquadratic problems that depend of a perturbed parameter that converges to zero. The procedure generates a central path that converges to a point on the solution set of the l1-underdetermined problem. This allows to mimic the path-following methodology for primal-dual interior-point methods. To obtain inexact directions associated to the KKT conditions, a fixed-point conjugate gradient method is implemented. To prevent the algorithm from becoming quite expensive, a measure of closeness to the central path is provided. The perturbed parameter is implemented in the same fashion as it is done in interior-point methods. To this end, we characterize the complementarity variables associated to the primal variables of the problem. We present a numerical result to recover sparse signals for some large scale problems, and compare our results with some state-of-the-art algorithms. Finally, we implement our algorithm successfully in some seismic reflection problems.

 

SDSU: Computational Science and Engineering Gateway to Latin America

Last updated: May 5, 2010 3:41 PM