Abstract: In order to solve a class of tensor least squares problem arising in the image restoration, an iterative algorithm based on the minimal polynomial extrapolation (MPE) method is proposed. The tensor sequence generated by the minimal polynomial extrapolation acceleration algorithm is proved to converge to the solution of the tensor least squares problem. The new algorithm for the minimal Frobenius parametric solution of the tensor least squares problem is further given. Simulation experiments are designed for the color image restoration and the new algorithm is compared with the fixed-point iterative algorithm, the gradient descent method and the conjugate gradient method. The experimental results illustrate the feasibility and effectiveness of the new algorithm.