Fast $ell^1$-Greedy Algorithm for Sparse Solutions of Underdetermined Linear Systems

The algorithms for finding sparse solutions of underdetermined systems of linear equations will be compared. Among those algorithms Orthogonal Greedy Algorithm, $ell^1$ minimization, Re-weighted $ell^1$ minimization, $ell^1$-Greedy Algorithm will be discussed. We also present a new fast algorithm combining ideas of fast implementation of OGA and $ell^1$-Greedy Algorithm. The algorithm basic constructive block is one iteration of the standard interior-point linear programming algorithm. This algorithm combines computational complexity close to plain $ell^1$-minimization with the efficiency of the sparse representations recovery approaching to the efficiency of the $ell^1$-greedy algorithm.

Joint work with I. Kozlov