Error analysis of reweighted l¹ greedy algorithm for noisy reconstruction

Sparse solutions for an underdetermined system of linear equations Φx=u can be found more accurately by ^l1-minimization type algorithms, such as the reweighted ^l1-minimization and ^l1 greedy algorithms, than with analytical methods, in particular in the presence of noisy data. Recently, a generalized ^l1 greedy algorithm was introduced and applied to signal and image recovery. Numerical experiments have demonstrated the convergence of the new algorithm and the superiority of the algorithm over the reweighted ^l1-minimization and ^l1 greedy algorithms although the convergence has not yet been proven theoretically. In this paper, we provide an error bound for the reweighted ^l1 greedy algorithm, a type of the generalized ^l1 greedy algorithm, in the noisy case and show its improvement over the reweighted ^l1-minimization.