Abstract In this paper a new dictionary learning algorithm for multidimensional data is proposed. Unlike most conventional dictionary learning methods which are derived for dealing with vectors or matrices, our algorithm, named K-TSVD, learns a multidimensional dictionary directly via a novel algebraic approach for tensor factorization as proposed in [Braman, 2010; Kilmer et al., 2011; Kilmer and Martin, 2011]. Using this approach one can define a tensorSVD and we propose to extend K-SVD algorithm used for 1-D data to a K-TSVD algorithm for handling 2-D and 3-D data. Our algorithm, based on the idea of sparse coding (using group-sparsity over multidimensional coefficient vectors), alternates between estimating a compact representation and dictionary learning. We analyze our K-TSVD algorithm and demonstrate its result on video completion and video/multispectral image denoising.