Para resolver sistemas lineales de tensores bajo el producto tensorial tensor-tensor, proponemos el algoritmo Kaczmarz promediado aleatorio (TRAK), el algoritmo Kaczmarz promediado aleatorio con muestreo aleatorio (TRAKS) y su versión de Fourier, que puede implementarse de manera efectiva en un entorno distribuido. Analizamos en detalle las relaciones (de las fórmulas actualizadas) entre los algoritmos originales y sus versiones de Fourier y demostramos que estos nuevos algoritmos pueden converger a la solución única de norma F menos en los sistemas lineales de tensores consistentes. Experimentos numéricos extensos muestran que superan significativamente al algoritmo Kaczmarz aleatorio de tensores (TRK) en términos tanto de recuentos de iteraciones como de tiempos de cálculo y tienen potencial en datos del mundo real, como datos de video, datos de CT, etc.