Adaptive matching pursuit using coordinate descent and double residual minimization

We present a greedy recursive algorithm for computing sparse solutions to systems of linear equations. Derived from adaptive matching pursuit, the algorithm employs a greedy column selection strategy which, combined with coefficient update via coordinate descent, ensures a low complexity. The sparsity level is estimated online using the predictive least squares (PLS) criterion. The key to performance is the minimization of two residuals, corresponding to two solutions with different sparsity levels, one for finding the values of the nonzero coefficients, the other for maintaining a large enough pool of candidates for the PLS criterion. We test the algorithm for a sparse time-varying finite impulse response channel; the performance is comparable with or better than that of the competing methods, while the complexity is lower.