This paper proposes a novel uncorrelated multilinear discriminant analysis (UMLDA) algorithm for the challenging problem of gait recognition. A tensor-to-vector projection (TVP) of tensor objects is formulated and the UMLDA is developed using TVP to extract uncorrelated discriminative features directly from tensorial data. The small-sample-size (SSS) problem present when discriminant solutions are applied to the problem of gait recognition is discussed and a regularization procedure is introduced to address it. The effectiveness of the proposed regularization is demonstrated in the experiments and the regularized UMLDA algorithm is shown to outperform other multilinear subspace solutions in gait recognition.