Technical Report CS-2008-08

Title: Efficient Implementation of the K-SVD Algorithm using Batch Orthogonal Matching Pursuit
Authors: Ron Rubinstein, Michael Zibulevsky, and Michael Elad
PDF - RevisedCS-2008-08.revised.pdf
Abstract: 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 useful for a variety of sparsity-based techniques which involve coding large numbers of signals. In the report, we discuss the Batch-OMP and K-SVD implementations and analyze their complexities. The report is accompanied by Matlab(R) toolboxes which implement these techniques, and can be downloaded at

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 2008
To the main CS technical reports page

Computer science department, Technion