Because of gait sequences are naturally three-dimensional data, there have been several tensorial feature extraction methods to deal with tensors while there are effective tensorial classifiers. In this work, by using a linear tensor projection, a new classifier based on neural networks with random weights is introduced. Due to the proposed algorithm can classify gait samples directly without vectorizing them, the intrinsic structure information of the input data can be reserved. In addition, discriminative features sets are generated using MPCA to ascertain classification accuracy. Finally, Extensive experiments are carried out on two gait databases and results are compared against state-of-the-art techniques. It is demonstrated that the proposed algorithm MPCA plus TNNRE achieves better recognition performance.