Alexander Petoukhov (joint work with Inna Kozlov)
Title: l^1 greedy algorithm for finding solutions of underdetermined linear systems.
Abstract: Finding sparse solutions of undedetermined systems Ax=b is a hot topic of the last years. Many
problems of information theory (data compression, error correcting
codes, compressed sensing, etc) can be reformulated in terms of this problem.
We are gointg to discuss different apprlications of this problem
and to present a new algorithm solving the problem for wider range of
the input data. The known algorithms are represent
two competing classes: l^1 minimization and orthogonal greedy
methods. Our
new algorithm, essentially based on reweighted l^1 minimization (by
E.Candes, M.Wakin and S.Boyd), may serve as "a peace agreement" between
the two competing approaches. The algorithm outperporms the reweighted l^1 optimization by about 10%.