|
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.
|