The interest around a sparse representation of data is growing in these years due to its several applications such as image classification, image denoising and image compression. Dictionary learning is one of the most important techniques to address this task. With such an approach, data are represented using a large matrix D and a sparse matrix X. Moreover, to deal with multidimensional data, a tensor formulation of the dictionary learning problem has been recently introduced. Within this framework,we propose a new Tensor-Train based nonlinear optimization algorithm and we compare its performance with well established dictionary learning algorithms such as K-SVD, Ho-SuKro and K-HOSVD.