al.: A fast orthogonal matching pursuit algorithm

The problem of optimal approximation of members of a vector space by a linear combination of members of a large overcomplete library of vectors is of impor-tance in many areas including image and video coding, image analysis, control theory, and statistics. Finding the optimal solution in the general case is mathemat-ically intractable. Matching pursuit, and its orthogo-nal version, provide greedy solutions to this problem. Orthogonal matching pursuit typically provides signif-icantly better solution compared to the nonorthogonal version, but requires much more computation. This paper presents a fast algorithm for implementation of orthogonal matching pursuit which for many coding applications has computational complexity very close to that of the nonorthogonal version. 1