Paper of the Day (Po’D): Implementations of Orthogonal Matching Pursuit Edition

Hello, and welcome to Paper of the Day (Po’D): Implementations of Orthogonal Matching Pursuit Edition. Today’s paper is my first of three submissions to 2012 EUSIPCO, and provides an overdue look at the numerical properties and performance characteristics of three implementations of orthogonal matching pursuit: B. L. Sturm and M. G. Christensen, “Comparison of Orthogonal Matching Pursuit Implementations“, submitted to EUSIPCO 2012, Bucharest, Romania, Aug. 2012. All the MATLAB code for reproducing the experiments and figures is here.

My one line summary of this paper is:

Wow, the QR implementation of OMP really cooks!

One impetus of this paper is to collect the various implementations of OMP that have been proposed and used (i.e., the QR and Cholesky implementation) since its “inception” in the signal processing community — elsewhere, in speech processing, it was known as a version of the “standard iterative algorithm,” and/or recursive modified Gram-Schmidt (see P. Dymarski, N. Moreau and G. Richard, “Greedy sparse decompositions: a comparative study”, EURASIP Journal on Advances in Signal Processing, Aug. 2011; Po’D here. And I think in the statistics community it is known as a type of “forward selection.” And now that I remembered that, I see this relevant paper: S. F. Cotter, J. Adler, B. D. Rao and K. Kreutz-Delgado, “Forward sequential algorithms for best basis selection,” IEEE Proc. Vision, Image, Signal Process., vol. 146, no. 5, pp. 235-244, 1999. The scan quality of the article makes it very hard to read.)
Anyway, we not only wanted to collect these different approaches, but also make their derivation as clear as possible.
We also propose a new variation based on the matrix inversion lemma, which theoretically scales more favorably than either the QR or Cholesky versions.
A second impetus was to study the numerical effects of making the various steps recursive.
We wanted to answer whether one implementation suffers more than another in its accumulation of numerical error.
Finally, we wanted to see how the three compare in terms of raw computation time.

What we conclude is that none of the algorithms suffer particularly bad error accumulation, that QR is slower than the others at first, but scales much better for larger problem sizes, and that though the implementation based on the matrix inversion lemma is supposedly completely linear in cost (compared to the others that are quadratic), a linear regression of its results reveals that it does have a quadratic component to it — probably due to the fact that applying big-O notation to multivariate algorithms makes strong assumptions that are not always true (see R. R. Howell, “On asymptotic notation with multiple variables”, Tech. Rep., Kansas State University, Jan. 2008).

In a previous entry, Stephen Becker commented that it would be interesting to compare with the Cholesky OMP implementation of the SPAM toolbox. I have downloaded this package and will see if it is any different from what we have.