Error analysis of reweighted l 1 greedy algorithm for noisy reconstruction

Sparse solutions for an underdetermined system of linear equations ? x = u can be found more accurately by l 1 -minimization type algorithms, such as the reweighted l 1 -minimization and l 1 greedy algorithms, than with analytical methods, in particular in the presence of noisy data. Recently, a generalized l 1 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 l 1 -minimization and l 1 greedy algorithms although the convergence has not yet been proven theoretically. In this paper, we provide an error bound for the reweighted l 1 greedy algorithm, a type of the generalized l 1 greedy algorithm, in the noisy case and show its improvement over the reweighted l 1 -minimization.