A fast orthogonal matching pursuit algorithm

Abstract

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 importance in many areas including image and video coding, image analysis, control theory, and statistics. Finding the optimal solution in the general case is mathematically intractable. Matching pursuit, and its orthogonal version, provide greedy solutions to this problem. Orthogonal matching pursuit typically provides significantly 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 a computational complexity very close to that of the nonorthogonal version.