The sparsifying representation plays a significant role in compressive sensing (CS)-based hyperspectral (HS) imaging. Training the dictionaries for each dimension from HS samples is very beneficial to accurate reconstruction. However, the tensor dictionary learning algorithms are limited by a great amount of computation and convergence difficulties. We propose a least squares (LS) type multidimensional dictionary learning algorithm for CS-based HS imaging. We develop a practical method for the dictionary updating stage, which avoids the use of the Kronecker product and thus has lower computation complexity. To guarantee the convergence, we add a pruning stage to the algorithm to ensure the similarity and relativity among data in the spectral dimension. Our experimental results demonstrated that the dictionaries trained using the proposed algorithm performed better at CS-based HS image reconstruction than those trained with traditional LS-type dictionary learning algorithms and the commonly used analytical dictionaries.