Error analysis of reweighted l1 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.