Efficient Implementation of the K-SVD Algorithm using Batch Orthogonal Matching Pursuit

The K-SVD algorithm is a highly effective method of training overcomplete dictionaries for sparse signal representation. In this report we discuss an efficient implementation of this algorithm, which both accelerates it and reduces its memory consumption. The two basic components of our implementation are the replacement of the exact SVD computation with a much quicker approximation, and the use of the Batch-OMP method for performing the sparse-coding operations. Batch-OMP, which we also present in this report, is an implementation of the Orthogonal Matching Pursuit (OMP) algorithm which is specifically optimized for sparse-coding large sets of signals over the same dictionary. The Batch-OMP implementation is…